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

[Paul Zimmermann]

   Date: Mon, 12 Sep 2005 22:37:48 +0200
   From: Dirk Osterkamp <osterkamp at gmx.de>

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

   [...]

   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.

I don't remember exactly the break-even point I had with my experiments,
but I believe it was less than five million bits.

Paul