6 ms·
no... you can do fibonacci as O(log n)... you cannot represent (1 + sqrt(5))/2 on a computer.
by bodhiandphysics 2y ago
no... you can do fibonacci as O(log n)... you cannot represent (1 + sqrt(5))/2 on a computer.
- Smaug123 2y agoYou literally just did! The problem is not representing the number, it's computing digits.
- xyzzyz 2y agoYou 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 https://github.com/xyzzyz/FibBinet/blob/master/FibBinet.hs