[patrick.pelissier@gmail.com: Fwd: Optimizing 1/x]

[Torbjorn Granlund]

Ashod Nakashian <saghmos at xter.net> writes:

  > When it will be finished, I'll submit my implementation to GMP.
  
  Great! Looking forward to it.

We have plans for completely rewritten mpn division (for GMP 5).
It will include Newton inversion, and Barrett's algorithm, with
support for invariant divisors.

(There will also be O(m(n)) exact division, which will be a
constant factor faster than truncating division.)

  > The current GMP division uses a recursive algorithm for large operands,
  > with complexity O(M(n) log(n)), whereas Newton's division has complexity
  > O(M(n)), so we can expect a more-than-constant speedup once Newton's division
  > is in GMP.
  > 
  
  A substantial gain, I'd say. So basically we will be left with the Mul 
  complexity, which floats at about (IIRC) O(n^1.125) for numbers with 
  larger-than-fft-threshold bits.
  
No, M(n) is n*log(n).

-- 
Torbjörn