[firstname.lastname@example.org: Fwd: Optimizing 1/x]
Paul.Zimmermann at loria.fr
Tue Sep 13 09:08:09 CEST 2005
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.
More information about the gmp-discuss