Hacker News new | ask | show | jobs
by bodhiandphysics 597 days ago
no... you can do fibonacci as O(log n)... you cannot represent (1 + sqrt(5))/2 on a computer.
2 comments
Smaug123 597 days ago
You literally just did! The problem is not representing the number, it's computing digits.
link
xyzzyz 596 days ago
You totally can. Here is a O(log n) implementation of the Binet formula with infinite precision:

https://github.com/xyzzyz/FibBinet/blob/master/FibBinet.hs

link