#include <gmp.h>
#include "array.h"
Go to the source code of this file.
Defines | |
| #define | _TIFA_X_TREE_H_ |
Typedefs | |
| typedef mpz_array_t | mpz_tree_t |
Equivalent to mpz_array_t. | |
Functions | |
| mpz_tree_t * | prod_tree (const mpz_array_t *const array) |
Computes the product tree of some mpz_t integers. | |
| mpz_tree_t * | prod_tree_mod (const mpz_array_t *const array, const mpz_t n) |
Computes the product tree of some mpz_t integers modulo a positive integer. | |
| mpz_tree_t * | prod_tree_ui (const uint32_array_t *const array) |
Computes the product tree of some uint32_t integers. | |
| mpz_tree_t * | rem_tree (const mpz_t z, const mpz_tree_t *const ptree) |
| Computes a remainder tree. | |
| void | free_mpz_tree (mpz_tree_t *tree) |
Clears a tree of mpz_t integers. | |
| void | print_mpz_tree (const mpz_tree_t *const tree) |
Prints a tree of mpz_t integers. | |
Definition in file x_tree.h.
Equivalent to mpz_array_t.
While an mpz_tree_t is just an mpz_array_t, its memory is allocated in a different manner than in the mpz_array_t case. Indeed, the elements of an mpz_tree_t array should NOT be modified later on since the memory used is allocated in one huge block to prevent overhead from multiple malloc calls. So the allocated memory of the mpz_t's in the tree can NOT be increased.
The mpz_tree_t typedef is introduced only as a reminder of this different underlying memory allocation. free_mpz_tree should be used to clear the memory space occupied by an mpz_tree_t. Do NOT call free_mpz_array on an mpz_tree_t!
| void free_mpz_tree | ( | mpz_tree_t * | tree | ) |
Clears a tree of mpz_t integers.
Clears a tree of mpz_t integers returned by prod_tree, prod_tree_ui or rem_tree.
free_mpz_array. Indeed, even if the mpz_tree_t type is merely a typedef of mpz_array_t, the memory used by the mpz_t elements is allocated in a completely different manner, hence the need for a different function.| [in] | tree | Pointer to the mpz_tree_t to clear. |
| void print_mpz_tree | ( | const mpz_tree_t *const | tree | ) |
Prints a tree of mpz_t integers.
Prints a tree of mpz_t integers on the standard output. Useful only for debugging purposes and for relatively small trees.
| [in] | tree | Pointer to the mpz_array_t containing the tree to print. |
| mpz_tree_t* prod_tree | ( | const mpz_array_t *const | array | ) |
Computes the product tree of some mpz_t integers.
Computes the product tree of the mpz_t integers given by array and returns it as a newly allocated mpz_tree_t.
mpz_array_t tree with the usual compact representation: tree->data[2i+1] and tree->data[2i+2] are the children of the node tree->data[i].array->length equals to a power of 2. If this is not the case, the product tree will be computed as if array was completed by as many useless nodes as necessary until a power of 2 is reached.This choice was made to keep a space efficient representation and to avoid dynamic allocations of nodes.
mpz_tree_t structure (i.e. an mpz_array_t), the elements of the array should NOT be modified later on since the memory used is allocated in one huge block to prevent overhead from multiple malloc calls. So the allocated memory of the mpz_t's in the array can NOT be increased...| [in] | array | Pointer to the mpz_array_t containing the mpz_t integers to multiply. |
mpz_tree_t holding the computed product tree. | mpz_tree_t* prod_tree_mod | ( | const mpz_array_t *const | array, | |
| const mpz_t | n | |||
| ) |
Computes the product tree of some mpz_t integers modulo a positive integer.
Similar to prod_tree but each node is reduced mod n.
prod_tree(const mpz_array_t* const array).| [in] | array | Pointer to the mpz_array_t containing the mpz_t integers to multiply. |
| [in] | n | The positive modulo. |
mpz_tree_t holding the computed product tree. | mpz_tree_t* prod_tree_ui | ( | const uint32_array_t *const | array | ) |
Computes the product tree of some uint32_t integers.
Computes the product tree of the uint32_t integers given by array and returns it as a newly allocated mpz_tree_t.
mpz_array_t tree with the usual compact representation: tree->data[2i+1] and tree->data[2i+2] are the children of the node tree->data[i].array->length equals to a power of 2. If this is not the case, the product tree will be computed as if array was completed by as many useless nodes as necessary until a power of 2 is reached.This choice was made to keep a space efficient representation and to avoid dynamic allocations of nodes.
mpz_tree_t structure (i.e. an mpz_array_t), the elements of the array should NOT be modified later on since the memory used is allocated in one huge block to prevent overhead from multiple malloc calls. So the allocated memory of the mpz_t's in the array can NOT be increased...| [in] | array | Pointer to the uint32_array_t containing the mpz_t integers to multiply. |
mpz_tree_t holding the computed product tree. | mpz_tree_t* rem_tree | ( | const mpz_t | z, | |
| const mpz_tree_t *const | ptree | |||
| ) |
Computes a remainder tree.
Computes the remainder tree of z by the mpz_t integers whose product tree is given by ptree and returns it as a newly allocated mpz_tree_t. If rtree is the returned remainder tree, then one has: rtree->data[i] = z mod ptree->data[i].
mpz_array_t tree with the usual compact representation: tree->data[2i+1] and tree->data[2i+2] are the children of the node tree->data[i].mpz_tree_t structure (i.e. an mpz_array_t), the elements of the array should NOT be modified later on since the memory used is allocated in one huge block to prevent overhead from multiple malloc calls. So the allocated memory of the mpz_t's in the array can NOT be increased...| [in] | z | The integer to divide. |
| [in] | ptree | Pointer to the mpz_tree_t containing the product tree of the mpz_t integers to divide z by. |
mpz_tree_t holding the computed remainder tree.