tg at swox.com
Tue Apr 27 18:03:27 CEST 2004
Paul.Zimmermann at loria.fr (Paul Zimmermann) writes:
I've just implemented a nice way due to Scho"nhage to compute Pi using the AGM.
It only uses squarings and square roots. Unfortunately the square root
(mpn_sqrtrem) relies on the division, which has complexity O(M(n) log n) in
gmp-4.1.2, so the square roots take most of the total time:
mermoz% ./a.out 5000000 # compute 5000000 bits of Pi
division took 1670ms
multiplication took 4820ms
square root took 27640ms
mpfr_const_pi2 took 34220ms
output took 3250ms
I've heard in the past that a O(M(n)) division was in progress, based on
Newton's method. Is that available somewhere?
We are far from ready with it, mainly since we moved our goals
as the work progressed.
(We are working on a complete rewrite of mpn division, with a new,
More information about the gmp-devel