3 ms·
def fib(n): return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1) Looks like there's a small bug in this code. fib(0) = 0 fib(1) = 1
by monochromatic 11y ago
def fib(n):
return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)
Looks like there's a small bug in this code.
fib(0) = 0
fib(1) = 1
fib(2) = 2
fib(3) = 3
fib(4) = 5
etc.
But there should be two values at the beginning that evaluate to 1. (Whether it's fib(0) and fib(1), vs. fib(1) and fib(2) is just a matter of convention. But there should definitely be two of them.)
- dsp1234 11y agoA couple of commenters have mentioned this, but with his definition of fib that's given right below in the 'overview' section, the function works: Fib(0) = 1 Fib(1) = 1 Fib(n) = Fib(n−1) + Fib(n−2) So n has a constraint of n > 1, for which the function works.