On calculating Fibonacci numbers in C

It's interesting to note that one can get O(lg (n)) complexity of analytical solution without using any floating arithmetic. There are at least two easy ways to do it: one is to recognize the analytical formula as a result of diagonalizing certain linear map, and calculate nth power of that map using repeated squaring instead of diagonalization. In more concrete terms: consider a square matrix A = {{1,1},{1,0}}. To obtain nth Fibonacci number, raise A to the nth power and take lower left entry. Clever multiplication by repeated squaring lets one perform only a logarithmic number of matrix multiplications instead of linear number using naive method.<p>Another way is to interpret analytical formula in Q(sqrt(5)) ring, and implement Q(sqrt(5)) arithmetic using quadruples of integers. More concretely: suppose we have two numbers of the form a+b sqrt(5), c+d sqrt(5), where a,b,c,d are rational. then their sum is (a+c) + (b+d)sqrt(5), and their product is (ac+5bd)+(ad+bc)sqrt(5). Thus, just like we usually represent complex numbers as pairs of real numbers with special multiplication formula, we can represent elements of Q(sqrt(5)) as pairs of rationals with special multiplication formula. then we just use the analytical formula for our special number system. I've implemented it a while ago in Haskell: <a href="https://github.com/xyzzyz/FibBinet" rel="nofollow">https://github.com/xyzzyz/FibBinet</a>

I still don't understand how the author jumped from a cute comparison of Fibonacci algorithms to saying programmers shouldn't learn more math. Math isn't just arithmetic and numbers. He acts as if the recursive solution isn't also math.<p>Developing mathematical maturity is, in my opinion, an excellent way to think more clearly, precisely, and rationally about any problem, even if it doesn't necessarily involve numbers. The author could make the case that <i>number theory</i> in particular isn't directly applicable to many problems (I do have a lot of fun with Project Euler though), but again, math isn't just about numbers. Math teaches you how to reason about the <i>relationships and patterns</i> between <i>objects</i> (which can be numbers, vectors, spaces, groups, rings, etc. In a certain sense, you become more comfortable with higher levels abstraction, and it requires you to be precise and explicit about assumptions.<p>That's jut my two cents. Math education is pretty dismal in the US, but math can be very enjoyable if you find the right textbook, teacher, or even free online class nowadays. Never fear math.<p>EDIT: The author has pointed out that he is making a play on words between "math" and "Math" (the mathematical library). I didn't understand that when I wrote this post.

Re-commenting on OP @ author's request:<p>The article really isn't about speed, it's more that engineers shouldn't necessarily take mathematical results as the end-all to their considerations when developing an algorithm. In particular, what is considered "best" in theory is not necessarily the best choice in a given program.<p>Math is important to formulating algorithms, since it can provide, in theory, a closed form solution for something typically done iteratively (the example here: fibonacci numbers). But you still need to verify when an algorithm is going to be correct, and more importantly, appropriate. In this case, it's pretty well known how inaccurate floats and doubles can be within X significant figures, and this is why I've always said the analytical solution doesn't really work on a computer unless you have a CAS library that can approximate an exact answer to an arbitrary number of significant figures (and it still won't be accurate if shoved into a float/double afterwards). So there's a trade-off, and choosing the theoretically best solution (a closed form solution) isn't necessarily the best possible choice for the task. In this case, yes, as others have pointed out, if we only need the first 96 fibonacci numbers, ever, it makes more sense to pre-compute them. However, if we only do the computation once in the entire program, even that doesn't necessarily make sense. It entirely depends on the application, but that's the entire point: a closed form for fibonacci numbers isn't the end of considerations.<p>I am curious though, why is it so many people are oblivious that there's an O(logN) time algorithm to compute fibonacci numbers iteratively on integers? It's a beautiful piece of math, and very simple so everyone should understand it. Just notice that:<p><pre><code> ((1, 1), (1, 0))^N -&#62; ((f_{N+1}, f_N), (f_N, f_{N-1})) </code></pre> given N &#62; 0, where f_N denotes the Nth fibonacci number. For SW engineers who are actively interviewing: does anyone still ask you to write a function to compute the Nth fibonacci number in technical interviews?

"....since the 96th Fibonacci number is the largest to fit in an unsigned long int"<p>Have to agree with the first person to comment on the article's site. If we are going for speed, just pre-calc the 96 numbers and do an array lookup in the function guarded by and if.

The analytic solution to the Fibonacci sequence is nice and all, but I generally dislike methods that require you to very carefully check how much precision you need. I much prefer the matrix exponentiation by repeated squaring approach [1].<p>1: <a href="http://ronzii.wordpress.com/2011/07/09/using-matrix-exponentiation-to-calculated-nth-fibonacci-number/" rel="nofollow">http://ronzii.wordpress.com/2011/07/09/using-matrix-exponent...</a>

GMP (arbitrary precision library) implements it as a lookup table for "low" n but uses a different set of identities for larger n.<p><a href="http://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html" rel="nofollow">http://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html</a>

If im not mistaken the iterative solution of using a simple for loop would definitely be insanely faster than a recursive algorithm which is exponential.. What am i missing here?

The author very casually takes a potshot at issue #41, calling it a "really silly time wasting debate". Was #41 honestly such a silly time waster? Pray, what would you have done with your precious time instead? I for one took away a lot from #41. It was a very valuable learning experience. #41 was definitely way more valuable than computing fibonaccis, if I may say so.

I used to use the two bucket method to generate a Fibonacci number, thanks for showing me another way to do it.<p>I am working on Ackermann Numbers now, but it takes a very long time to generate them and I have to either write my own classes to handle big numbers or using a different library to use large numbers. I moved from C to C++ to do that. Your unsigned long int variable would run out of room after the 96th Fibonacci number, and you might have to move to C++ and use a custom class as well to be able to handle those big numbers.

I came to the exact opposite conclusion as the author. Programmers should know a lot of things, including both recursion and math since tere are many ways to approach a problem.

Wait Im confused. Wouldnt the point of using the analytic approach be that i could start at any n besides 0? Because of course if im just taking the sums from 0 to n it'd be faster to do it the tail recursive way because thats just simple addition.

Only the first 90ish fibonacci numbers fit in a 4 byte int. Use a lookup table, make it O(1).