search

WebDrake / Rational

std.rational Phobos candidate module
2 stars 0 forks source link

Greatest common factor/divisor #2

Open WebDrake opened 11 years ago

WebDrake commented 11 years ago

std.rational currently implements its own custom gcf (greatest common factor) function, probably in order to ensure it can handle both std.bigint.BigInt integers and other possible "big integer" implementations.

The existing gcf is buggy as it cannot handle gcf(0, n) or gcf(n, 0) as input, failing with a divide-by-zero error: when calculating the remainder in Euclid's Algorithm, it does not take into account the possibility that one or other of the numbers may be 0, and so ends up calculating n % 0.

The optimal solution here is probably to improve Phobos' existing gcd such that it can handle any conceivable BigInt implementation. In the process it may be worthwhile to also implement the superior binary GCD algorithm.

See also:

WebDrake commented 11 years ago

https://github.com/WebDrake/Rational/commit/6667c835af896325ccd588c3f87f9c188f359b2e fixes the bug; now the remaining question is how to integrate gcf with Phobos.