Your best Fibonacci algorithm?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Your best Fibonacci algorithm?

Postby squareroot » Thu Jul 15, 2010 3:58 pm UTC

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!
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: You're best Fibonacci algorithm?

Postby mike-l » Thu Jul 15, 2010 5:56 pm UTC

You could just use the closed form here: http://en.wikipedia.org/wiki/Fibonacci_ ... lden_ratio
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

cogman
Posts: 112
Joined: Sun May 18, 2008 2:17 pm UTC

Re: You're best Fibonacci algorithm?

Postby cogman » Thu Jul 15, 2010 6:26 pm UTC

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.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: You're best Fibonacci algorithm?

Postby jaap » Thu Jul 15, 2010 6:36 pm UTC

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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: You're best Fibonacci algorithm?

Postby skeptical scientist » Fri Jul 16, 2010 6:57 pm UTC

Both of those take O(log n), which is best possible (since it takes O(log n) time just to read the input).
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: You're best Fibonacci algorithm?

Postby squareroot » Sat Jul 17, 2010 12:03 am UTC

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.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

User avatar
Patashu
Answerful Bignitude
Posts: 378
Joined: Mon Mar 12, 2007 8:54 am UTC
Contact:

Re: You're best Fibonacci algorithm?

Postby Patashu » Sat Jul 17, 2010 3:31 am UTC

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.

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: You're best Fibonacci algorithm?

Postby PM 2Ring » Sun Jul 18, 2010 12:23 am UTC

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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: You're best Fibonacci algorithm?

Postby skeptical scientist » Sun Jul 18, 2010 4:06 am UTC

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).
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: You're best Fibonacci algorithm?

Postby WarDaft » Sun Jul 18, 2010 4:51 am UTC

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.
Last edited by WarDaft on Sun Jul 18, 2010 8:28 pm UTC, edited 1 time in total.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: You're best Fibonacci algorithm?

Postby Berengal » Sun Jul 18, 2010 10:38 am UTC

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.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: You're best Fibonacci algorithm?

Postby PM 2Ring » Sun Jul 18, 2010 11:08 am UTC

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.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: You're best Fibonacci algorithm?

Postby WarDaft » Sun Jul 18, 2010 11:30 pm UTC

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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

somebody already took it
Posts: 310
Joined: Wed Jul 01, 2009 3:03 am UTC

Re: You're best Fibonacci algorithm?

Postby somebody already took it » Mon Jul 19, 2010 1:16 am UTC

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?

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: You're best Fibonacci algorithm?

Postby WarDaft » Mon Jul 19, 2010 5:29 am UTC

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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: You're best Fibonacci algorithm?

Postby Berengal » Mon Jul 19, 2010 6:14 am UTC

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.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: You're best Fibonacci algorithm?

Postby BlackSails » Mon Jul 19, 2010 1:49 pm UTC

Could a mod please change the title? It is driving me crazy

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: You're best Fibonacci algorithm?

Postby skeptical scientist » Mon Jul 19, 2010 2:22 pm UTC

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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
Dason
Posts: 1311
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

Re: Your best Fibonacci algorithm?

Postby Dason » Mon Jul 19, 2010 2:28 pm UTC

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".
double epsilon = -.0000001;

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: Your best Fibonacci algorithm?

Postby squareroot » Mon Jul 19, 2010 3:44 pm UTC

Oh, dear, I hadn't noticed that mistake... I must now withdraw from all human contact in my shame... *shuffles into corner"
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

mikazo
Posts: 4
Joined: Tue Jul 20, 2010 9:38 pm UTC
Location: Canada

Re: Your best Fibonacci algorithm?

Postby mikazo » Tue Jul 20, 2010 10:08 pm UTC

Why not write it in Scheme or some other Lisp-like language?

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

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

Re: You're best Fibonacci algorithm?

Postby qbg » Wed Jul 21, 2010 2:31 am UTC

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)?

fr00t
Posts: 113
Joined: Wed Jul 15, 2009 11:06 am UTC

Re: You're best Fibonacci algorithm?

Postby fr00t » Fri Jul 23, 2010 6:03 pm UTC

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.

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

Re: Your best Fibonacci algorithm?

Postby letterX » Fri Jul 23, 2010 8:10 pm UTC

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.

User avatar
Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC

Re: Your best Fibonacci algorithm?

Postby Strilanc » Wed Aug 11, 2010 6:29 pm UTC

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.
Don't pay attention to this signature, it's contradictory.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 3 guests