greatest common divisor implementation

[Andrei Alexandrescu]

On 2/14/11 10:38 PM, 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).
> Yeah, so I did tests for long now, too. Unfortunately with gdc I was
> unable to generate uniform long numbers ("UniformIntGenerator.popFront
> not implemented for large ranges"). Interestingly, with DMD it works...
>
> The dmd-only results of long as type, with random long values:
>
> SimpleRecursive!(long):  0.134
> SimpleIterative!(long):  0.127
> BinaryRecursive!(long):  1.727
> BinaryIterative!(long):  0.345
> BoostIterative!(long):   0.136
> BoostBinary!(long):      0.575
> gcdSteinTable!(long, 1): 0.594
> gcdSteinTable!(long, 2): 0.527
> gcdSteinTable!(long, 3): 0.489
> gcdSteinTable!(long, 4): 0.536
> gcdSteinTable!(long, 5): 0.489
> gcdSteinTable!(long, 6): 0.531
> gcdSteinTable!(long, 7): 0.498
> gcdSteinTable!(long, 8): 0.542
> gcdSteinTable!(long, 9): 0.491
> gcdSteinTable!(long,10): 0.539
> gcdSteinTable!(long,11): 0.494
> gcdSteinTable!(long,12): 0.538
>
> The results for dmd and gdc with long as type, but random int values:
>
> SimpleRecursive!(long):  0.110 0.143
> SimpleIterative!(long):  0.100 0.136
> BinaryRecursive!(long):  0.661 0.208
> BinaryIterative!(long):  0.166 0.133
> BoostIterative!(long):   0.104 0.142
> BoostBinary!(long):      0.277 0.174
> gcdSteinTable!(long, 1): 0.275 0.134
> gcdSteinTable!(long, 2): 0.259 0.130
> gcdSteinTable!(long, 3): 0.249 0.108
> gcdSteinTable!(long, 4): 0.253 0.095
> gcdSteinTable!(long, 5): 0.243 0.089
> gcdSteinTable!(long, 6): 0.243 0.086
> gcdSteinTable!(long, 7): 0.245 0.084
> gcdSteinTable!(long, 8): 0.245 0.082
> gcdSteinTable!(long, 9): 0.246 0.081
> gcdSteinTable!(long,10): 0.245 0.081
> gcdSteinTable!(long,11): 0.246 0.080
> gcdSteinTable!(long,12): 0.250 0.081
>
>
>
>>> 2. What do you think, we should finally use?
>> It seems more complex algorithms don't pay much for int values.
> I agree on that and suggest to take Boost's implementation which is very
> readable, too.
>
> I will probably do some tests with BigInt, too. But I suspect that the
> result looks totally different which means that we'll use different
> specializations. The same holds true for the extended algorithm.
>
> @Andrei: As soon as I'm done, I'll submit a pull request to github.
>
> Matthias

Sounds great. Thanks!

Andrei