Maths
- This topic has 2 replies, 3 voices, and was last updated 1 week, 2 days ago by .
-
Posts
-
Recently I came across a very interesting fact about the time complexity of Euclidean algorithm about how the number of steps in the algorithm does not exceed 5 times the number of decimal digits in the smaller of the two numbers.
So if the algorithm took N steps, the smallest number b satisfies
b >= F_(n+1) >= φ^(n-1)
Where F_n in the nth Fibonacci number and φ is the golden ratio. I find it fascinating that the golden ratio somehow shows up here in the worst-case complexity of the algorithm finding the gcd of two numbers.Does anyone have any good explanations or reading suggestions that explain how and why φ shows up here?
@Crackerjack_404
You may have solved this by yourself already, but there is a decent covering of this in CLRS (Introduction to Algorithms) in the chapter on Number-theoretic algorithms. I can’t quite tell if you are asking about the derivation of the run-time or the relationship between the Fibonacci numbers and the golden ratio. If the former, then CLRS should give a good presentation. For the latter – I seem to recall you saying you know some linear algebra – try writing the recurrences which define the Fibonacci sequence as a matrix equation. Now try diagonalising the matrix. How does this help you?
@AndGiggles
Thanks! I was actually curious both about the runtime derivation and then Fibonacci/golden ratio link. I’ll check the CLRS chapter for the former. I’ve got Fibonacci sequence as a matrix equation, and computing the eigenvalues then diagonalising does the golden ratio! Quite satisfying to get the closed form expression for Fibonacci!
- You must be logged in to reply to this topic.