The 1 millionth fibonacci number

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

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

Sample Output

19532821287077577316320149475962563324435429965918733969534051945716\
...
54385552378378141386675079286837205802043347225419033684684301719893\
411568996526838242546875

(over two hundred thousand digits, too long to display fully!)

real	0m6.614s
user	0m5.888s
sys	0m0.024s

-135

By: Escher

2009-09-10 09:00:44

echo time

1 Alternatives + Submit Alt

The absolutely fastest nth fibonacci number

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 Show Sample Output
This is sample output - yours may be different.
```
14764850684189816403580140143363762977190377750284997600081715975272\
...
86184952971938819341683867271994735126240287405611087016153703798851\
46303000784

real	0m0.148s
user	0m0.128s
sys	0m0.004s
```
-136

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

Escher · 2009-09-10 08:58:47 8

What Others Think

My C version is faster. Stop posting duplicates.

hank · 786 weeks and 3 days ago

Stop it Escher. You're just spamming now. Quit posting this and more variants. We get it already!

linuxrawkstar · 786 weeks and 3 days ago

Your C version is slower,in fact ~47secs vs my ~36secson a Core 2 Duo. I have put a message for people like you in capitals in the description section. No go away little buzzing insect.

Escher · 786 weeks and 3 days ago

Don't be too hard on this MrMerry/Escher degenerate... Desperate attempts to get some attention on the internet is his only way of communicating with the world outside his mama's basement...

sklm · 786 weeks and 3 days ago

Please only post comments if you have required skillz to compete against me. I know it's depressing for you to witness true greatness and realise how insignificant you are, but that's life sklm, you always were and always will be an irrelevant ant.

Escher · 786 weeks and 3 days ago

"Please only post comments if you have required skillz to compete against me. I know it's depressing for you to witness true greatness and realise how insignificant you are, but that's life sklm, you always were and always will be an irrelevant ant." LMAO!!!

sklm · 786 weeks and 3 days ago

Well now. Someone has a voting script...

SuperFly · 786 weeks and 3 days ago

can this be made faster by using multiple CPUs ?

alperyilmaz · 786 weeks and 2 days ago

Not really, though it can be made faster by using the recurrence relations from the wikipedia article more efficiently. Check for an update soon :) For the record, mathematica uses an algorithm which is about 4 times faster.

Escher · 786 weeks and 2 days ago

I don't think this was a voting script; I'd like to think this is a reward for arrogance. Escher: a truly great person is humble. What bothers you is that the reverse is not necessarily true. And as long as that bothers you, you will be what you are, and will not grow further.

sitaram · 786 weeks and 1 day ago

Don't be so arrogant, dude ! It's just a shell command... I don't care for these numbers in any shell script... useless for me, sorry.

alvinx · 785 weeks and 6 days ago

rahimhh21 · 109 weeks and 1 day ago

Perfecthomepugs · 100 weeks and 5 days ago

pugpuppies95 · 62 weeks and 5 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.

Share Your Commands

Similar Commands

The 1 millionth fibonacci number

Fibonacci With Case

Fibonacci numbers with awk

Stay in the loop…

Follow the Tweets.

Every new command is wrapped in a tweet and posted to Twitter. Following the stream is a great way of staying abreast of the latest commands. For the more discerning, there are Twitter accounts for commands that get a minimum of 3 and 10 votes - that way only the great commands get tweeted.

» http://twitter.com/commandlinefu
» http://twitter.com/commandlinefu3
» http://twitter.com/commandlinefu10

Subscribe to the feeds.

Use your favourite RSS aggregator to stay in touch with the latest commands. There are feeds mirroring the 3 Twitter streams as well as for virtually every other subset (users, tags, functions,…):

Subscribe to the feed for:

» all commands
» commands with 3 up-votes (commandlinefu3)
» commands with 10 up-votes (commandlinefu10)