On calculating Fibonacci numbers in C
blog.noblemail.ca
blog.noblemail.ca
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
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).
Also, the number n has O(log(n)) digits.
And nothing in my comment relates to "number of transistor switches or CPU cycles required for a single multiplication".
That's not to say you shouldn't take it into account, but the algorithm he described is, in fact, O(log(n)) time. It just is. That's how the math works. Now, you should note that the O(log(n)) time constraint does not take into account arbitrary integer size which will cause progressively larger constant factors to influence the efficiency of the algorithm... but it is still a O(log(n)) algorithm.
This isn't simply my viewpoint on the subject; even the very theoretical textbook by Papadimitriou and Vazirani takes this approach to the question (see exercise 0.4 and note that everything is carried out in terms of the complexity of arbitrary-size integer multiplication M(n)).
If they are getting progressively larger with larger inputs, then they are not in fact constant factors.
The analytic solution really should win for very large terms though, but I'm not sure how to implement it properly. Can someone outline how you would decide what precision is needed to compute the Nth Fibonacci number?
Lets say that A` and B` are approximations of A and B, that are within E of the actual answer, that is to say |A`-A|<E and |B`-B|<E.
The total error can be found by:
|(A^n-B^n)/sqrt(5) - (A`^n-B`^n)/sqrt(5)|
If we can make this error be less than 1/2, we can simply round to the nearest integer and have the correct answer.
|(A^n-B^n)/sqrt(5) - (A`^n-B`^n)/sqrt(5)| < 1/2
|(A^n - A`^n + B`^n - B^n)| < sqrt(5)/2
Notice that: |(A^n - A`^n + B`^n - B^n)| <= |(A^n - A`^n| + |B`^n - B^n)|
If both of those absolute values are less than sqrt(5)/4, than their sum would be less than sqrt(5)/2, satisfying the inequality. Because 1<sqrt(5/4), I will make them be less than 1. Without loss of generality, I will consider only one of the absolute values.
|A`^n - A^n| < 1
Assuming the maximum error:
|(A+E)^n - A^n| < 1
Notice that the first term when you expand the binomial is A^n, so the n-1 remaining terms are our error. Every coefficient is less than 2^n. The greatest that A factor can be is A^(n-1)<A^n. And the greatest that the E factor can be is E^1. Therefore all (n-1) factors are less than (2^n)(A^n)E.
The sum of these error term is therefore less than (n-1)(2^n)(A^n)E. So:
(n-1)(2^n)(A^n)E < 1
Because A<2, A^n<2^n we can say: (n-1)2(2^n)E < 1
E < 1/(2(n-1)(2^n))
If our value for A is accurate for d+1 (binary) digits passed the decimal point, E<=2^(-d).
2^(-d) < 1/(2(n-1)(2^n))
2^d > 2(n-1)(2^n)
d>lg(2)+lg(n-1)+lg(2^n)
d>1+lg(n-1)+n
d>2n
I made a lot of simplifications in this analysis, so you can probably get away with fewer terms. It is interesting to note that Fibonacci numbers grow exponentially, so the number of digits needed simply to right the answer grows linearly, so the extra digits do not decrease the algorithmic efficiency.
[1]http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib 2 = 1
fib n = case n `quotRem` 2 of
-- if n = 2*m
(m,0) -> (fib (m+1))^2 - (fib (m-1))^2
-- if n = 2*m + 1
(m,1) -> (fib (m+1))^2 + (fib (m ))^2Real answer: because I didn't realize that it's equivalent to O(n).
Define: Im5(a+b * sqrt(5)) =b
Fib(n)= Im5 ((1+1* sqrt(5))^n) / 2^(n-1)
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.
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}))
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.
I get the "less math" part of the article, but it just seemed a bit confused.
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.
You don't know a reason to use Fibonacci numbers, but that doesn't mean someone else might find a way to use them.
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.
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}))
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.
1: http://ronzii.wordpress.com/2011/07/09/using-matrix-exponent...
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.
Anyway I forked the original code, added an iterative version based on the comment by (Nick Craig Wood) (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.
[Recursive - 7921 ms], [Iteratiive - 8078 ms]
So the difference is negligible.
>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
Well, let's make them a bit more interesting then... The simple for loop is actually an example of dynamic programming, i.e. building a table of values from the bottom up in order to avoid repeated calculations. In this case the table only needs to have size 2, as an entry won't be read ever again after the first 2 uses.
2. The recursive function `fib_helper` in TFA is actually iterative in an TCO environment. Read it closely. There's only on recursive call at the end, not two. `back_one` and `back_two` mean fib(x-1) and fib(x-2) respectively, the same way you would solve it with a loop. With the right `CFLAGS` it should produce more or less the same bytecode.
In general, a recursive solution need never have a bigger big-O than an iterative solution. You just need to define a helper function that has a many input parameters as your for-loop had variables that it updates.
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.