$next$ $up$ $previous$
Next: Computing the greatest common

Analyzing the efficiency of the Euclidean algorithm

David R. Hayes

Computing the greatest common divisor of x and y
The worse case: Fibonacci numbers
Fibonacci numbers and the Golden Ratio
The Euclidean algorithm stops in $\hbox{$O\!\left(\log(N)\right)$}$ steps
About this document ...

David Hayes
2/4/1999