Hacker News new | past | comments | ask | show | jobs | submit login

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.



You 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.


I 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)".


No joke! See this thread: 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.


Ah! I see what you're saying. Thank for the link, that is a clever approach.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: