By how much times is Euclid algorithms faster than consecutive integer checking algorithm while finding the GDC of two numbers?

Given integers 0 < a <= b, consecutive integer checking requires sqrt(a) steps to find all the possible factors of a, and test if they are also factors of b. Each step requires two divisions.

Each step in Euclid's Algorithm converts g(a,b) into g(b-n*a, a), where n>1 is an integer such that 0 <= b-n*a < a. The worst case is when n is equal to 1 each time, giving the least reduction in size of the new value for a. The new a,b values are b-a,a and you end up with a Fibonacci-type sequence working backwards down to 0. The limiting ratio of terms in any positive Fibonacci sequence (with any two starting values) is the golden ratio phi. The number of steps is approximately ln(a)/ln(phi) for large values of a,b. Since 1/ln(phi) is about 2 and there is only one division per Euclid step compared to two for sequential, the performance ratio is approximately:

(sequential time)/(Euclid time) ~~ sqrt(a)/ln(a)

GCD (greatest common denominator)

Euclid algorithms involving GCD...