Re: Public domain algorithm for arbitrary-precision fast division?

Helmut Jarausch wrote:
> Greg Lovern wrote:
>> I'm looking for an algorithm for doing arbitrary-precision (bignum)
>> division more quickly than the "long division" method taught to school
>> children.
>
> Depending on the number of digits there are methods which are
> dramatically faster.
> AFAIK, the fastest method uses fast multiplication by two steps.
> To compute a/b do
>
> 1.) compute 1/b without any division. That can be done by Newton's method
> applied to the function f(x) = 1/x - b giving the quadratic
> convergent
> iteration x<- x*(2-b*x) (Use a standard precision (64-bit
> hardware floating point)
> approximation to 1/b as initial value of x).
> Quadratic convergence means: the number of exact digits doubles in
> each iteration!
>
> 2) compute a*(1/b)
>
> Now, you have to use a fast multiplication. There are many of them
> e.g. by using the Fast Fourier Transform
> or
> http://mathworld.wolfram.com/KaratsubaMultiplication.html
> or
> http://en.wikipedia.org/wiki/Schönhage-Strassen_algorithm
>
> and probably some more.
>
> Google for multiple precision arithmetic.

David N. Williams wrote:
> [...]
> I'm not expert on the literature, but my impression from my own
> searches is that Knuth's division algorithm is likely to be
> about as fast as the current state of the art, for general
> purposes. I'd certainly like to know if that's not true!

Dave Rusin sent a private response to my post, mentioning
Newton's method and kindly explaining a bit about FFT
multiplication, which made me realize that my impression was, to
say the least, fuzzy.

So I tried to get a more precise feel for when Knuth's
multiplication and division algorithms are better by looking at
the documentation for GMP 4.2.4 (GNU Multiple Precision
Arithmetic Library):

http://gmplib.org/
http://gmplib.org/manual/Multiplication-Algorithms.html#Multiplication-Algorithms
http://gmplib.org/manual/Division-Algorithms.html#Division-Algorithms

If I read that correctly, Knuth is thought to be roughly better
for multiplication when the number of limbs* is below
MUL_KARATSUBA_THRESHOLD, and below DIV_DC_THRESHOLD for
division. The latter is said to be about twice the former. And
according to the source file gmp-impl.h:

/* If MUL_KARATSUBA_THRESHOLD is not already defined, define it to a
value which is good on most machines. */
#ifndef MUL_KARATSUBA_THRESHOLD
#define MUL_KARATSUBA_THRESHOLD 32
#endif

It appears that MUL_FFT_THRESHOLD is roughly 128 * 3 * 10 =
3,840, with other non-Knuth methods preferred between 32 and
3,840.

For 2N by N limb division, Newton's method sets in for "large to
very large N". On the other hand, on some machines it is faster
than hardware division, and is then used for the machine-size
division steps in the algorithms.

(Hope I've got all of this right!)

I've never used it, but I must say that from the outside, GMP
seems pretty impressive. It appears to have undergone a lot of
theoretical and empirical algorithm analysis, tuned for various
cpus.

The OP says he doesn't want "... any GNU or similar
restrictions." But I wonder if GMP wouldn't be okay -- since
GMP is under the LGPL, not the GPL, his software wouldn't suffer
unusual restrictions by linking to the GMP library.

I'd appreciate corrections to any of the above info. And what
are the disadvantages of GMP?

-- David

* A "limb" stores a base 2^[n-1] digit, where n is the number of
bits in a machine word.
.

Relevant Pages

  • Re: Public domain algorithm for arbitrary-precision fast division?
    ... David N. Williams wrote: ... >> I'm looking for an algorithm for doing arbitrary-precision ... the fastest method uses fast multiplication by two steps. ... I've never used it, but I must say that from the outside, GMP ...
    (sci.math.num-analysis)
  • Re: Fast Binary-to-Decimal Conversion Algorithms?
    ... >> about he needs the kind of stuff that they use in gmp. ... Notice that the ADD-3 to TENS suddenly is ... i.e. a register long enough to hold the value. ... It's a nice algorithm and you have a good writeup, ...
    (comp.programming)
  • Re: Diophantine matters
    ... on the internet - either as mathematical formulae or as computer code. ... P. Zimmerman's implementation using GMP at ... Could this algorithm (or perhaps the LLL ...
    (sci.math.symbolic)
  • Re: Diophantine matters
    ... on the internet - either as mathematical formulae or as computer code. ... P. Zimmerman's implementation using GMP at ... Could this algorithm (or perhaps the LLL ...
    (sci.math.symbolic)
  • Re: Dividing long numbers
    ... something else) seemed to be the big bottleneck. ... to me like I was using the right approach, only that my algorithm was ... You might, as an alternative, use GMP. ...
    (sci.crypt)