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

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

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

> PPS: Toom-6.5 will require divisions by: 2835*4, 42525, 9*4, 255. Only the
> last one is good... Tricks/suggestions for the others?

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

42525 = 3^5 * 5^2 * 7. Could divide by 3^2 * 5^2 * 7 (factor of 2^60 -
1) and 3^3 (factor of 2^54 - 1).

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

I'll see if I can get some division using 2^60-1 working.

/Niels