| GMP developers' corner |
| ♦Documentation: | Online | PDF |
| ♦Development sources: | GMP repository - Repo usage tips | Daily snapshots |
| ♦Testing: | Current status |
| ♦Tuneup: | Current threshold tables |
| ♦Asm: | Assembly loops |
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.
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:
|
|
|
|
|
|
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 |