greatest common divisor implementation

[Matthias Walter]

On 02/07/2011 05:13 PM, Andrei Alexandrescu wrote:
> On 2/7/11 3:18 PM, Matthias Walter wrote:
>> Hi everyone,
>>
>> as I'm currently working on a C++ project which involves gcd
>> computations I had a quick look at phobos' implementation.
>>
>> 1. First thing I saw is that gcd(-3,6) raises an exception, although
>> mathematically it is just 2. Of course checking the sign of the
>> arguments takes computation time, but for my stuff I'd definitely need
>> it. If it's really too expensive then there should be at least another
>> routine.
>>
>> 2. I'd be happy to implement the Extended Euclidean algorithm for phobos
>> which also gives multipliers s and t such that gcd(x,y) = s*x + t*y.
>>
>> Any comments before I start working on it?
>>
>> Matthias
>
> Please do. I implemented gcd in a hurry because I needed it for
> unsigned numbers, so it's not the greatest it could be. A github pull
> request would be much appreciated!
I re-implemented [1] several things like recursive / iterative or modulo
/ binary implementations. For the latter I found one with a lookup-table
that pre-computes partial results.

The testbed generated a sequence of 10000 int pairs, computing the gcd
of a pair of ints and adding the sum of all (as checksum and to avoid
removal by the compiler). This was repeated 100 times using the same
sequence. Time is per gcd call and given in nanoseconds.

First column: dmd -O -release -inline
Second column: gdc -O3

SimpleRecursive:        0.096 0.086
SimpleIterative:        0.090 0.083
BinaryRecursive:        0.240 0.213
BinaryIterative:        0.141 0.133
BoostIterative:         0.087 0.085
BoostBinary:            0.219 0.177
gcdSteinTable!(int, 1): 0.161 0.136
gcdSteinTable!(int, 2): 0.133 0.130
gcdSteinTable!(int, 3): 0.107 0.108
gcdSteinTable!(int, 4): 0.093 0.094
gcdSteinTable!(int, 5): 0.089 0.088
gcdSteinTable!(int, 6): 0.087 0.083
gcdSteinTable!(int, 7): 0.086 0.081
gcdSteinTable!(int, 8): 0.085 0.081
gcdSteinTable!(int, 9): 0.085 0.082
gcdSteinTable!(int,10): 0.085 0.080
gcdSteinTable!(int,11): 0.086 0.082
gcdSteinTable!(int,12): 0.086 0.080

Remark: The 2nd template parameter of the gcdSteinTable implementation
means the number of bits for the lookup-table. It therefore uses 2^bits
bytes of memory!

1. Are there any further suggestions on the implementations / Did I
forget something?

2. What do you think, we should finally use?

3. I will also implement the extended gcd (i.e. having gcd(a, b) = z = x
* a + y * b we are interested in x,y,z)

Matthias

[1] http://pastebin.com/sXpsdK5S