greatest common divisor implementation

[Don]

Matthias Walter wrote:
>>> 1. Are there any further suggestions on the implementations / Did I
>>> forget something?
>> Are benchmarks done with "BigInt" and "long" too? (If you test bigints you need bigger numbers too, and to test that the results are correct).
> I'd like to work on the BigInt things but there are a couple of blockers:
> 
> 1. abs() does not work, because opCmp for BigInts is not pure, yet. IIRC
> Don waits / waited for a pure/nothrow bug to be fixed before he'd
> continue working on BigInt purity, etc.
> 
> 2. I don't think the current random number implementation has code to
> generate BigInts easily via uniform() method. There was a fixed number
> of bits that are used per call.
> 
> So I suggest to work on the Extended Euclidean algorithm implementations
> and get results for int/long for those. If this is done I'll submit a
> pull request with nice code for int+long and code for BigInt that just
> works but is not benchmarked. Then we should change the gcd bug to
> BigInt-only (or open another one...)
> 
> Matthias

There's a (very complicated) O(n log n) algorithm for GCD for large numbers.