Results Of The Fibonacci Challenge Are In

Another bunch of good replies to my challenge of yesterday. And again, a bunch of answers that I didn't expect, and some of the points that I was thinking of weren't mentioned.

People seem to like this more conversational format; I'll probably use it more in the future.

Three readers had conjectures as to the running time of fib_1, the recursive algorithm. Deriving the asymptotic order is pretty straightforward. There must be some function f(n) such that fib_1 is O(f(n)). Well, what are the costs? It's trivially true that fib_1(1) is O(1), and so is fib_1(2). Let's therefore say that f(1) = 1 and f(2) = 1.

What's the cost of the algorithm for large n? Well, there's a constant bit at the beginning with the comparison, and a constant cost in the addition, but we can neglect those. The real work is done in the recursion. Clearly O(f(n)) = O(f(n-2)) + O(f(n-1))

That looks familiar! Apparently f(n) = fib(n), so fib_1 is O(fib(n)).

We’ve established the truth of Frederik Slijkerman's comment that recursive fib has a running time proportional to the size of its output. Steven Bone conjectured that recursive fib was O(2ⁿ). He was also right -- almost. How is that possible?

The definition of the Fibonacci numbers that I gave is called a "recurrence relation". Let me define two more recurrences:

s(1) = s(2) = 1, s(n) = s(n-2) + s(n-2)
f(1) = f(2) = 1, f(n) = f(n-2) + f(n-1)
b(1) = b(2) = 1, b(n) = b(n-1) + b(n-1)

You agree that it is clear that s(n) <= f(n) <= b(n), right? The first sequence is 1, 1, 2, 2, 4, 4, 8, 8, 16, 16...  which grows at O(SQRT(2)ⁿ). The second sequence is 1, 1, 2, 4, 8, 16, 32, ...  which clearly grows at O(2ⁿ).  f is sandwiched between two functions that grow at O(somethingⁿ) so it must also be O(somethingⁿ)! 

The exact constant doesn't really matter for our purposes. It's actually about O(1.6ⁿ). Yes, I'm handwaving here. A more precise definition of order notation would make it clear when two functions are asymptotically equivalent, but that's a subject for another day. There are different notations for functions with asymptotic upper, lower, and strict approximations, but I don't want to get into that now. The point is that this thing grows way faster than any polynomial in the long run and, more important, grows extremely quickly even in the short run.

Clearly fib_1 consumes O(n) memory off the stack. Equally clearly,  fib_2 is O(n) and consumes O(1) memory. I hinted that there was an O(1) solution. Indeed there is, provided that we more carefully define the problem. Before I get to it, I mentioned that I often ask about robustness in interviews. 

Clearly it's a good idea to make sure that n is one or larger; fib_2 goes into an infinite loop if it isn't. But that's certainly not all! What's the actual vs. desired output of

fib_2();
fib_2(1, 2, 3)
fib_2("2B||!2B");
fib_2("hello, world!");
fib_2(null);
fib_2(3.14159);
fib_2(new Date());

and so on? None of those make much sense and some of them go into infinite loops. Remember, JScript isn't C++ in fancy dress. It's not a statically typed language, so if you have type restrictions, you're going to have to write a bunch of runtime code, or use a different language.

Furthermore, clearly there is a sensible lower bound of one. Is there a sensible upper bound? I note that

fib_2(77) --> 5527939700884757
fib_2(78) --> 8944394323791464
fib_2(79) --> 14472334024676220

How do we add together a number ending in 7 and a number ending in 4 and end up with an even number? We've run out of precision. A floating point number only has 53 bits of precision; as soon as the value exceeds 2⁵³, we start dropping bits off the end and therefore start returning incorrect results. I asked for a function that produced the nth Fibonacci number, not one that produced a close approximation of it! That's a point which a good interview candidate would clarify. 

Assuming that we really do need exact numbers, and assuming further that the caller is willing to accept the limitations on precision that an IEEE float imposes, this method only has 78 sensible inputs -- the first 78 positive integers. Therefore it only has 78 possible outputs. When I hear that a method only has 78 outputs and the inputs are integers, I like table driven solutions. (If we were using some other language that had 64 bit or 32 bit integers, the limits would be different, but they'd still be small enough to make a table-driven solution feasible.)

var fibarr = new Array(null, 1, 1, 2, 3, 5, /*[...]*/, 8944394323791464);
function fib_3(n)
{
  // [appropriate checking here.]
  return fibarr[n];
}

That's certainly O(1).

If those aren't sensible restrictions, then we have waaaaay more work to do. We need to figure out what the restrictions are, then write a numeric computation library that handles numbers up to the precision we need, and so on. That introduces a whole other set of costs which we'd have to analyze on a case by case basis. If we really did have to handle arbitrarily big numbers then a well-implemented algorithm would probably end up being O(log n). Several people mentioned Binet's Formula, which we could use. However, the mathematics of all that is more than I want to tackle in today's blog entry; I have work to do.

If the caller really, really wanted this to be as fast as possible in raw speed terms, not algorithmic complexity terms, then we have to start talking about what we can change. Language? Seems to me that a C++ or assembly language implementation is going to be faster all around. What hardware are we stuck with? How big is the processor cache? Will the table fit into it? Can we hint to the compiler that the table is read-only after it is constructed and eke out more speed somehow? What are these numbers being used for anyway, and how do we know that this method is even the bottleneck?

Finally, Dan Shappir mentioned tail recursion and lazy evaluation using a zipper function on an infinite list. That's quite coincidental; a couple days ago coworker of mine showed me a problem from an old ACM contest he'd been working on for fun. The problem was to implement a particular subset of Haskell's infinite list and zipper function capabilities. Which got me thinking that there are lots of interesting programming ideas that I could blog about. Perhaps I'll take up some of that stuff in the coming weeks.

Comments

• Anonymous
  May 24, 2004
  > That's certainly O(1)
  
  Sorry, this doesn't apply. The question was about the asymptotic order of calculating fibonacci number. Taking the number from an array does not calculate it.

• Anonymous
  May 24, 2004
  First off, please point out the sentence in which I stated that the problem was "calculate the nth fibonacci number". I can't find such a sentence. I said that I wanted an algorithm that produced the nth Fibonacci number.
  
  Second, your objection is based on a semantic quibble. Tell you what, I'll modify the algorithm:
  
  var fibarr = new Array(null, 0, 0, 1, 2, 4, /[...]/, 8944394323791463);
  function fib_3(n)
  {
  // [appropriate checking here.]
  return fibarr[n] + 1;
  }
  
  OK, now it calculates the nth fib number, and its still O(1). Happy now? :-)
  
  Here's a question for you: True or false: the planet Saturn is a device which computes the orbit of the planet Saturn.
  
  You've got to admit that Saturn does an admirable, 100% accurate job of computing the orbit of Saturn. Want to know where Saturn is in its orbit? Go to Saturn, and there it is! Want to know where it will be in a year? Follow Saturn around for a year, and Saturn will give you the answer.
  
  And yet that seems unsatisfying somehow. You need to carefully define the word "calculate" if you want to have this conversation.

• Anonymous
  May 24, 2004
  This topic was too old for me to reply to it in the original thread... The discussion below neglects the fact that the JScript engine has a limited call stack... recursion dies when the stack is only 467 levels deep - a fact which once prompted me to rewrite the easy to implement recursive solution with an iterative one :P
  
  # re: The Stygian Depths Of Hacked-Together Scripts 5/13/2004 6:50 PM Eric Lippert
  Good point. For a list which mostly consists of unique words, this solution makes two entire in-memory copies of most of the data in the list. If the data are large and not copied by reference, that could be quite expensive.
  
  Quicksort on the other hand only consumes memory in the form of stack frames, and each stack frame is of a constant size, and in the typical case there will be O(log n) stack frames max in use at any time. (The standard quicksort algorithm suffers from a n-squared worst case in rare cases, but getting into those details would take us far afield.)
  
  There are other aspects that I've neglected in this analysis. (Hint: think about what I said above; what if the data are large?)
  

• Anonymous
  September 06, 2007
  I’ve mentioned recursive programming techniques several times over the years in this blog ( Topological

• Anonymous
  October 10, 2007
  Back in May we were discussing the merits and drawbacks of recursive programming techniques -- that is,