math:gcd is incorrect
- Posted by bill May 07, 2012
- 1904 views
The manual:
62.7.7 GCD
include std/math.e
namespace math
public function gcd (atom p, atom q)
Returns the greater common divisor of to atoms
Parameters:
p : one of the atoms to consider
q : the other atom.
Returns:
A positive atom, without a fractional part, evenly dividing both
parameters, and is the greatest value with those properties.
Comments:
Signs are ignored. Atoms are rounded down to integers.
Any zero parameter causes 0 to be returned.
....
Evidence:
include std/math.e ? gcd(0, 48) returns 0
This is simply wrong.
GCD (0, 48) = 48
1. By definition a greatest common divisor could not be 0.
Division by 0 is undefined (and 1/0 != INF).
2. 0 is divisible by 48.
Pseudocode GCD (from Knuth pp.319-20)
quoted in Wikipedia article on GCD algorithm
function gcd(a, b) while b != 0 t := b b := a mod b a := t return a
Note: formally gcd(0, 0) is undefined and should be an
error just as much as division by zero is an error.
Theorem 2.1 Given any two integers a and b, not both zero,
there is a unique integer d, called their greatest common
divisor, with these properties: 1: d | a and d | b;
2: if d1 | a and d1 | b then d1 | d;
3: d > 0.
WJ Leveque Fundamentals of Number Theory p.31