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

[bodrato at mail.dm.unipi.it]

Dear David,

> On Oct 9, 2009, at 12:47 PM, Torbjorn Granlund wrote:
>> factors (B is the limb base).  Unfortunately, neither 2^32-1 or 2^64-1
>> is divisible by 45=3*3*5.  But 2^(12n)-1 is.  So we should be able to
>> form 60-bit "minilimbs" on-the-fly, and combine that with bdiv_dbm1c's

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

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... Probably it doesn't worth writing the
code. How much faster those tricks are with respect to general divexact?

I wrote the one with evaluations in {1/2,1,2}. Divisions are by 9 and 15.
The same used by Toom-4. So that I could steal the #define BINVERT_9,
moreover any trick one can implement for those divisions will improve both
Toom-4 and Toom-4.5.

It is available, as usual, at http://bodrato.it/software/toom.html#TC4.5
I prefer the first version... but if someone want to test them both...

Regards,
Marco

PS: Why not #define BINVERT_9 ((BINVERT_3*BINVERT_3)&GMP_NUMB_MAX) ? :-P
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?

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