Toom-4.5 (aka Toom-5x4, Toom-6x3, Toom-7x2)

Torbjorn Granlund tg at
Fri Oct 9 18:47:33 CEST 2009


May I invoke your assign.future and put this into the GMP repo?

I looked very briefly, and saw the division by 45.  This is relatively
expensive, as GMP looks today.  There is already an (internal)
interfaces where you can provide the inverse, mpn_bdiv_q_1_pi1.

I'd suggest code like this:

#ifndef mpn_divexact_by45
#if HAVE_NATIVE_mpn_bdiv_q_1_pi1
#define mpn_divexact_by45(dst,src,size) mpn_bdiv_q_1_pi1(dst,src,size,45,BINVERT_45,0)
#define mpn_divexact_by45(dst,src,size) mpn_divexact_1(dst,src,size,45)

I suspect we could do much, much better with some tricks like those of
bdiv_dbm1c, which makes use of the fact B-1 is divisible by small
factors (B is the limb base).  Unfortunately, neither 2^32-1 or 2^64-1
is divisible by 45=3*3*5.  But 2^(12n)-1 is.  So we should be able to
form 60-bit "minilimbs" on-the-fly, and combine that with bdiv_dbm1c's


More information about the gmp-devel mailing list