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

[Dirk Osterkamp]

> * Newton's iteration isn't currently implemented in GMP, even for the
>   integer division. The main reason is that you need to carefully analyze
>   the roundoff errors to get a correct answer (as in the above proposal).
>   I've implemented several variants which are quite fast; however the
>   fastest known algorithm is currently under a patent from HP, and I failed
>   so far to obtain a license for use within GMP...

There is an interessting thesis from Hasselström, in which he has 
investigated newton division using gmp.

http://www.treskal.com/kalle/exjobb/

Abstract:

Fast Division of Large Integers – A Comparison of Algorithms

I have investigated, theoretically and experimentally, under what 
circumstances Newton division (inversion of the divisor with Newton's 
method, followed by division with Barrett's method) is the fastest 
algorithm for integer division. The competition mainly consists of a 
recursive algorithm by Burnikel and Ziegler.

For divisions where the dividend has twice as many bits as the divisor, 
Newton division is asymptotically fastest if multiplication of two n-bit 
integers can be done in time O(n^c) for c < 1.297, which is the case in 
both theory and practice. My implementation of Newton division (using 
subroutines from GMP, the GNU Multiple Precision Arithmetic Library) is 
faster than Burnikel and Ziegler's recursive algorithm (a part of GMP) 
for divisors larger than about five million bits (one and a half million 
decimal digits), on a standard PC.

Regards,

Dirk Osterkamp