Find The Greatest Common Divisor of Two Integers Using Euclid's Algorithm

Category:
Dates and Math
Type:
Snippets
Difficulty:
Intermediate
Author:
Jay

Version Compatibility:

More information:
This function computes the GCD (Greatest Common Divisor) of any two integers, negative or positive, up to 28 digits long. The method used is based on an ancient algorithm devised by Euclid. Euclid was a Greek geometer of the 3d century b.c., famous for his treatise on geometry. Many of his logical concepts are still being studied and applied in mathematics today. This function is one of those concepts in action.

The GCD is simply the largest positive integer that will perfectly divide any two integer values in common. The signs of the integers are ignored and the GCD is always expressed as a positive value. In integer fractional arithmetic, the GCD may be used to reduce a fraction to its lowest terms by dividing both the numerator and the denominator of the fraction by this GCD. This produces the smallest integer fraction that has the same identical numerical ratio.

More information regarding the function and its usage can be found in the included readme file and the code's comments.


Instructions: Click the link below to download the code. Select 'Save' from the IE popup dialog. Once downloaded, open the .zip file from your local drive using WinZip or a comparable program to view the contents.

Download gcd.zip