Gabriele Biondo

The Euclidean Algorithm

Here: Complexity of Euclidean Algorithm we prove that if \(a,b\in\mathbb{Z},a>b>0\), then the number of steps in the Euclidean algorithm is about \(\log_{10}\left(b\right)/\log_{10}\left(\Phi\right)\); which is at most five times the number of decimal digits of \(b\).

There are more efficient algorithms to find the greatest common divisor between two numbers, indeed. This is nothing but a starting point.


Leave a Reply

Your email address will not be published. Required fields are marked *