Re:Recursive fibonacci benchmark using top languages on GitHub
by braythwayt on Friday September 28, 2018 @06:38AM
(#18092308)
As mentioned in other comments, working with floating point numbers in practice is trickier than it looks in theory:
Re:Recursive fibonacci benchmark using top languages on GitHub
by edflsafoiewq on Friday September 28, 2018 @06:01AM
(#18092171)
You can't really compute it in constant time since the number of bits in the nth Fibonacci number is O(n), so you need to take at least that long just to write the result out.
Computing with Binet's formula is also rather tricky. You just need to round φ^n/√5, but how many bits of √5 do you need to use?
https://artofproblemsolving.com/wiki/index.php?title=Binet%2...