| Popis: |
The Euclidean algorithm has been analyzed in detail, particularly with regard to the number of steps needed. In 1845 Lame proved that if the Euclidean algorithm for (a,b) with a > b > 0 requires exactly n divisions and the number a is minimal, then a = F n + 2 and b = F n+1. [4] This result can claim to be the first practical application of the Fibonacci numbers [3] and the first algorithm whose worst-case running time was precisely determined. [4] In turn this implies that for any pair (a,b) where 0 < b < a < N, the number of divisions is at most \( \left\lceil {\log \phi (\sqrt 5 N)} \right\rceil - 2 \) where \( \phi = (1 + \sqrt 5 )/2 \) . Much more difficult to show is that the average number of divisions when b = N is approximately ((12 ln 2)/π2) In N. [1] [6] [7] |
