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

[bodrato at mail.dm.unipi.it]

Ciao Niels,

>> Yes, they can... evaluating in {1,2,3}, instead of {1,2,4}, gives a
>> division by 3 and one by 15; but it needs a trickier evaluation and a
>> spurious 2/3 of a division by 3...
>
> Evaluation in 3 would use some shifting and adding rather than
> multiplies, but I imagine it's going to be more costly than evaluation
> in 4?
>
> The 2 in 2/3 should be easy to handle, by passing in 2*(2^64 -1) / 3
> to mpn_bdiv_dbm1c, right?

Sorry, I did not explain it clearly.
I mean: evaluating in {1,2,3} I need a division by 3 and one by 15, both
on operands of (3*n) limbs. But I also need a "spurious" division by 3 on
a smaller operand: (2*n) limbs. I called it "two third of a division" :-D

> For 2835 = 3^4 * 5 * 7 the closest I get is 2^54 - 1, which is
> divisible by 3^4*7, but not by 5. Could do one divide by 3^2 * 5 * 7
> (factor of 2^60-1) and 3^2 (also a factor of 2^60 - 1).

Is the division by 3 (a divisor of B-1) twice as fast as the division by 9
(not a divisor)? If it is not, then I'll prefer one slow division. If it
is, then I'll #define div_by9() {div_by3(); div_by3();} ...

> And finally, 255 is a factor of 2^60 - 1.

You mean "of 2^8n -1"

Regards,
Marco

-- 
http://bodrato.it/