How can I find the max number of times the Euclidean Algorithm must be executed for a given starting remainder?

Question

If each step of the Euclidean Algorithm reduces the remainder by at least 50%, how can I calculate the max number of steps it will take to find the greatest common denominator? If the initial remainder of two numbers is 1000, would log2(m) give me this value? If r ≤ m/2 for each step of the Euclidean Algorithm, could I just find m assuming that r = 1000 in the max case and substitute m in the previous logarithm to find the max number of steps?

Answer 1

A brute force run shows that the maximum number of iterations is indicated by the ordinality of the first Fibonacci number greater than the larger number of the pair subjected to Euclid's Algorithm. For example, for the numbers $(1000,x)$, the next Fibonacci number is $1597$ and it is the $15^{th}$ or $16^{th}$ Fibonacci number depending on where you begin the series, so the maximum number of iterations is $15$ or $16$ assuming $x$ is smaller than $1000$.

(Note: If the larger number is entered second, the iteration count is one higher.) Here is a sample run in which the "count" and GCD numbers are displayed only when the current iteration count for a pair is greater than the previous "largest count". It took $\approx 3.2$ hours of CPU time using interpretive BASIC. I'm sure it would take less time with math-specific languages.

 enter limit? 100000
 iterations( 1 )    GCD( 2 , 1 ) = 1 
 iterations( 2 )    GCD( 3 , 2 ) = 1 
 iterations( 3 )    GCD( 5 , 3 ) = 1 
 iterations( 4 )    GCD( 8 , 5 ) = 1 
 iterations( 5 )    GCD( 13 , 8 ) = 1 
 iterations( 6 )    GCD( 21 , 13 ) = 1 
 iterations( 7 )    GCD( 34 , 21 ) = 1 
 iterations( 8 )    GCD( 55 , 34 ) = 1 
 iterations( 9 )    GCD( 89 , 55 ) = 1 
 iterations( 10 )   GCD( 144 , 89 ) = 1 
 iterations( 11 )   GCD( 233 , 144 ) = 1 
 iterations( 12 )   GCD( 377 , 233 ) = 1 
 iterations( 13 )   GCD( 610 , 377 ) = 1 
 iterations( 14 )   GCD( 987 , 610 ) = 1 
 iterations( 15 )   GCD( 1597 , 987 ) = 1 
 iterations( 16 )   GCD( 2584 , 1597 ) = 1 
 iterations( 17 )   GCD( 4181 , 2584 ) = 1 
 iterations( 18 )   GCD( 6765 , 4181 ) = 1 
 iterations( 19 )   GCD( 10946 , 6765 ) = 1 
 iterations( 20 )   GCD( 17711 , 10946 ) = 1 
 iterations( 21 )   GCD( 28657 , 17711 ) = 1 
 iterations( 22 )   GCD( 46368 , 28657 ) = 1 
 iterations( 23 )   GCD( 75025 , 46368 ) = 1 

BASIC is considered unsophisticated these days but it is free and easier to learn that PYTHON and others. Here is the program that ran the test above.

  100 print "enter limit";
  110 input l1
  120 c9 = 0
  130 for i1 = 1 to l1
  140    for i2 = 1 to i1-1
  150 c1 = 0
  160 x1 = i1
  170 x2 = i2
  180 r1 = x1 mod x2
  190 c1 = c1+1
  200 if r1 > 0
  210    x1 = x2
  220    x2 = r1
  230 goto 180
  240 endif
  250 if c1 > c9
  260    c9 = c1
  270    print "iterations( " c1 ")  ",;
  280    print "GCD( " i1 ", " i2 ") = " x2
  290 endif
  300   next i2
  310 next i1