Magic speedup

Torbjorn Granlund tg at swox.com
Fri Apr 21 10:22:56 CEST 2006


I only now regenerated the "Computing billions of pi digits using GMP"
page for GMP 4.2, see http://swox.com/gmp/pi-with-gmp.html.

The speedups I got for 4.1.4 => 4.2 was surprising.  Computing 1e9
digits used to take 34300 seconds, now it takes just 8859 seconds on
an Opteron.  The main sources of speedup should be the x86_64 assembly
and Paul Zimmermann's 2003 FFT improvements.  But still a speedup of
almost 4x is much, much more than I had expected.

The numbers still suffers from that division in GMP is O(M(n)log(n))
instead of just O(M(n)).  The divisions in Chudnovsky's algorithm are
exact, and since we plan O(M(n)) exact division for a future GMP
version, things will improve further in the future.

--
Torbjörn


More information about the gmp-discuss mailing list