OpenEuphoria

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