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