Magic speedup

[Jens Hillenbach]

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

Torbjorn Granlund <tg at swox.com> wrote:  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
_______________________________________________
gmp-discuss mailing list
gmp-discuss at swox.com
https://gmplib.org/mailman/listinfo/gmp-discuss


		
---------------------------------
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...
URL: http://gmplib.org/list-archives/gmp-discuss/attachments/20060421/8019322f/attachment.html