precomputed modular reductions in GMP?

[David Harvey]

On Aug 28, 2006, at 11:35 AM, Torbjorn Granlund wrote:

> You're welcome to contribute in this area, but please start with what
> is already at the GMP development pages.

Wow.... after following up some of the links and algorithms you  
mentioned, I can see that an awful lot of clever people have thought  
about this question a LOT.

I would love to be able to contribute, but time is a bit short right  
now. I'll get back to you if that changes.


>>   Are there any plans to add to GMP an interface for doing modular
>>   arithmetic with respect to a given base, where some kind of
>>   precomputation is performed to speed up the reductions, like I
>>   suggest above? If there aren't any such plans, pretty pretty please
>>   add this to the to-do list .... :-)
>
> Plans, but vague.
>
> There will be functions at the mpn level with all needed support, but
> not sure about any higher level stuff.

I did notice the following thread from about two years ago:

http://gmplib.org/list-archives/gmp-devel/2004-February/000382.html

Did these "mpz_prediv_t" structs get any further?

It does seem sensible for GMP to include some kind of higher-level  
interface like this. I for one would be extremely happy if an  
interface was available in GMP 5, even if the code backing it was not  
that fantastic yet. It sounds like you guys have already thought  
quite a lot about the basic algorithms that could be used, and it's  
just a question of implementing and tuning them. In other words, it  
sounds like you already know enough about the structural requirements  
to design a good interface.

I think for now what I will do in SAGE is ensure that the classes/ 
interfaces we design are compatible with introducing some  
precomputation later on. I might throw in my simple version for very  
large integers just to get us started, since I've already got the  
code written, and then if something better comes along I can throw  
that in too.

We at SAGE are big fans of GMP. Keep up the good work!

David