Toom-4.5 (aka Toom-5x4, Toom-6x3, Toom-7x2)
tg at gmplib.org
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:
#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