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

[David Harvey]

On Oct 9, 2009, at 5:15 PM, Niels Möller wrote:

>> (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.
>
> The multiplicative inverse (mod B^2) is 2B + 1, so I'd expect division
> to be cheap. But to get a division by 45, you'd also have to multiply
> by (B^2 - 2B + 1 ) / 45, which is a two limb number.

Ah yes good point.

>> (3) can you do fast Hensel division by 2^64 - 16? (It's not odd, but
>> maybe some sense can be made of this?)
>
> Anyway, I think hensel division or divexact by d = 2^60 - 1 should be
> fairly efficient, or at least multiplication free.

[...]

I don't have time to check through what you've suggested, but another  
approach could be to use 2^48 - 1 (which is also divisible by 45),  
and process each 3-limb block by breaking it up into four 48-bit chunks.

david