O(M(n)) division
Paul Zimmermann
Paul.Zimmermann at loria.fr
Tue Apr 27 17:45:55 CEST 2004
Hi,
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?
Paul
More information about the gmp-devel
mailing list