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

[Torbjorn Granlund]

Marco,

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)
#else
#define mpn_divexact_by45(dst,src,size) mpn_divexact_1(dst,src,size,45)
#endif
#endif

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
code.

-- 
Torbjörn