5 ms·
I like this one as well: Fibonacci(n) = (Φ^n - (1-Φ)^n) / √5 (Where Φ = (1 + √5) / 2)
by alain_gilbert 11y ago
I like this one as well:
Fibonacci(n) = (Φ^n - (1-Φ)^n) / √5
(Where Φ = (1 + √5) / 2)
- 0xmohit 10y agoThis formula is attributed to Binet (1843). See https://math.temple.edu/~reich/Fib/fibo.html https://math.temple.edu/~reich/Fib/fibo.html for more on the Fibonacci sequence and the golden mean.
- tanderson92 10y agoMathematically they might be the same, but they reduce to different problems in computer science. The OP uses algorithmic approaches, but yours requires finite-precision root solvers (for the calculation of \Phi ) and some numerical analysis to determine how many bits of \sqrt(5) are needed to be correct to yield a calculation of Fibonacci(n) which is correct to the nearest integer.
- panic 10y agoYou don't need to use a root solver. If you represent numbers as "a + b sqrt(5)" you can do algebra directly in that space.
- tanderson92 10y agoI take it you are making a joke? Heh. Otherwise, I'd point out that any result where you ultimately need to use Fibonacci(n) as an actual integer, you can't represent it as an algebraic combination of "sqrt(5)".
- panic 10y agoNo joke! See this thread: https://news.ycombinator.com/item?id=11561336 https://news.ycombinator.com/item?id=11561336 for some real-life implementations of this technique. Since the Fibonacci numbers are integers, at the end of your computation you'll get a number like "a + 0 sqrt(5)". Then you can just take the "a" part.
- tanderson92 10y agoAh! I see what you're saying. Thank for the link, that is a clever approach.
- thomasahle 10y agoWhen computing, you can ignore the second term, and just round the result to nearest integer. At for n larger than 2, or so, that should simplify calculations.