precomputed modular reductions in GMP?
dmharvey at math.harvard.edu
Mon Aug 28 21:54:53 CEST 2006
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:
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!
More information about the gmp-discuss