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

[bodrato at mail.dm.unipi.it]

Ciao!

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

The choices are 45*3 or 15*9... if we can both do fast division by 15
(4|b) and by 9 (6|b), than we can do fast division by 45 (12|b)...

> Evaluation in 0, oo, ±1, ±2, ±1/2 gives a matrix with determinant
>
>   9331200 = 2^9 * 3^6 * 5^2

I evaluated in 0, oo, ±1, ±2, ±4, but this does not change the odd part of
the determinant: 3^6*5^2

> So these are the numbers we have to divide out somewhere in the
> interpolation. If we want to use the B-1 trick, we can only divide by
> 3, 5 or 15 at a time, so we'd need at least 6 divisions. Combining
> factors, such as 45 = 3^2 * 5, gives fewer but more expensive
> divisions.

Then I used "early recomposition", this means that we have to face only
the square root of the determinant: 3^3*5. Alternatives are: two
divisions, with one not as fast as hoped... or three 3*3*15.

But remember, in toom_interpolate_7pts we have mpn_divexact_by9.
Efforts should be focused on that division first, because it affects the
balanced Toom-4.

Regards,
Marco

-- 
http://bodrato.it/toom-cook/