Algorithmic Efficiency
The computational efficiency of Euclid's algorithm has been studied thoroughly. This efficiency can be described by the number of steps the algorithm requires, multiplied by the computational expense of each step. As shown first by Gabriel Lamé in 1844, the number of steps required for completion is never more than five times the number h of digits (base 10) of the smaller number b. Since the computational expense of each step is also typically of order h, the overall expense grows like h2.
Read more about this topic: Euclidean Algorithm
Famous quotes containing the word efficiency:
“Nothing comes to pass in nature, which can be set down to a flaw therein; for nature is always the same and everywhere one and the same in her efficiency and power of action; that is, nature’s laws and ordinances whereby all things come to pass and change from one form to another, are everywhere and always; so that there should be one and the same method of understanding the nature of all things whatsoever, namely, through nature’s universal laws and rules.”
—Baruch (Benedict)