Two 10-lines functions

[bodrato at mail.dm.unipi.it]

Gian,

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

I did some very simple testing and a small benchmark:
   n    mul  mulmod_bnm1  mulmod_2expm1
  20   2139       0.836          1.070
  83  22975       1.008          1.026
 146  54820       0.728          1.020
 209  93124       1.006          1.019
 272 136258       0.604          1.017
 335 178806       1.003          1.014
 398 227124       0.785          1.015
 461 276010       1.004          1.014

Where n is the number of limbs (not bits!), column "mul" gives times (in
cycles), then relative times for the respective functions (>1 means slower
than mul, <1 means faster).
I tested both even and odd numbers. You function is slower for any value,
but not terribly slower for odd sizes, when mul is faster anyway (both
mulmod simply use mul+some wrapping).

>>(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?

In this list we discuss developing of the library. When developing
internal functions we use any function and macro we have and need. To be
honest... I did not read the manual when I started contributing to GMP, I
usually read the code directly.
When/if the interface of mpn_mulmod_bnm1 will be very stable (it will
probably be changed soon, because of observations on memory usage by Paul
et alias), it _may_ be documented and exported.

>>Too me, they seem too application 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.

IIRC Niels suggested some time ago that we could try to split
odd-limb-sized mulmod using bitwise shifts... Do I remember wrongly?
Currently we simply try to avoid odd sizes, by using an (internal again)
mpn_mulmod_bnm1_next_size function that suggests sizes to be used, so that
many split are possible before using the base case (hopefully used for
small sizes only).
You may want to look at current mulmod implementation:
http://gmplib.org:8000/gmp/file/tip/mpn/generic/mulmod_bnm1.c
and generalise it to bit sizes? Then we will benchmark it again.

Regards,
Marco

-- 
http://bodrato.it/