5 ms·

On calculating Fibonacci numbers in C

109 points by avibryant 14y ago

protomyth 14y ago
"....since the 96th Fibonacci number is the largest to fit in an unsigned long int" 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.
- tlarkworthy 14y ago
  and only perform any optimizations at all after you have proved its a bottleneck for your application (unlikely) :p
  - protomyth 14y ago
    I just thought it was funny the article took a shortcut on speed testing because only 96 values were possible from the function. At that point, we are no longer talking about math or math error, we are talking a simple array lookup. I get the "less math" part of the article, but it just seemed a bit confused.
- orionblastar 14y ago
  This is basically a table lookup. You could do the same for any series of numbers like the prime numbers. You could store them in a database table even and then pull out the result by a key with the number assigned to it that represents the Nth Fibonacci number. It might even be faster than an array loaded from a text file, and if you happen to have limited memory and cannot store the entire array in memory some how later on when you use a different data type for large numbers and go past 96 numbers, the database method may even be faster and use less memory. You might even have to store the big numbers as a blob or text or something if the database cannot handle numbers that big.
  - protomyth 14y ago
    If I don't have room to store 96 numbers in an array in the function, I am going to have problems elsewhere.
    - groby_b 14y ago
      You haven't worked with embedded systems, have you? 96 numbers is 384 bytes. That's a lot of space for some applications.
      - protomyth 14y ago
        actually, in the distant past, I did. I don't remember a lot of embedded systems where Fibonacci numbers were important or where floating point was a real option (been awhile, probably same length of time since 384 bytes was the killer). I was always RAM constrained more than ROM /EPROM.
    - orionblastar 14y ago
      You have to think ahead. You have 96 numbers now, but after 96 you have to change the data type to a larger storage to be able to store larger numbers. So when you pre-calc say 10,000 numbers what happens to your array then? What if the program is run on an embedded system for some reason that has memory limits? Like say someone finds a reason to use Fibonacci numbers on an embedded system to monitor machines and control machines and other stuff? You don't know a reason to use Fibonacci numbers, but that doesn't mean someone else might find a way to use them.
      - protomyth 14y ago
        Given the limits of the data type, I really am not going to think ahead until I change the data type[1]. If the new datatype can hold 10,000 numbers, then I will probably go back to an algorithm. I am really not sure about these embedded systems that have more RAM than ROM / EPROM / Flash. 384 bytes used for constant time performance in and embedded situation sounds pretty good to me. 1) not only would that be premature optimization, it would also change a function from constant time to variable. I do wonder about how big the stack frame is.
- snoble 14y ago
  Sure, but it's not a post about the bestest solution. It's a post about how using more advanced math can ("can" not "will") lead to a worse solution for your context. Fibonacci numbers in a long int is certainly a toy example; but it's a toy example that had an actual reference.
- just2n 14y ago
  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. 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. 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, if we only need the first 96 fibonacci numbers, ever, in our program, 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. 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: ((1, 1), (1, 0))^N -> ((f_{N+1}, f_N), (f_N, f_{N-1})) given N > 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?
  - snoble 14y ago
    I'd greatly appreciate it if you left this as a comment on the original post.
  - protomyth 14y ago
    I get the point of the article, but it seems like defaulting to a compiler optimization that might not be in other compilers is a poorer solution than examining the problem for another Math solution. You yourself have shown one. Computer precision is a problem and programmers should learn a lot about how ints and fp work, but throwing out all Mathematical solutions is really not a good idea.
orionblastar 14y ago
I used to use the two bucket method to generate a Fibonacci number, thanks for showing me another way to do it. 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.
- dalke 14y ago
  Note that the author did write "since the 96th Fibonacci number is the largest to fit in an unsigned long int".
jdreaver 14y ago
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. 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 number theory 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 relationships and patterns between objects (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. 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. 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.
- snoble 14y ago
  I do distinguish between math and Math. Decide for yourself what that distinction means.
  - mikeash 14y ago
    The shift key?
  - jdreaver 14y ago
    I reread the article with that in mind, and it makes much more sense, to the point that I am inclined to agree with much of what you said now. I think you should highlight that difference closer to the beginning of the article. That is a nice, subtle play on words.
    - snoble 14y ago
      how much emphasis to give to which messages is always the hardest part for me to writing these posts. I'll keep in mind that at times I can be too subtle.
Strilanc 14y ago
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]. 1: http://ronzii.wordpress.com/2011/07/09/using-matrix-exponentiation-to-calculated-nth-fibonacci-number/ http://ronzii.wordpress.com/2011/07/09/using-matrix-exponent...
mathattack 14y ago
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.
tyler-dodge 14y ago
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.
- dubya 14y ago
  The post didn't go into this, but the sum has a lovely closed form as well. The sum of the (phi^n-psi^n) terms is the difference of two geometric series, so you can apply sum(r^i, i=0..n)=(r^(n+1)-1)/(r-1) to get a formula that evaluates the sum exactly.
xyzzyz 14y ago
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. 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: https://github.com/xyzzyz/FibBinet https://github.com/xyzzyz/FibBinet
- stephencanon 14y ago
  While I agree with the gist of your comment, it's important to note that none of these give an O(lg(n)) algorithm for computing fibonacci numbers (except on a hypothetical computer that can do arbitrary size integer operations in O(1) time). The nth fibonacci number has O(n) digits, so you can't even write it out in time less than O(n). The repeated-squaring approach will involve multiplying numbers with O(n/2) = O(n) digits in its final step, so a very coarse analysis says the complexity is at least O(n lg n).
  - rcfox 14y ago
    You're conflating the magnitudes. You can't directly compare the number of multiplications with the number of transistor switches or CPU cycles required for a single multiplication. Also, the number n has O(log(n)) digits.
just2n 14y ago
Re-commenting on OP @ author's request: 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. 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. 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: ((1, 1), (1, 0))^N -> ((f_{N+1}, f_N), (f_N, f_{N-1})) given N > 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?
- dbaupp 14y ago
  (The author probably meant on the actual blog post, rather than at the top level on HN. :) )
  - just2n 14y ago
    If that's the case, I apologize, but I feel like a victim of ambiguous terminology!
aeon10 14y ago
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?
- snoble 14y ago
  fork the code and post the benchmark results
- dmlorenzetti 14y ago
  The recursive approach isn't necessarily worse, provided the compiler can do a so-called "tail call optimization" (in the original posting, note the line that says of the compiler optimization level, "We need -O2 so gcc will recognize the tail-call."). Tail-call optimization says that if a function directly returns the result of calling another function, then you don't need to add to the call stack in order to effect the function call-- you just modify the current stack frame as needed. For a recursive function, apparently a good compiler can essentially transform this into code very similar to what you'd get with an explicit loop. None of this means that a simple for-loop wouldn't be appropriate, or even faster. Personally I use for-loops a lot, and, like you, I would naturally incline to writing this using a loop rather than recursion. I see yours is a new account, so maybe this is just a cultural thing that I've got used to. To generalize grossly, recursion is more fashionable on HN than iteration. Every once in a while you'll see a post here that touches on iteration-- like maybe somebody will mention the tradeoffs between counting down and counting up a loop variable. But guaranteed at least once a week you'll see something on recursion and functional programming. My impression is that most people here understand that a simple for-loop will get the job done, but they don't see for-loops as very interesting, and don't figure it adds anything to the discussion to bring it up. Meanwhile, there are people here who will actively advocate against using for-loops. There's a whole theory of functional languages that says that if your program doesn't directly modify variables, then it's easier to reason about. A for-loop modifies the trip variable, so it's not a functional construct.
  - aeon10 14y ago
    Yes, I understand that recursion is much more appealing and leads to much cleaner and elegant code than iterative solutions. and thank you for the introduction to the community I suppose. Anyway I forked the original code, added an iterative version based on the comment by (Nick Craig Wood) (https://github.com/AeonAxan/benchmarking_fibonacci https://github.com/AeonAxan/benchmarking_fibonacci) Here are the benchmarks [recursive fib: 7,765 ms] | [iterative fib: 8,047 ms] | [analytic opt fib: 54,875] | [analytic fib: 103,937 ms] | And it appears that the recursive version is faster than the naive iterative version by a few hundred milliseconds.
alexkus 14y ago
GMP (arbitrary precision library) implements it as a lookup table for "low" n but uses a different set of identities for larger n. http://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html http://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html
dxbydt 14y ago
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.
pmb 14y ago
Only the first 90ish fibonacci numbers fit in a 4 byte int. Use a lookup table, make it O(1).

109 points by avibryant 14y ago

"....since the 96th Fibonacci number is the largest to fit in an unsigned long int" 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.

tlarkworthy 14y ago
and only perform any optimizations at all after you have proved its a bottleneck for your application (unlikely) :p
- protomyth 14y ago
  I just thought it was funny the article took a shortcut on speed testing because only 96 values were possible from the function. At that point, we are no longer talking about math or math error, we are talking a simple array lookup. I get the "less math" part of the article, but it just seemed a bit confused.
orionblastar 14y ago
This is basically a table lookup. You could do the same for any series of numbers like the prime numbers. You could store them in a database table even and then pull out the result by a key with the number assigned to it that represents the Nth Fibonacci number. It might even be faster than an array loaded from a text file, and if you happen to have limited memory and cannot store the entire array in memory some how later on when you use a different data type for large numbers and go past 96 numbers, the database method may even be faster and use less memory. You might even have to store the big numbers as a blob or text or something if the database cannot handle numbers that big.
- protomyth 14y ago
  If I don't have room to store 96 numbers in an array in the function, I am going to have problems elsewhere.
  - groby_b 14y ago
    You haven't worked with embedded systems, have you? 96 numbers is 384 bytes. That's a lot of space for some applications.
    - protomyth 14y ago
      actually, in the distant past, I did. I don't remember a lot of embedded systems where Fibonacci numbers were important or where floating point was a real option (been awhile, probably same length of time since 384 bytes was the killer). I was always RAM constrained more than ROM /EPROM.
  - orionblastar 14y ago
    You have to think ahead. You have 96 numbers now, but after 96 you have to change the data type to a larger storage to be able to store larger numbers. So when you pre-calc say 10,000 numbers what happens to your array then? What if the program is run on an embedded system for some reason that has memory limits? Like say someone finds a reason to use Fibonacci numbers on an embedded system to monitor machines and control machines and other stuff? You don't know a reason to use Fibonacci numbers, but that doesn't mean someone else might find a way to use them.
    - protomyth 14y ago
      Given the limits of the data type, I really am not going to think ahead until I change the data type[1]. If the new datatype can hold 10,000 numbers, then I will probably go back to an algorithm. I am really not sure about these embedded systems that have more RAM than ROM / EPROM / Flash. 384 bytes used for constant time performance in and embedded situation sounds pretty good to me. 1) not only would that be premature optimization, it would also change a function from constant time to variable. I do wonder about how big the stack frame is.
snoble 14y ago
Sure, but it's not a post about the bestest solution. It's a post about how using more advanced math can ("can" not "will") lead to a worse solution for your context. Fibonacci numbers in a long int is certainly a toy example; but it's a toy example that had an actual reference.
just2n 14y ago
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. 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. 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, if we only need the first 96 fibonacci numbers, ever, in our program, 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. 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: ((1, 1), (1, 0))^N -> ((f_{N+1}, f_N), (f_N, f_{N-1})) given N > 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?
- snoble 14y ago
  I'd greatly appreciate it if you left this as a comment on the original post.
- protomyth 14y ago
  I get the point of the article, but it seems like defaulting to a compiler optimization that might not be in other compilers is a poorer solution than examining the problem for another Math solution. You yourself have shown one. Computer precision is a problem and programmers should learn a lot about how ints and fp work, but throwing out all Mathematical solutions is really not a good idea.

orionblastar 14y ago

I used to use the two bucket method to generate a Fibonacci number, thanks for showing me another way to do it. 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.

dalke 14y ago
Note that the author did write "since the 96th Fibonacci number is the largest to fit in an unsigned long int".

jdreaver 14y ago

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. 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 number theory 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 relationships and patterns between objects (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. 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. 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.

snoble 14y ago
I do distinguish between math and Math. Decide for yourself what that distinction means.
- mikeash 14y ago
  The shift key?
- jdreaver 14y ago
  I reread the article with that in mind, and it makes much more sense, to the point that I am inclined to agree with much of what you said now. I think you should highlight that difference closer to the beginning of the article. That is a nice, subtle play on words.
  - snoble 14y ago
    how much emphasis to give to which messages is always the hardest part for me to writing these posts. I'll keep in mind that at times I can be too subtle.

Strilanc 14y ago

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]. 1: http://ronzii.wordpress.com/2011/07/09/using-matrix-exponentiation-to-calculated-nth-fibonacci-number/ http://ronzii.wordpress.com/2011/07/09/using-matrix-exponent...

mathattack 14y ago

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.

tyler-dodge 14y ago

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.

dubya 14y ago
The post didn't go into this, but the sum has a lovely closed form as well. The sum of the (phi^n-psi^n) terms is the difference of two geometric series, so you can apply sum(r^i, i=0..n)=(r^(n+1)-1)/(r-1) to get a formula that evaluates the sum exactly.

xyzzyz 14y ago

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. 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: https://github.com/xyzzyz/FibBinet https://github.com/xyzzyz/FibBinet

stephencanon 14y ago
While I agree with the gist of your comment, it's important to note that none of these give an O(lg(n)) algorithm for computing fibonacci numbers (except on a hypothetical computer that can do arbitrary size integer operations in O(1) time). The nth fibonacci number has O(n) digits, so you can't even write it out in time less than O(n). The repeated-squaring approach will involve multiplying numbers with O(n/2) = O(n) digits in its final step, so a very coarse analysis says the complexity is at least O(n lg n).
- rcfox 14y ago
  You're conflating the magnitudes. You can't directly compare the number of multiplications with the number of transistor switches or CPU cycles required for a single multiplication. Also, the number n has O(log(n)) digits.

just2n 14y ago

Re-commenting on OP @ author's request: 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. 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. 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: ((1, 1), (1, 0))^N -> ((f_{N+1}, f_N), (f_N, f_{N-1})) given N > 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?

dbaupp 14y ago
(The author probably meant on the actual blog post, rather than at the top level on HN. :) )
- just2n 14y ago
  If that's the case, I apologize, but I feel like a victim of ambiguous terminology!

aeon10 14y ago

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?

snoble 14y ago
fork the code and post the benchmark results
dmlorenzetti 14y ago
The recursive approach isn't necessarily worse, provided the compiler can do a so-called "tail call optimization" (in the original posting, note the line that says of the compiler optimization level, "We need -O2 so gcc will recognize the tail-call."). Tail-call optimization says that if a function directly returns the result of calling another function, then you don't need to add to the call stack in order to effect the function call-- you just modify the current stack frame as needed. For a recursive function, apparently a good compiler can essentially transform this into code very similar to what you'd get with an explicit loop. None of this means that a simple for-loop wouldn't be appropriate, or even faster. Personally I use for-loops a lot, and, like you, I would naturally incline to writing this using a loop rather than recursion. I see yours is a new account, so maybe this is just a cultural thing that I've got used to. To generalize grossly, recursion is more fashionable on HN than iteration. Every once in a while you'll see a post here that touches on iteration-- like maybe somebody will mention the tradeoffs between counting down and counting up a loop variable. But guaranteed at least once a week you'll see something on recursion and functional programming. My impression is that most people here understand that a simple for-loop will get the job done, but they don't see for-loops as very interesting, and don't figure it adds anything to the discussion to bring it up. Meanwhile, there are people here who will actively advocate against using for-loops. There's a whole theory of functional languages that says that if your program doesn't directly modify variables, then it's easier to reason about. A for-loop modifies the trip variable, so it's not a functional construct.
- aeon10 14y ago
  Yes, I understand that recursion is much more appealing and leads to much cleaner and elegant code than iterative solutions. and thank you for the introduction to the community I suppose. Anyway I forked the original code, added an iterative version based on the comment by (Nick Craig Wood) (https://github.com/AeonAxan/benchmarking_fibonacci https://github.com/AeonAxan/benchmarking_fibonacci) Here are the benchmarks [recursive fib: 7,765 ms] | [iterative fib: 8,047 ms] | [analytic opt fib: 54,875] | [analytic fib: 103,937 ms] | And it appears that the recursive version is faster than the naive iterative version by a few hundred milliseconds.

alexkus 14y ago

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

dxbydt 14y ago

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.

pmb 14y ago

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