A simple sieve in Phobos?

[Chris Williams]

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.