3 ms·
Mathematically they might be the same, but they reduce to different problems in computer science. The OP uses algorithmic approaches, but yours requires finite-
by tanderson92 11y ago
Mathematically 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 11y 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 11y 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 11y 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 11y agoAh! I see what you're saying. Thank for the link, that is a clever approach.