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:

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?

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?

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.

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

### Re: You're best Fibonacci algorithm?

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.
$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$
This combined with the exponentiation by squaring is probably equivalent to what you have.

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?

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?

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 - __ -

Patashu
Posts: 378
Joined: Mon Mar 12, 2007 8:54 am UTC
Contact:

### Re: You're best Fibonacci algorithm?

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.

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

### Re: You're best Fibonacci algorithm?

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.

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?

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

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

### Re: You're best Fibonacci algorithm?

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.

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?

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.CRealphi = (1 + sqrt 5) / 2fib n = (phi^n - (1 - phi)^n) / sqrt 5

Code: Select all

ghci> fib 1000 :: Double4.346655768693734e208ghci> fib 1000 :: CReal43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875.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.

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

### Re: You're best Fibonacci algorithm?

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.

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

### Re: You're best Fibonacci algorithm?

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.

Posts: 310
Joined: Wed Jul 01, 2009 3:03 am UTC

### Re: You're best Fibonacci algorithm?

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?

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

### Re: You're best Fibonacci algorithm?

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.

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?

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.

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

### Re: You're best Fibonacci algorithm?

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

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?

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

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

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

### Re: Your best Fibonacci algorithm?

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?

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

### Re: Your best Fibonacci algorithm?

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?

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?

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?

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.

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

### Re: Your best Fibonacci algorithm?

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.