O(M(n)) division

[Paul Zimmermann]

       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