« Cell Counting 1: COUNTIF | Main | Auto Filling Cells »
September 09, 2004
A simple recursive macro: GCD
In mathematics, the greatest common divisor (abbreviated GCD), or highest common factor (HCF) of two integers which are not both zero is the largest integer that divides both numbers.
The GCD of a and b is often written as gcd(a,b) or simply (a,b). For example, gcd(12,18) = 6, gcd(-4,14) = 2 and gcd(5,0) = 5. Two numbers are called coprime or relatively prime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.
The greatest common divisor is useful for writing fractions in lowest terms.
The algorithm for determining the GCD of two numbers is known as a recursive algorithm - and the OpenOffice Basic code is listed below..
Function gcd(a As Integer, b As Integer) As Integer
If b = 0 Then
gcd = a
Else
gcd = gcd(b,a)
End If
End Function
Posted by Dave at September 9, 2004 05:42 AM
Comments
Hi, the code won't work! Since if (b != 0) it just calls gcd() with a and b swapped it will go into an infinite loop. Or am I missing something?
Richard.
Posted by: Richard Day at November 29, 2004 06:29 PM
gcd = gcd(b,a mod b)
Posted by: Annesh at May 3, 2005 06:33 AM