Search code examples
algorithmgreatest-common-divisor

Whether or not there is an algorithm faster than Euclid for finding GCD

Is there any algorithm faster than Euclid's algorithm for finding if gcd of two numbers is one?

Solution

  • The Binary GCD algorithm tends to outperform the Euclidean algorithm. The idea is to replace division by subtraction and use

    gcd(a,b) = gcd(a, b-a)

    and that if a is odd, and b is even, then 

    gcd(a,b) = gcd(a,b/2)

    which can be implemented as a simple bit operation.

    If you are looking for something even faster, there are algorithms here and here that manage to run the binary algorithm in parallel.