O(M(n)) division

[Torbjorn Granlund]

Paul.Zimmermann at loria.fr (Paul Zimmermann) writes:

         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?
  
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,
coherent API.)

-- 
Torbjörn