Your best Fibonacci algorithm?
Moderators: phlip, Moderators General, Prelates

 Posts: 548
 Joined: Tue Jan 12, 2010 1:04 am UTC
 Contact:
Your best Fibonacci algorithm?
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(N1)+fibo(N2));}
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!
if (N<3) {return 1;} else {return (fibo(N1)+fibo(N2));}
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  __ 
Good fucking job Will Yu, you found me  __ 
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.
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.
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?
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_{n1} \end{pmatrix}[/math]
This combined with the exponentiation by squaring is probably equivalent to what you have.
 skeptical scientist
 closedminded 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
"With math, all things are possible." —Rebecca Watson

 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.
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  __ 
Good fucking job Will Yu, you found me  __ 
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.
Re: You're best Fibonacci algorithm?
For quick calculation of moderatelysized 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.
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.
See here for details of how it works, and the Life pattern in .RLE format.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.
 skeptical scientist
 closedminded 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
"With math, all things are possible." —Rebecca Watson
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 (a1)))
 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.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.
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 (a1)))
 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?
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.
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.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.
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: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.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.
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?
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 Haskellmagic 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
 closedminded 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
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
"With math, all things are possible." —Rebecca Watson
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;

 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  __ 
Good fucking job Will Yu, you found me  __ 
Re: Your best Fibonacci algorithm?
Why not write it in Scheme or some other Lisplike language?
http://en.literateprograms.org/Fibonacci_numbers_%28Scheme%29
http://en.literateprograms.org/Fibonacci_numbers_%28Scheme%29
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)?
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.
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.
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:
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.
 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.
Who is online
Users browsing this forum: No registered users and 12 guests