EUCLID'S ALGORITHM
\jˈuːklɪdz ˈalɡəɹˌɪθəm], \jˈuːklɪdz ˈalɡəɹˌɪθəm], \j_ˈuː_k_l_ɪ_d_z ˈa_l_ɡ_ə_ɹ_ˌɪ_θ_ə_m]\
Sort: Oldest first

(Or "Euclidean Algorithm") An algorithm forfinding the greatest common divisor (GCD) of two numbers.It relies on the identitygcd(a, b) = gcd(ab, b)To find the GCD of two numbers by this algorithm, repeatedlyreplace the larger by subtracting the smaller from it untilthe two numbers are equal. E.g. 132, 168 > 132, 36 > 96, 36> 60, 36 > 24, 36 > 24, 12 > 12, 12 so the GCD of 132 and168 is 12.This algorithm requires only subtraction and comparisonoperations but can take a number of steps proportional to thedifference between the initial numbers (e.g. gcd(1, 1001) willtake 1000 steps).
By Denis Howe