[Issue 7102] std.numeric.gcd with BigInts too

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=7102


Don <clugdbug at yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |clugdbug at yahoo.com.au


--- Comment #1 from Don <clugdbug at yahoo.com.au> 2011-12-13 08:34:07 PST ---
There are a few interesting issues here:

Firstly, GCD for bigints is an important primitive operation, but it's very
complicated (the sub-quadratic algorithms are highly non-trivial). It's
completely different to algorithms used for built-in types (where the cost of
arithmetic is independent of the magnitude of the integer). So it can't
sensibly be made generic.

Secondly, Euclid's algorithm is always inferior to the binary GCD algorithm,
whenever the latter applies. The generic version should be using binary GCD.

Finally, it's Euclid's algorithm, not Eulers!

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------