redc_c
Zimmermann Paul
Paul.Zimmermann at loria.fr
Tue Feb 28 21:31:32 CET 2012
> Hi everyone, I'm a grad student at the University of Massachusetts. I work
> on high precision arithmetic for GPUs.I was looking at the implementation of
> the redc_n function and was blown away. It's such a clever useof
> mpn_mulmod_bnm1. From reading the docs / change log, it looks like the
> mpn_mulmod_bnm1 stuff can be used to accelerate other functions as well.
> So, here's my question -- is there a main paper tocite for the origin of
> this idea (i.e. using mulmod_bnm1 to accelerate various computations)?
> And further,is there a paper to cite for the specific use of mulmod_bnm1 in
> REDC?
> Many thanks,Niall Emmart
the idea behind redc_n is simply the Chinese Remainder Theorem: if you have a
number C of 2n limbs, and know its low n limbs (mullo) and its value mod B^n-1,
where B correspond to one limb, then you can easily reconstruct C.
For large n what is interesting is that the value mod B^n-1 can be computed
faster using FFT: it is equivalent to multiplying two numbers of n/2 limbs.
This is known as the "wrap-around trick", see for example Section 3.4 of
Modern Computer Arithmetic, Richard Brent and Paul Zimmermann, Cambridge
University Press, 2010 (also available online).
Paul Zimmermann
More information about the gmp-discuss
mailing list