3 ms·

No, the iterative approach is only marginally less terrible. If, for some strange reason, you actually need a Fibonacci function that's efficient, you have two

No, the iterative approach is only marginally less terrible. If, for some strange reason, you actually need a Fibonacci function that's efficient, you have two choices, depending on the return type: Are you returning a machine integer (long or otherwise)? Precompute them and use a freaking lookup table. The sequence grows so fast you'll never see more than maybe 60 or so terms. Are you returning an arbitrary-size bignum? Use the closed-form solution based on powers of the golden ratio. It still runs in non-constant time (bignum math isn't free), but will run much faster than pointlessly enumerating the sequence up to that point. Of course, I would be surprised if anyone asking about Fibonacci numbers in an interview has ever been looking for one of those answers. Usually it's a "FizzBuzz for recursion" question.

gjm11 17y ago
I have asked a candidate about Fibonacci numbers in interview. We discussed a number of different implementations, the possibility of memoization, the practical differences between machine integers, machine floating-point, and bignums, etc. Incidentally, if you want arbitrary-sized bignum results as quickly as possible, you might do better with a "matrix-squaring" approach (equivalently: use the recurrences that give you F(2k) and F(2k-1) in terms of F(k) and F(k-1)) so that you stick with integer arithmetic. If your bignum library isn't clever about multiplication, I suspect that the simple iterative solution is about as fast as anything else, but most bignum libraries have at least Karatsuba multiplication.
- camccann 17y ago
  Well, iterative (and smart tail recursive [0]) solutions are going to be roughly O(n) for the nth Fibonacci number, assuming addition is O(1). In bignum territory, addition isn't free, but is still pretty cheap. The closed form solution involves computing something raised to the power of n, so would be O(log n) assuming nonintegral multiplication is O(1), which is... not so much the case. Given that the (sqrt 5) factors will always be eliminated by the end you can manipulate things to work with only integers, at the expense of complicating the algorithm. The matrix-based solution, which I had forgotten, is also of the form x^n, so is probably isomorphic to a sufficiently clever handling of Binet's formula that completely avoids the (sqrt 5) terms. So, yes, good call, the matrix approach is better--you win this round. [0] The naive un-memoized recursive algorithm, such as the recursive solution in the linked article, is not only not tail-recursive, but manages to have time complexity of precisely O(fib(n)). If that doesn't make you die a little inside, you're made of sterner stuff than I.
  - gjm11 17y ago
    With a dumb bignum library addition will be O(d) and multiplication will be O(d^2), d being the number of digits; d increases linearly with index, so to compute the n'th Fibonacci number by naive iteration will be O(d^2), whereas doing it by repeated squaring will involve (ignoring lots of constant factors) one size-n multiply, one size-n/2 multiply, one size-n/4 multiply, etc., so also O(d^2). So, same order of magnitude, but it seems quite possible that the constant factor will be worse. And yes, the naive recursive approach is a total disaster. Pretty code, though, and if you have language or library support for memoization you can just write the naive recursive function and demand that it be memoized.
dmv 17y ago
No, they are probably not looking for that answer - but failure to accept them (with working code) would be a negative corporate indicator. An interviewer shouldn't look for answers like that because it requires some amount of fibonacci domain knowledge, which, unless the company specifically works with fibonacci (or similar math), would be a pretty odd filter criteria for programmer quality.

gjm11 17y ago

I have asked a candidate about Fibonacci numbers in interview. We discussed a number of different implementations, the possibility of memoization, the practical differences between machine integers, machine floating-point, and bignums, etc. Incidentally, if you want arbitrary-sized bignum results as quickly as possible, you might do better with a "matrix-squaring" approach (equivalently: use the recurrences that give you F(2k) and F(2k-1) in terms of F(k) and F(k-1)) so that you stick with integer arithmetic. If your bignum library isn't clever about multiplication, I suspect that the simple iterative solution is about as fast as anything else, but most bignum libraries have at least Karatsuba multiplication.

camccann 17y ago
Well, iterative (and smart tail recursive [0]) solutions are going to be roughly O(n) for the nth Fibonacci number, assuming addition is O(1). In bignum territory, addition isn't free, but is still pretty cheap. The closed form solution involves computing something raised to the power of n, so would be O(log n) assuming nonintegral multiplication is O(1), which is... not so much the case. Given that the (sqrt 5) factors will always be eliminated by the end you can manipulate things to work with only integers, at the expense of complicating the algorithm. The matrix-based solution, which I had forgotten, is also of the form x^n, so is probably isomorphic to a sufficiently clever handling of Binet's formula that completely avoids the (sqrt 5) terms. So, yes, good call, the matrix approach is better--you win this round. [0] The naive un-memoized recursive algorithm, such as the recursive solution in the linked article, is not only not tail-recursive, but manages to have time complexity of precisely O(fib(n)). If that doesn't make you die a little inside, you're made of sterner stuff than I.
- gjm11 17y ago
  With a dumb bignum library addition will be O(d) and multiplication will be O(d^2), d being the number of digits; d increases linearly with index, so to compute the n'th Fibonacci number by naive iteration will be O(d^2), whereas doing it by repeated squaring will involve (ignoring lots of constant factors) one size-n multiply, one size-n/2 multiply, one size-n/4 multiply, etc., so also O(d^2). So, same order of magnitude, but it seems quite possible that the constant factor will be worse. And yes, the naive recursive approach is a total disaster. Pretty code, though, and if you have language or library support for memoization you can just write the naive recursive function and demand that it be memoized.

dmv 17y ago

No, they are probably not looking for that answer - but failure to accept them (with working code) would be a negative corporate indicator. An interviewer shouldn't look for answers like that because it requires some amount of fibonacci domain knowledge, which, unless the company specifically works with fibonacci (or similar math), would be a pretty odd filter criteria for programmer quality.