Schönhage's algorithm for fast integer GCD
Sat, 14 Jun 2003 09:28:57 +1000
firstname.lastname@example.org (Niels Möller) writes:
> I haven't done any benchmarks yet (that's mostly pointless without a
> good basecase), but my gut feeling is that the algorithm can be
> competitive for moderately large numbers, say about a few hundred
Paul Z had a go at something similar and only found thresholds up in
the thousands of limbs.
A gcd of that size takes a long time anyway, so it's almost hard to be
too worried about it. Or on the other hand perhaps if someone really
needs such sizes they'll appreciate whatever help they can get :).
> * r = u1 (a1 2^ n + a2) + v1 (b1 2^n + b2)
Yes, if I remember rightly a divide and conquer along those lines is
the way to go. I forget quite what the complexity comes out as, it
might be a rather modestly sub-quadratic exponent, and biggish