Hacker News Reader

Comment by protomyth | Hacker News Reader

"....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.

View on HN

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?

I'd greatly appreciate it if you left this as a comment on the original post.

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.

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.

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.

If I don't have room to store 96 numbers in an array in the function, I am going to have problems elsewhere.

You haven't worked with embedded systems, have you? 96 numbers is 384 bytes. That's a lot of space for some applications.

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.

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.

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.

and only perform any optimizations at all after you have proved its a bottleneck for your application (unlikely) :p

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.

Reply on news.ycombinator.com