# The absolutely fastest nth fibonacci number

time echo 'n=70332;m=(n+1)/2;a=0;b=1;i=0;while(m){e[i++]=m%2;m/=2};while(i--){c=a*a;a=c+2*a*b;b=c+b*b;if(e[i]){t=a;a+=b;b=t}};if(n%2)a*a+b*b;if(!n%2)a*(a+2*b)' | bc
Calculates nth Fibonacci number for all n>=0, (much faster than matrix power algorithm from http://everything2.com/title/Compute+Fibonacci+numbers+FAST%2521 ) n=70332 is the biggest value at http://bigprimes.net/archive/fibonacci/ (corresponds to n=70331 there), this calculates it in less than a second, even on a netbook. UPDATE: Now even faster! Uses recurrence relation for F(2n), see http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form n is now adjusted to match Fn at wikipedia, so bigprimes.net table is offset by 1. UPDATE2: Probably fastest possible now ;), uses a simple monoid operation: uses monoid (a,b).(x,y)=(ax+bx+ay,ax+by) with identity (0,1), and recursion relations: F(2n-1)=Fn*Fn+F(n-1)*F(n-1) F(2n)=Fn*(2*F(n-1)+Fn) then apply fast exponentiation to (1,0)^n = (Fn,F(n-1)) . Note that: (1,0)^-1=(1,-1) so (a,b).(1,0) = (a+b,a) and (a,b)/(1,0)=(a,b).(1,0)^-1=(b,a-b) So we can also use a NAF representation to do the exponentiation,http://en.wikipedia.org/wiki/Non-adjacent_form , it's also very fast (about the same, depends on n): `time echo 'n=70332;m=(n+1)/2;a=0;b=1;i=0;while(m>0){z=0;if(m%2)z=2-(m%4);m=(m-z)/2;e[i++]=z};while(i--){c=a*a;a=c+2*a*b;b=c+b*b;if(e[i]>0){t=a;a+=b;b=t};if(e[i]<0){t=a;a=b;b=t-b}};if(n%2)a*a+b*b;if(!n%2)a*(a+2*b)' | bc`
Sample Output
```14764850684189816403580140143363762977190377750284997600081715975272\
...
86184952971938819341683867271994735126240287405611087016153703798851\
46303000784

real	0m0.148s
user	0m0.128s
sys	0m0.004s

```

-135
2009-09-10 08:58:47

## 1 Alternatives + Submit Alt

• EDIT: Trolling crap removed ;) takes approx 6 secs on a Core 2 Duo @ 2GHz, and 15 secs on atom based netbooks! uses monoid (a,b).(x,y)=(ax+bx+ay,ax+by) with identity (0,1), and recursion relations: F(2n-1)=Fn*Fn+F(n-1)*F(n-1) F(2n)=(Fn+2*F(n-1))*Fn then apply fast exponentiation to (1,0)^n = (Fn,F(n-1)) . Note that: (1,0)^-1=(1,-1) so (a,b).(1,0) = (a+b,a) and (a,b)/(1,0)=(a,b).(1,0)^-1=(b,a-b) So we can also use a NAF representation to do the exponentiation,http://en.wikipedia.org/wiki/Non-adjacent_form , it's also very fast (about the same, depends on n): `time echo 'n=1000000;m=(n+1)/2;a=0;b=1;i=0;while(m>0){z=0;if(m%2)z=2-(m%4);m=(m-z)/2;e[i++]=z};while(i--){c=a*a;a=c+2*a*b;b=c+b*b;if(e[i]>0){t=a;a+=b;b=t};if(e[i]<0){t=a;a=b;b=t-b}};if(n%2)a*a+b*b;if(!n%2)a*(a+2*b)' | bc` Show Sample Output

-134
time echo 'n=1000000;m=(n+1)/2;a=0;b=1;i=0;while(m){e[i++]=m%2;m/=2};while(i--){c=a*a;a=c+2*a*b;b=c+b*b;if(e[i]){t=a;a+=b;b=t}};if(n%2)a*a+b*b;if(!n%2)a*(a+2*b)' | bc
· 2009-09-10 09:00:44

### What Others Think

I already pwnd you with C. hank · 581 weeks and 2 days ago
Nope, yours is slower on both machines I tested, in fact it's 10secs slower on a Core 2 Duo that's over 30% slower. So you're attempt, as well as being a cheat, was pretty rubbish, I have to say. Still, it's unfair on you guys to challenge you to to a contest against my colossal skill, you are all meer ants to me. Escher · 581 weeks and 2 days ago
`n=1000000; time bc <<< 'n='\$n';m=(n-1)/2;a=1;b=1;d=0;w=a;x=b;y=b;z=d;while(1){if(m%2){s=w*b+x*d;t=y*b+z*d;w=w*a+x*b;if(!--m)break;x=s;y=y*a+z*b;z=t};f=a+d;g=b*b;a=a*a+g;b*=f;d=g+d*d;m/=2};if(n%2)s*s+t*t;if(!n%2)(t+w)*s;'` is faster embe · 580 weeks and 6 days ago
yes ok, I should have spotted that the c variable was superfluous. The caclulation can in fact be made much faster than this, but a deal is a deal. Post your bank account details and I'll transfer an amount equal to a random fibonacci number. Escher · 580 weeks and 5 days ago
Updated to be even faster. Almost as fast as mathematica now! Can only be beaten by applying a shortest path algorithm to the exponentiation, which would make it unwieldy as a single shell command line. Escher · 580 weeks and 4 days ago

### What do you think?

Any thoughts on this command? Does it work on your machine? Can you do the same thing with only 14 characters?

You must be signed in to comment.

### What's this?

commandlinefu.com is the place to record those command-line gems that you return to again and again. That way others can gain from your CLI wisdom and you from theirs too. All commands can be commented on, discussed and voted up or down.

### Stay in the loop…  