Two 10-lines functions

gianrico.fini at gianrico.fini at
Fri Jan 22 14:58:28 CET 2010

>> I know that the function is not there yet. What is mpn_mulmod_bnm1 supposed 
>> do?
>It takes two inputs of sizes 0 < bn <= an <= rn limbs (with some
>additional restrictions), and computes the product mod
>2^{GMP_NUMB_BITS*rn} - 1.

So it is something like the mpn_mulmod_2expm1 I wrote, but it works only for 
2^b-1 with b multiple of limb size?

>The reason it's useful is that it does not (except for small sizes or
>odd rn) compute the full product and then add the high and low halves,
>instead the product is computed mod 2^{GMP_NUMB_BITS*rn/2} - 1
>(recursively) and mod 2^{GMP_NUMB_BITS*rn/2} + 1 (full mul + wrapping
>for small and moderate sizes, FFT multiplication with "built in"
>wraparound for large sizes), and these two values are then CRT:ed
>together. Here's a benchmark comparing it to a full multiplication:

It must also be more complicated and quicker than mine. I have not benchmarked 
my function, I have only tested it.

>(And to be clear, mpn_mulmod_bnm1 is an *internal* function, it can
>change or even disappear between any two releases).

It can not be used by applications? For this, it is not documented?

>Too me, they seem too applicaton specific to fit in GMP, but maybe
>there are some relevant use cases?

I do not know. You seem to have very similar functions. It is possible that 
the existing functions can be changed to work also with the precision of bits. 
I'm sure you can do it quicker than I. But not shorter!

Thanks for the informations about the internal functions.


More information about the gmp-devel mailing list