prodtree.h (1088B)
1 #ifndef _PRODTREE_H_ 2 #define _PRODTREE_H_ 3 4 #include <err.h> 5 #include <fmpz.h> 6 #include <fmpz_vec.h> 7 #include <stdio.h> 8 #include <stdlib.h> 9 10 /** 11 * Compute a prodtree from a vector. 12 * 13 * Given a vector v of length bv we first pad a product tree is 14 * constructed by first padding the vector with ones to make it a vector 15 * of length a power of 2. This vector forms the leaves of the product 16 * tree, and the remaining (complete binary) tree is formed by takning 17 * the pairwise product of the children of a node. 18 * 19 * This function allocates a new vector for the tree, the function 20 * calling this has to free the tree. 21 * 22 * @param res pointer to the vector to initialize 23 * @param v vector to compute the product tree from 24 * @param nv size of the vector n 25 * @returns size of the product tree 26 */ 27 slong prodtree_compute(fmpz **res, const fmpz *v, slong nv); 28 29 /** 30 * Pretty print a product tree. 31 * 32 * @param v the product tree to print (as a vector) 33 * @param nv the size (number of nodes) of the prouct tree 34 */ 35 void prodtree_pprint(const fmpz *v, const slong nv); 36 37 #endif