Multi-modular techniques |
Naive algorithms for bidirectional multi-modular transformers are
implemented in
The following piece of code computes 101 modulo 2, 3, 5, and 7:
|
Here
Let be a subset of a ring
.
A covering
of
is a set of coprime elements of
such that any
element of
is uniquely charaterized by its
residues modulo all the elements of
.
The class . For
example for the integers, the following instructions fill the vector
with a covering for integers of 30 bits.
|
Here the default covering being used is made of the sequence of the
prime numbers: 2, 3, 5, 7, 11, etc. The value returned in
The sequence used for the covering can be specified as an extra argument:
|
Here are used prime numbers of at most 10 bits. The first ones are well-suited to FFT.
Support for long integers is available in crt_integer.hpp. The following piece of code covers signed integers of 1000 bits with prime hardware integers of at most 20 bits:
|
The divide and conquer algorithm is implemented in
|
If the moduli are small, it is often faster to use the naive
algorithm. While for large moduli the divide and conquer has soft
linear cost. In
|
Here 10 is the threshold between the two transformers: each block of 10 moduli is using the naive algorithm, and then the dichotomic algorithm is called with the moduli obtained from the products of those of each block.