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

[David Harvey]

On Oct 9, 2009, at 12:47 PM, Torbjorn Granlund wrote:

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

A few other random ideas:

(1) can the evaluation points in Marco's code be changed so that  
division by 45 becomes something else that succumbs to these tricks?

(2) can you do fast Hensel division by B^2 - 2*B + 1? Maybe the only  
way is to divide by B - 1 twice, or maybe something faster is possible.

(3) can you do fast Hensel division by 2^64 - 16? (It's not odd, but  
maybe some sense can be made of this?)

david