Actually that is a slightly misleading benchmark, because it takes 1.9s to generate all the primes. In other words, it only takes 0.3s to do the actual CRT.
Bill. 2009/11/15 Bill Hart <[email protected]>: > 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 -~----------~----~----~----~------~----~------~--~---
