On Wednesday, 19 March 2014 at 01:44:16 UTC, bearophile wrote:
Chris Williams:
Yeah, several methods work just fine if you change their
declaration to isIntegral!T || is(typeof(T) == BigInt). gcd()
is one of them.
Unfortunately, I don't trust rewriting isIntegral, so this
sort of change would need to be on a function-by-function
basis.
Don explained me that a GCD on BigInts should use a more
efficient algorithm.
Bye,
bearophile
There's a couple algorithms on the Wikipedia, but when I profiled
them on some -very large- values, they all had similar
performance times, including the ones that were just a few lines
of simple code. It's possible that there's an optimized variant
somewhere on the greater internet, but that might take some
hunting to track down.
Ultimately, it's probably better to expose functionality in
Phobos, even if they're simple implementations. Eventually, some
enterprising person will find and implement an optimized version,
and in the meantime, everyone has a working, tested version that
they didn't have to write nor validate themselves.
