Toom-Fool: a fool tool to generate Toom-Cook implementations for GMP

[bodrato at mail.dm.unipi.it]

Ciao!

Since Toom is back again on the mailing-list, I must officially announce
the fool-toom-tool (name suggested by a comment Torbjorn wrote, but
remember to pronounce it something like ful-To-om-tul, with a loong "o" in
Toom, not an "u").

I wrote an awful, ugly script, with GP-Pari, to automatically write
functions like mpn_toom_interpolate_15pts() or mpn_toom115_mul()... Now it
is far from perfect, but it somehow works, and if you want you can try it.

The script can be found on my web-site
http://bodrato.it/toom-cook/Toom-Tool.html

How does it work?
You need the "gp" interpreter installed, then try:

echo "generateToomCode(6)"|gp -quiet ToomGenMPN.gp|head --lines=-1>tc6.c

You will find in tc6.c a working Toom-6 implementation with the functions
mpn_toom_interpolate_11pts, mpn_toom84_mul, mpn_toom75_mul, mpn_toom66_mul.

You can test it with
gcc -DWANT_ASSERT -DCHECK -O3 -lgmp tc6.c -o tc6test
./tc6test 59 58
It will test the code 'till it find an error...

You can somehow tune the output: try

echo "GMP_BITS_PER_LIMB=32;BE_VERBOSE=1;DO_ASSERT=1;generateToomCode(4.5)"

This will write the Toom-4.5 (mpn_toom_interpolate_8pts) code, for a
32-bits environment, with a lot more ASSERT() and comments.

Limitations:
- _interpolate_Npts should be correct from Toom-3.5 (6pts) and passes
(some) tests up to Toom-8 (15pts)
- evaluation for operands with less than four parts are not generated
(e.g. no _toom63 nor _toom72, but only _toom54 for Toom-4.5)
- border/corner-cases are not considered, this means that "n" must be
large enough, and the most significant parts (the not necessarily full
ones) too.
- the set of points used is not the best one... but it allows an easy
sequence generation
- generated code depends on GMP_BITS_PER_LIMB...
- no mixing between interpolation and recomposition parts... yet! A lot
can be done for the Toom-and-a-half (as explained), but we can gain a lot
also on the last part of the balanced Toom, starting from the divisions
(included!).

Bugs:
- too many bugs to be reported :-)

If you will play with this code, please report any observation to me or to
the list.

Let me know,
Marco

PS: next step, as soon as I have some free time, will be some speed test
to have some more complete graphs than the ones I did before:
http://bodrato.it/software/toom.html#TCcomp

-- 
http://bodrato.it/software/