For project "Faster multiplication": faster Toom-3, proposed Toom-4

Marco Bodrato bodrato at
Mon Nov 20 22:25:09 CET 2006

Dear Paul and Torbjörn,

I have to thank you both for your help and stimulating comments.

> Paul.Zimmermann at (Paul Zimmermann) writes:
>   Quite interesting! Did you try to implement your new algorithm in GMP,
>   and compare it to the gmp-4.2.1 code? You can use "make tune" in the

Implementation done, and now it's ready to be seen, you can find it on:, with some speed test. Gain on my
Centino is around 1%. Tests on different platforms would be useful.

As a "bonus" I implemented also Toom5, Toom6 and Toom7, in a non optimized
fashion. Anyway Toom-Cook 5x5, 6x6 and 7x7 are all faster than actual code.

On 26 Oct 2006 13:15:28 +0200, Torbjorn Granlund wrote
> The use of exhaustive search to discover new algorithms is something I
> have played with myself, using the GNU superoptimizer.  The super-

The not so easy problem with exhaustive search is to find a model:
-large enough, so that results will be useful,
-small enough, so that the answer will arrive in reasonable time.

Regards, Marco


More information about the gmp-devel mailing list