6 ms·

That's given early in the article, but requires arbitrary precision arithmetic: Another method is to find a closed form for the solution of the recurrence rela

by agf 10y ago

That's given early in the article, but requires arbitrary precision arithmetic: Another method is to find a closed form for the solution of the recurrence relation. This leads to the real-valued formula: Fib(n)=(ϕn+1−ψn+1)/5‾√) where ϕ=(1+5‾√)/2 and ψ=(1−5‾√)/2. The practical flaw in this method is that it requires arbitrary precision real-valued arithmetic, but it works for small n.

tspiteri 10y ago
At first glance, the given integer formula is worse regarding arbitrary precision. The first bracket term is (4 << n*(3+n)) That is shifting 4 by n squared digits to the left, requiring more than n^2 binary digits. I think calling this an integer formula is misleading, since in computing algorithms, by integers we normally understand the basic integer supported by an ALU. This formula, while dealing with integers in the mathematical sense, deals with arbitrary precision (or bignum, or whatever you call it) in the computing sense.
- hnkain 10y ago
  I'm the author of the blog post. You're right, it requires n^2 binary digits (and I mention this at the end of the article). The formula isn't, and isn't meant to be, a good way to find Fibonacci numbers -- it's more of a fun curiosity.
skierscott 10y ago
Regardless, when I learned this method in my linear algebra it inspired me to write a blog post [1] showing the derivation! This is a classic programming question, and it's refreshing to see a closed form solution. [1]:https://scottsievert.com/blog/2015/01/31/the-mysterious-eigenvalue/ https://scottsievert.com/blog/2015/01/31/the-mysterious-eige...
- sidedishes 10y ago
  That it's the fastest is pretty surprising to me. Both Binet and matrix multiplication require exponentiation to n, which can be done in O(log n) multiplications (not n-1) using a clever recursion (and indeed numpy uses it). 2x2 matrices aren't exactly the hardest to multiply either, but I figured that the floating point operations with the Binet formula would enough baggage that would make it slower than the matrix method. Edit: I just saw Someone's comment - I guess that explains it.
  - Someone 10y ago
    No, it doesn't, if I understand the OPs claim correctly. I agree with you that, for large enough n, using O(n) steps in the recursion will be slower than doing O(log n) matrix multiplication steps. The addition chain improves on the binary approach for some values of n, but I don't think it can go below O(log n) because the binary method is fastest for all n that are powers of two (disclaimer: I know almost nothing of addition chains besides what I learned from TAOCP). And of course, finding the fastest addition chain doesn't come cheaply, either, if P != NP. Hm, maybe I understand the OP's claim: if you want to generate the first n items in the series, the recursive formula will be hard to beat. Even then, it may not be fastest on modern CPUs. https://oeis.org/A000045 https://oeis.org/A000045 gives F(n + 12) = 18F(n + 6) - F(n) So, six completely independent threads can each compute a sixth of the sequence. Doing that may be faster than trying to paralllelize the bignum additions.
Someone 10y ago
If you add a "round to integer" step at the end, it doesn't require arbitrary precision arithmetic. Careful numerical analysis can tell you how many digits of precision you need to compute fib(n). I would guess the end result would be similar to that of this method (2n bits being more than sufficient), the difference being that this method puts all the digits before the decimal point. Also, for large n, you may be able to assume ψ = 0 to speed up computations (given ψ < n, its nth power will get vanishingly small) But the matrix method is the easiest fast method one can write and prove robust. (It is not fastest because the trivial binary approach doesn't product optimal addition chains. See https://en.wikipedia.org/wiki/Addition_chain https://en.wikipedia.org/wiki/Addition_chain or (dense writing, as is normal in HAKMEM) http://www.inwap.com/pdp10/hbaker/hakmem/recurrence.html http://www.inwap.com/pdp10/hbaker/hakmem/recurrence.html) Also, there is a very simple method for implementing "isFib": isFib(n) := isSquare(5n^2+4) or isSquare(5n^2-4)
- user2994cb 10y ago
  Most fast methods for computing fib(n) come down to some variation of repeated squaring, so the time is dominated by the last multiplication (since the number of digits is doubling each time).
catnaroek 10y ago
Or you can do exact arithmetic in Q[sqrt(5)].
Grue3 10y ago
You only need to calculate round((1+√5)^n). The other term tends to 0, and thus can be ignored.

by agf 10y ago

tspiteri 10y ago

At first glance, the given integer formula is worse regarding arbitrary precision. The first bracket term is (4 << n*(3+n)) That is shifting 4 by n squared digits to the left, requiring more than n^2 binary digits. I think calling this an integer formula is misleading, since in computing algorithms, by integers we normally understand the basic integer supported by an ALU. This formula, while dealing with integers in the mathematical sense, deals with arbitrary precision (or bignum, or whatever you call it) in the computing sense.

hnkain 10y ago
I'm the author of the blog post. You're right, it requires n^2 binary digits (and I mention this at the end of the article). The formula isn't, and isn't meant to be, a good way to find Fibonacci numbers -- it's more of a fun curiosity.

skierscott 10y ago

Regardless, when I learned this method in my linear algebra it inspired me to write a blog post [1] showing the derivation! This is a classic programming question, and it's refreshing to see a closed form solution. [1]:https://scottsievert.com/blog/2015/01/31/the-mysterious-eigenvalue/ https://scottsievert.com/blog/2015/01/31/the-mysterious-eige...

sidedishes 10y ago
That it's the fastest is pretty surprising to me. Both Binet and matrix multiplication require exponentiation to n, which can be done in O(log n) multiplications (not n-1) using a clever recursion (and indeed numpy uses it). 2x2 matrices aren't exactly the hardest to multiply either, but I figured that the floating point operations with the Binet formula would enough baggage that would make it slower than the matrix method. Edit: I just saw Someone's comment - I guess that explains it.
- Someone 10y ago
  No, it doesn't, if I understand the OPs claim correctly. I agree with you that, for large enough n, using O(n) steps in the recursion will be slower than doing O(log n) matrix multiplication steps. The addition chain improves on the binary approach for some values of n, but I don't think it can go below O(log n) because the binary method is fastest for all n that are powers of two (disclaimer: I know almost nothing of addition chains besides what I learned from TAOCP). And of course, finding the fastest addition chain doesn't come cheaply, either, if P != NP. Hm, maybe I understand the OP's claim: if you want to generate the first n items in the series, the recursive formula will be hard to beat. Even then, it may not be fastest on modern CPUs. https://oeis.org/A000045 https://oeis.org/A000045 gives F(n + 12) = 18F(n + 6) - F(n) So, six completely independent threads can each compute a sixth of the sequence. Doing that may be faster than trying to paralllelize the bignum additions.

Someone 10y ago

If you add a "round to integer" step at the end, it doesn't require arbitrary precision arithmetic. Careful numerical analysis can tell you how many digits of precision you need to compute fib(n). I would guess the end result would be similar to that of this method (2n bits being more than sufficient), the difference being that this method puts all the digits before the decimal point. Also, for large n, you may be able to assume ψ = 0 to speed up computations (given ψ < n, its nth power will get vanishingly small) But the matrix method is the easiest fast method one can write and prove robust. (It is not fastest because the trivial binary approach doesn't product optimal addition chains. See https://en.wikipedia.org/wiki/Addition_chain https://en.wikipedia.org/wiki/Addition_chain or (dense writing, as is normal in HAKMEM) http://www.inwap.com/pdp10/hbaker/hakmem/recurrence.html http://www.inwap.com/pdp10/hbaker/hakmem/recurrence.html) Also, there is a very simple method for implementing "isFib": isFib(n) := isSquare(5n^2+4) or isSquare(5n^2-4)

user2994cb 10y ago
Most fast methods for computing fib(n) come down to some variation of repeated squaring, so the time is dominated by the last multiplication (since the number of digits is doubling each time).

catnaroek 10y ago

Or you can do exact arithmetic in Q[sqrt(5)].

Grue3 10y ago

You only need to calculate round((1+√5)^n). The other term tends to 0, and thus can be ignored.