Thanks Robert, Actually I have something like this in FLINT, though it uses mpn's instead of mpz's. It takes 2.2s to do the benchmark you give. Of course the machine I'm using is pretty powerful (2.4GHz Opteron K10).
I'm not doing any balancing when building the product tree, but it does use a divide and conquer algorithm which reverts to a basecase when that is faster. Actually, nowadays multimodular reduction could also be sped up using the new mpn_mod_1_? functions which Jason implemented in MPIR. Anyhow, thanks again for the contribution. Bill. 2009/11/15 gerrob <[email protected]>: > > Read on http://gmplib.org/tasks.html that you/gmp needs an > implementation for Chinese Remainder Theorem, on googlegroup I've > uploaded two codes that solves it: mpz_crt_coprime works for pairwise > coprime modulus, and mpz_crt works in general. One timing: > > crt_coprime solves the > x==i mod prime(i) > for 0<=i<131072 system in about 4 seconds on my machine. > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en -~----------~----~----~----~------~----~------~--~---
