Magic speedup

Jens Hillenbach jhillenbach at
Fri Apr 21 12:06:48 CEST 2006

Congratulation to the speedup. May I ask what function M is in O(M(n))?

Torbjorn Granlund <tg at> wrote:  I only now regenerated the "Computing billions of pi digits using GMP"
page for GMP 4.2, see

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.

gmp-discuss mailing list
gmp-discuss at

Yahoo! Messenger with Voice. Make PC-to-Phone Calls to the US (and 30+ countries) for 2¢/min or less.
-------------- next part --------------
An HTML attachment was scrubbed...

More information about the gmp-discuss mailing list