[prev in list] [next in list] [prev in thread] [next in thread] 

List:       gmp-devel
Subject:    Two 10-lines functions
From:       gianrico.fini () terra ! es (gianrico ! fini at terra ! es)
Date:       2010-01-22 13:58:28
Message-ID: 23817115.1087821264168708400.JavaMail.defaultUser () defaultHost
[Download RAW message or body]

>> I know that the function is not there yet. What is mpn_mulmod_bnm1 supposed 
to 
>> 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.

Gian.

[prev in list] [next in list] [prev in thread] [next in thread]