download GCD program
download Delphi-7 GCD project
This article describes a recursive GCD (Greatest Common Divisor) algorithm.
It is based on Euclid's theorem which simply amounts to:
GCD(60,45) = GCD(15,45) = GCD(45,15) = GCD(15,15) = GCD(0,15) = 15.
60 mod 45 = 15, GCD(60,45) = GCD(15,45) = GCD(45,15)
45 mod 15 = 0, GCD(45,15) = GCD(0,15) = 15.
Recursive procedures or functions may call themselve.
This allows for compact coding at the price of difficulty to understand.
An approach is to visualize such a procedure many times, see picture below:
Here is the function:
function GCD(a,b : Int64) : Int64; //b <> 0 begin if a = 0 then result := b else if a < b then result := GCD(b,a) else result := GCD(a mod b,b); end;That's all !
The program allows for GCD calculations of number up to 12 digits. For details please refer to the source code.