1
$\begingroup$

I read the Euclidean algorithm of Wikipedia page(https://en.wikipedia.org/wiki/Euclidean_algorithm), but I was stuck at worst-case proof. At the second paragraph, it says:

For if the algorithm requires $N$ steps, then b is greater than or equal to $F_{N+1}$ which in turn is greater than or equal to $φ^{N−1}$, where $φ$ is the golden ratio. Since $b ≥ φ^{N−1}$, then $N−1 ≤ log_φb$. Since $log_{10}φ > 1/5$, $(N − 1)/5 < log_{10}φ×log_φb = log_{10}b$. Thus, $N ≤ 5×log_{10}b$. Thus, the Euclidean algorithm always needs less than $O(h)$ divisions, where $h$ is the number of digits in the smaller number $b$.

I just can't understand why $b≥φ^{N−1}$? Is it because $F_{N+1}≥φ^{N−1}$? how to prove relation between Fibonacci number $F_{N+1}$ and the golden ratio $φ^{N−1}$?

$\endgroup$
3
  • 1
    $\begingroup$ I will urge you to calculate the golden ratio from the Fibonacci sequence,which is the ratio of two consecutive terms when n is very large. You will get a beautiful construction in the book Structure and interpretation of computer programs. The pdf is freely available. $\endgroup$ – Bhaswat Jun 28 '20 at 16:56
  • $\begingroup$ The max number of iterations is the ordinality of the first Fibonacci number greater than the larger number of the "pair" put into Euclid's algorithm. For example, for $(1000,123)$, the $15^{th}$ Fibonacci number is $1597$ so the max iterations is $15$. The actual number is $5$ for $(1000,123)$ but $6$ for $(123,1000)$. $\endgroup$ – poetasis Aug 6 '20 at 17:06
  • $\begingroup$ For another problem, I programmatically verified that the worst case number of iterations of Euclid's algorithm is the ordinal number $N$ of the Fibonacci number just greater than the smallest of the two number for which GCD is sought. However, if the larger number is places second, it will require one more step sooo.... is appears that the second number is what determines N. $\endgroup$ – poetasis Sep 26 '20 at 2:04
2
$\begingroup$

A don't follow your notations, but I guess what you really want to show is that $$F_{N}\ge \varphi^{N-2}$$ where $\varphi$ is the golden ratio. Since $\varphi^2=\varphi+1$, one can show easily by induction on $N$ that $$\varphi^N=F_N\varphi+F_{N-1}$$ Hence $$\varphi^N=F_N\varphi+F_{N-1}\le F_N\varphi+F_{N}=F_N(\varphi+1)=F_N\varphi^2$$ so you get the result.

$\endgroup$
1
  • $\begingroup$ thanks for ur answers! $\endgroup$ – brushmonk Jun 29 '20 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.