GMP developers' corner

GMP release update

GMP 5.0.0 was received well, and no major bugs have been reported. There are a number of issues with Mac OS X, memory appetite issues with multiplication, and problems with fat builds. We have solved most of these problems, and fixed them in 5.0.1. We will still recommend the latest GMP 4.3 as the stable release.

New Toom multiplication code for unbalanced operands

We have been adding more Toom functions during the last years, mainly for better handling of unbalanced operands.

We believe that even more Toom functions might be needed for optimal performance, probably going further than 8 evaluation points (used by toom54, toom63, toom72). This will largely depend on ongoing work on FFT multiplication; the faster that will become, the less room for higher-order Toom. The large number of functions is a bit disturbing, of course, since complexity is always bad. (But performance is GMP's main objective.)

These pictures show the best current multiplication primitive for operand sizes 1 ≤ bn ≤ an ≤ N limbs, where N is indicated in each diagram. The x-axis represents an, which is the size of the first operand; the y-axis represents bn, the size of the second operand. The first picture uses linear scale, the second uses log/log scale. For larger scale, click the pictures.

Comments:

• GMP 4.3 uses schoolbook, toom22, tom32, toom42, toom33, toom44, and FFT.
• The GMP repo code uses (as of 2009-10-03) the same basic functions, but the algorithm selection code for unbalanced operands has been improved.
• FFT takes over for larger operands for machines with faster hardware multiplication. AMD's processors have great hardware multiplication, Core i7's multiplication has twice Athlon's latency, and the venerable Pentium 4 has really poor hardware multiplication. Basecase (a k a schoolbook) multiplication performance is direct function of hardware multiplication performance. And since the various Toom functions recurse into a large number of smaller basecase function invocations, their performance is also very linked. But FFT performs most of its work doing shifts and additions, and while these are also faster on Athlons, the other processors are closer behind.

The ideas behind much of the Toom multiply improvements are due to Marco Bodrato and Alberto Zanoni. Please see Marco Bodrato's site for more information about Toom multiplication. The algorithmic foundation was made by Anatolii Alexeevitch Karatsuba in 1962, and Andrei Toom in 1963. The GMP implementations were made by Marco Bodrato, Niels Möller, and Torbjörn Granlund.

This tool is useful for for optimising the evaluation sequences of Toom functions. It exhaustively searches for possible sequences, given a goal function. It is similar to the GNU superoptimizer, except that this program optimises over a a simple algebraic structure and handles m-ary -> n-ary projections (the GNU superoptimizer optimises over an assembly language subset, and handles m-ary -> 1-ary projections). This is very immature code, but it seems to work.

Download files	Last changed	What changed?
superopt-va.c	2007-01-16/2	speedup+UI improvement
goal-va.def	2007-01-16	bug fixes