Schönhage's algorithm for fast integer GCD

[Kevin Ryde]

nisse@lysator.liu.se (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
> limbs.

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
overheads.