Two 10-lines functions
gianrico.fini at terra.es
gianrico.fini at terra.es
Thu Jan 21 13:11:40 CET 2010
>There is no function mpn_mulmod_2expp1 in any version of GMP. (But an
>early version of mpn_mulmod_bnm1 was called something like that.)
I know that the function is not there yet. What is mpn_mulmod_bnm1 supposed to
do?
> It computes the product of xp and yp modulo 2^b+1. It assumes that xp and
yp
> have exactly b bits.
>
>What does it mean that "xp has exactly b bits"? That 2^(b-1) <= xp <
>2^b? It looks like your code does not handle any b value, or there
The function multiply two numbers modulo 2^b+1. xp points to one of them, and
contains allways b bits of that number X.
The number can be smaller than 2^(b-1)! Not all bits are set, but the bits
higher than b are zero.
If X is 2^b, then all the b bits are zero, and the parameter c is used for the
last bit.
The same for yp and the result.
>I'd suspect mpn_mul_fft might be directly applicable for that. It has
>existed in GMP since the dark ages...
Possible, but mpn_mul_fft is not documented. The 10-lines function works for
any b, using only documented functions.
>I am not sure what do do with your contribution, and where it would fit
>in.
If you need my functions, I'm happy to give them to you. If you don't, no
problems. I was challenged and I wrote them.
Gian.
More information about the gmp-devel
mailing list