Apparently, when initialized on $k$-bit integers $A$, $B$, Euclid's algorithm terminates after at most $2k$ iterations. This result is not immediately intuitive to me. I would appreciate help in showing this result. Thanks.
Asked
Active
Viewed 76 times
1
-
Are you familiar with how to get a maximum length of steps in Euclid's algorithm (for greatest common divisor)? – hardmath Feb 19 '16 at 02:21
-
6Have a look at this previous Question, Proving the number of iterations in the Euclidean algorithm, possibly close enough to answer your questions. – hardmath Feb 19 '16 at 02:25
-
I am not familiar with how to get a max length of steps. – velen Feb 19 '16 at 02:28
-
1Hint. Can you show that when you take two steps in the algorithm the bigger number is at most half of what it was? – Ethan Bolker Feb 19 '16 at 02:32