(1) The whole point of that "O(1) algorithm" is that the n'th Fibonacci number has asymptotic size:
F[n] ~= phi ** n / sqrt(5)
But this means that it requires O(n) memory to store, which means that it is impossible to get an algorithm which scales better than O(n), asymptotically. You might be able to get better than O(n²); I don't know much about arbtitrary-precision exponentiation algorithms.
(2) This is one of those nasty cases where CS folks are loose with the meaning of big-O, anyway. Strictly speaking the input size for the Turing machine scales like O(log n), and so the Fibonacci algorithms should probably be said to have exponential complexity, even though it's a linear recurrence relation. It depends how loose you are with what the 'n' means in O(n).
My apologies. You make a good point, and this is one of those cases where CS folks are loose with the meaning of big-O.
I still might be confused, but AFAICT, the OP's solution and computation by rounding both require O( (log n) * M(log n) ) time, where M(n) is the time it takes to multiply an n-bit number.
def fib_binet(n)
a = (1+Math.sqrt(5))**n
b = (1-Math.sqrt(5))**n
c = (2**n)*Math.sqrt(5)
return ((a-b)/c).truncate()
end
def fib2(n)
a = Math.sqrt(5)
return ((1/a)*(((1+a)/2)**n)).round()
end
(0..20).each do | i |
puts fib_binet(i)
puts fib2(i)
end
1) You don't really need the (b) term. (1 - \phi) is on the order of .5, so if you round the result of ((a - b) / c) instead of truncating it, you can ignore that term.
2) How long are your floating point numbers? You code works for n up to 71, but no further. The linked example works for any n.
Every time Fibonacci is discussed, someone brings up the Binet formula. If I'm interviewing for a position that requires any sort of numeric coding, this is a reason not to hire -- it demonstrates you don't know the first things about floating point.
Expanding on my original answer to Huggah, either this answer or a naïve recursive answer are fine if the purpose of the question is a “fizz buzz” to demonstrate that someone really can write a trivial piece of code.
If the objective is to generate an interesting conversation, I would go with this, with matrices, with memoization, or anything else that provides an opportunity to share experience.
The only time this one wouldn’t be right is when the interviewer is specifically trying to get you to demonstrate the ability to handle recursion. I don’t have an opinion about that, but there are some people who believe that pointers and recursion are some kind of innate talents that should be verified in the interview process.
Of course, if that’s what they want, they should probably pick a problem that only admits a recursive solution, but when you’re on the other side of the table it requires great tact to debug their interview process.
The short version: it's harder than people often think to do reliably (because you need arbitrary-precision floating-point operations); and, when you do, it turns out to be slower than integer methods.
You could work in the Euclidean domain of integers with sqrt(5) adjoined and avoid floating point completely. The matrix version is actually pretty efficient, and leads to the above if you diagonalize.
Just to expand this for people who aren't familiar with this idea, which has a nice analogue with complex numbers, one can take the number a + b sqrt(5) and represent it as the matrix:
[a, 5b]
[b, a]
This implements the multiplication rule for such numbers as a matrix multiplication. There is a straightforward generalization where you replace 5 with -1 and get complex numbers, which is one of the easiest ways to see that the complex numbers are scaled rotation matrices -- which is the easy way to see that a holomorphic function preserves angles and obeys the Cauchy Riemann equation ∂f/∂y = i ∂f/∂x.
It's very cute mathematics, but it's still not O(1). At the very least, exponentiating to the n requires log(n) matrix multiplications.
I'm late to the party, but a quick and dirty implementation of this in ghci computes the 10,000,000th Fibonacci number for me in about 3 seconds, though it takes a lot longer to print to my terminal. It's pretty neat.
newtype T = T (Rational,Rational) deriving Show
:{
instance Num T where { T (a,b) + T (c,d) = T (a+c,b+d);
T (a,b) * T (c,d) = T (a*c+5*b*d,b*c+a*d);
abs (T (a,b)) = T (a*a+5*b*b,0);
fromInteger n = T(fromInteger n,0);
signum (T (a,_)) = T (signum a,0);
negate (T(a,b)) = T(-a,-b) }
instance Fractional T where { recip (T(a,b)) = T(a/(a^2-5*b^2),-b/(a^2-5*b^2));
fromRational r = T(r,0)}
:}
let r5 = T(0,1)
let phi = (1+r5)/2
let psi = (1-r5)/2
let fromT (T(a,b)) = (a,b)
let fib n = floor . fst . fromT $ (phi^n-psi^n)/r5
let x = fib 10000000
x == 0
Even the page the author links to is doing a great deal too much work!