Toom-4.5 (aka Toom-5x4, Toom-6x3, Toom-7x2)
dmharvey at cims.nyu.edu
Sat Oct 10 00:04:33 CEST 2009
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
> 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.
More information about the gmp-devel