[patrick.pelissier@gmail.com: Fwd: Optimizing 1/x]
Dirk Osterkamp
osterkamp at gmx.de
Mon Sep 12 22:37:48 CEST 2005
> * 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
More information about the gmp-discuss
mailing list