Page 1 of 1

Your best Fibonacci algorithm?

Posted: Thu Jul 15, 2010 3:58 pm UTC
by squareroot
Okay, I was wondering what you pplz here on the interwebz have as your fastest method of computing Fibonacci numbers - given a number N, return the Nth fibonacci number. A few simple ones I know:

if (N<3) {return 1;} else {return (fibo(N-1)+fibo(N-2));}

Based directly on the mathematical definition. If b is the number of bits in an int, runs in O(b*2^N). Sucks.

var a=1;
var b=1;
var t;
for (i=3; i<=N; i++){
t=b;
b=a;
a+=b;
}
return a;

A bit more efficient, and I guess it runs in (b*N). Not optimal, I guess...

The best one I've thought of exploits a certain property that Fibonacci numbers have:

Fibo(a)*Fibo(b)+Fibo(a+1)*Fibo(b+1)=Fibo(a+b+1)

So, first we compute the binary expansion of N. Then, we can use the above rule I just mentioned to compute the (2^A - 1) fibonacci numbers, where A is integer. To see this, suppose we know that Fibo(15)=610, Fibo(16)=987, and Fibo(17)=1597. Then, we can see that Fibo(31)=610*610+987*987=1346269 and Fibo(33)=987*987+1597*1597=3524578. Then, Fibo(32)=Fibo(33)-Fibo(31). We can use these three to find the next group of three fibonacci numbers. Once we have Fibo(2^floor(log_2(N))-1) computed, we can again "add" them in with the identity above, in a way corresponding to the binary expansion of N, to sum the indices to N.

Well, that's an outline of my most efficient algorithm. I forget what O() it runs in, but it was better than O(b*N). So, what do other people have? I'm eager to know!

Re: You're best Fibonacci algorithm?

Posted: Thu Jul 15, 2010 5:56 pm UTC
by mike-l
You could just use the closed form here: http://en.wikipedia.org/wiki/Fibonacci_ ... lden_ratio

Re: You're best Fibonacci algorithm?

Posted: Thu Jul 15, 2010 6:26 pm UTC
by cogman
It really depends on how often you are calling the Fibonacci function. If you are going to compute a random set of fib numbers, I find the dynamic programming approach to be a useful one.

If you are just spitting out every fib number 1 to 100, then doing the iterative method will be the fastest.

Re: You're best Fibonacci algorithm?

Posted: Thu Jul 15, 2010 6:36 pm UTC
by jaap
squareroot wrote:The best one I've thought of exploits a certain property that Fibonacci numbers have:


I like the matrix form that can be used to quickly calculate Fibonacci numbers.
[math]\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n =
\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}[/math]
This combined with the exponentiation by squaring is probably equivalent to what you have.

Re: You're best Fibonacci algorithm?

Posted: Fri Jul 16, 2010 6:57 pm UTC
by skeptical scientist
Both of those take O(log n), which is best possible (since it takes O(log n) time just to read the input).

Re: You're best Fibonacci algorithm?

Posted: Sat Jul 17, 2010 12:03 am UTC
by squareroot
When you say "both of those", do you mean the method I suggested and the one jaap described? I'm feeling slightly unclear...

As for the closed form, that would require you to first calculate phi to a high accuracy first (the number of digits would be O(N), I believe), which would leave it not being any more efficient. And storing the value of phi beforehand would be cheating, as you could equally store an array of Fibonacci numbers.

Re: You're best Fibonacci algorithm?

Posted: Sat Jul 17, 2010 3:31 am UTC
by Patashu
Why is the matrix form inherently faster to work with than the naive fibbonaci seque...aha! It's because you can do exponentiation by squaring. Okay.

Re: You're best Fibonacci algorithm?

Posted: Sun Jul 18, 2010 12:23 am UTC
by PM 2Ring
For quick calculation of moderately-sized Fibonacci numbers I like to use Binet's formula, but I agree that it does rely on having a sufficiently accurate value of phi. But that's not a huge problem, since you can improve phi approximations fairly quickly with Newton's method (despite phi having the slowest converging continued fraction), and although that's not quite as efficient as the matrix squaring technique, it's less fiddly.

However my favourite of all Fibonacci generators I've ever made is definitely not fast, and it just uses naive addition, since it is designed to calculate the Fibonacci sequence, not just a given member of the sequence. But it does it in Conway's Life. :)
PM 2Ring wrote:This circuit calculates the Fibonacci sequence in binary using p60 and p30 glider streams. Output is displayed using LWSS bits. A new Fibonacci number is generated every 2100 generations.
See here for details of how it works, and the Life pattern in .RLE format.

Re: You're best Fibonacci algorithm?

Posted: Sun Jul 18, 2010 4:06 am UTC
by skeptical scientist
squareroot wrote:When you say "both of those", do you mean the method I suggested and the one jaap described?

Yes (which are in fact two different ways of viewing the same algorithm).

Re: You're best Fibonacci algorithm?

Posted: Sun Jul 18, 2010 4:51 am UTC
by WarDaft
PM 2Ring wrote:and although that's not quite as efficient as the matrix squaring technique, it's less fiddly.

Playing around with arbitrary precision reals seems more fiddly than something like:

fibSq a = (fst a * fst a + snd a * snd a, 2 * fst a * snd a + snd a * snd a)
fibNxt a = (snd a,fst a + snd a)
fFib 1 = (0,1)
fFib a
| (mod a 2) == 1 = (fibNxt (fFib (a-1)))
| True = fibSq (fFib (quot a 2))

In Haskell. I'm sure it could be optimized at least a little further, but you would not get significant returns on it. Heck you'd probably have better returns from optimizing large number multiplication.

Re: You're best Fibonacci algorithm?

Posted: Sun Jul 18, 2010 10:38 am UTC
by Berengal
WarDaft wrote:Playing around with arbitrary precision reals seems more fiddly than something like:

Since we're on the topic of Haskell and arbitrary precision reals:

Code: Select all

import Data.Number.CReal

phi = (1 + sqrt 5) / 2

fib n = (phi^n - (1 - phi)^n) / sqrt 5

Code: Select all

ghci> fib 1000 :: Double
4.346655768693734e208

ghci> fib 1000 :: CReal
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875.0

What I like about this is the ".0" on the end. It's doing computations on friggin irrational numbers, yet reaches an exact result. On a computer! Granted, even repeated summing beat the pants off of it in terms of speed...

But fiddly? Not at all.

Re: You're best Fibonacci algorithm?

Posted: Sun Jul 18, 2010 11:08 am UTC
by PM 2Ring
skeptical scientist wrote:
squareroot wrote:When you say "both of those", do you mean the method I suggested and the one jaap described?

Yes (which are in fact two different ways of viewing the same algorithm).

Indeed.
WarDaft wrote:
skeptical scientist wrote:and although that's not quite as efficient as the matrix squaring technique, it's less fiddly.

Playing around with arbitrary precision reals seems more fiddly than something like:

fibSq a = (fst a * fst a + snd a * snd a, 2 * fst a * snd a + snd a * snd a)
fibNxt a = (snd a,fst a + snd a)
fFib 1 = (0,1)
fFib a
| (mod a 2) == 1 = (fibNxt (fFib (a-1)))
| True = fibSq (fFib (quot a 2))

In Haskell. I'm sure it could be optimized at least a little further, but you would not get significant returns on it. Heck you'd probably have better returns from optimizing large number multiplication.

WTF? That was me, not skeptical scientist.

It's less fiddly, because you don't need to compute an exact power: you just keep improving phi, doubling its precision with each loop until it's equal to or higher than the precision you need.

Re: You're best Fibonacci algorithm?

Posted: Sun Jul 18, 2010 11:30 pm UTC
by WarDaft
PM 2Ring wrote:WTF? That was me, not skeptical scientist.

It's less fiddly, because you don't need to compute an exact power: you just keep improving phi, doubling its precision with each loop until it's equal to or higher than the precision you need.

Weird, I'm not sure how his name got in there.

What I like about this is the ".0" on the end. It's doing computations on friggin irrational numbers, yet reaches an exact result. On a computer! Granted, even repeated summing beat the pants off of it in terms of speed...

But fiddly? Not at all.
True, but Haskell is just magical like that. In many other languages you'd have to do the approximation yourself to keep track of the precision you've reached.

Though I wonder, how fast the fib matrix squaring method to calculate phi is compared to other approximations..

Compared to the Newton method, it should only be a low constant (around 1.5) multiple slower. Unless there is a better optimization for long squaring than there is for long multiplication, then I couldn't say.

Re: You're best Fibonacci algorithm?

Posted: Mon Jul 19, 2010 1:16 am UTC
by somebody already took it
WarDaft wrote:
What I like about this is the ".0" on the end. It's doing computations on friggin irrational numbers, yet reaches an exact result. On a computer! Granted, even repeated summing beat the pants off of it in terms of speed...

But fiddly? Not at all.
True, but Haskell is just magical like that. In many other languages you'd have to do the approximation yourself to keep track of the precision you've reached.

Though I wonder, how fast the fib matrix squaring method to calculate phi is compared to other approximations..

Compared to the Newton method, it should only be a low constant (around 1.5) multiple slower. Unless there is a better optimization for long squaring than there is for long multiplication, then I couldn't say.

What makes Haskell magical? Does it do lazy evaluation on irrational roots?

Re: You're best Fibonacci algorithm?

Posted: Mon Jul 19, 2010 5:29 am UTC
by WarDaft
somebody already took it wrote:What makes Haskell magical? Does it do lazy evaluation on irrational roots?

Sort of, otherwise it would spend forever getting closer and closer approximations.

It realized how much accuracy was needed to answer the question posed, got that much accuracy, and then answered it.

Re: You're best Fibonacci algorithm?

Posted: Mon Jul 19, 2010 6:14 am UTC
by Berengal
The only piece of Haskell-magic in that code is the syntax. You could do the same in Java if you didn't mind doing arithmetic with objects and methods. The real magic lies in the CReal type, which is able to represent exactly any computable real, including irrationals.

Re: You're best Fibonacci algorithm?

Posted: Mon Jul 19, 2010 1:49 pm UTC
by BlackSails
Could a mod please change the title? It is driving me crazy

Re: You're best Fibonacci algorithm?

Posted: Mon Jul 19, 2010 2:22 pm UTC
by skeptical scientist
BlackSails wrote:Could a mod please change the title? It is driving me crazy

If you're really that bothered by seeing "you're" instead of "your", your probably crazy already.

Re: Your best Fibonacci algorithm?

Posted: Mon Jul 19, 2010 2:28 pm UTC
by Dason
Oh sadness. I liked it the other way. Whenever I viewed the thread I made that simple substitution in my head "You are best Fibonacci algorithm?" and I would tell it "Yes, yes I am".

Re: Your best Fibonacci algorithm?

Posted: Mon Jul 19, 2010 3:44 pm UTC
by squareroot
Oh, dear, I hadn't noticed that mistake... I must now withdraw from all human contact in my shame... *shuffles into corner"

Re: Your best Fibonacci algorithm?

Posted: Tue Jul 20, 2010 10:08 pm UTC
by mikazo
Why not write it in Scheme or some other Lisp-like language?

http://en.literateprograms.org/Fibonacci_numbers_%28Scheme%29

Re: You're best Fibonacci algorithm?

Posted: Wed Jul 21, 2010 2:31 am UTC
by qbg
skeptical scientist wrote:Both of those take O(log n), which is best possible (since it takes O(log n) time just to read the input).

Isn't the best possible O(n) since the length of the answer grows at O(n)?

Re: You're best Fibonacci algorithm?

Posted: Fri Jul 23, 2010 6:03 pm UTC
by fr00t
qbg wrote:
skeptical scientist wrote:Both of those take O(log n), which is best possible (since it takes O(log n) time just to read the input).

Isn't the best possible O(n) since the length of the answer grows at O(n)?


The size of the input string grows at O(log n) wrt the magnitude of the input.

Re: Your best Fibonacci algorithm?

Posted: Fri Jul 23, 2010 8:10 pm UTC
by letterX
However, the nth Fibonacci number grows as [imath]\phi^n[/imath], so the size of the output grows as O(log([imath]\phi^n[/imath])) = O(n). So printing the nth Fibonacci number will in any case take at least linear time. Similarly, while the above algorithms may take only O(log n) steps, this ignores the fact that real computers don't have constant time arithmetical operations for arbitrarily large numbers. They are still preferable, though, because a supposed 'linear' algorithm (like the naive iterative approach) is going to run into the same problem, and depending on your model of computation, could take something like O(n log n) time.

Re: Your best Fibonacci algorithm?

Posted: Wed Aug 11, 2010 6:29 pm UTC
by Strilanc
I derived a nice algorithm after I noticed this:
- Let F(0) = [0,1] and F(1) = [1,0]
- Then F(a+b) = F(a) dotproduct [F(b), F(b+1)]
- And So F(2*n) = F(n) dotproduct [F(n), F(n+1)]

Turning it into an algorithm, simplifying it, and translating it to something iterative gives:

Code: Select all

    public static BigInteger Fib(BigInteger n) {
        if (n < 0) return Fib(-n) * (n % 2 == 0 ? -1 : 1)
        if (n == 0) return 0;

        var a = BigInteger.Zero;
        var b = BigInteger.One;
        foreach (var bit in n.BigEndianBits().Skip(1)) {
            var a2 = a * a;
            var b2 = b * b;
            var s2 = (a + b) * (a + b);
            if (bit) {
                a = s2 - a2;
                b = s2 + b2;
            } else {
                a = a2 + b2;
                b = s2 - a2;
            }
        }

        return b;
    }


It's as fast as the matrix exponentiation method, and probably almost exactly equivalent. Takes constant space and a logarithmic number of operations. However, the operations become quite expensive because the result is necessarily large.