Hide

What's this?

commandlinefu.com is the place to record those command-line gems that you return to again and again.

Delete that bloated snippets file you've been using and share your personal repository with the world. 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.

If you have a new feature suggestion or find a bug, please get in touch via http://commandlinefu.uservoice.com/

Get involved!

You can sign-in using OpenID credentials, or register a traditional username and password.

OpenID
or
Sign in Register

First-time OpenID users will be automatically assigned a username which can be changed after signing in.

Hide

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:

Hide

News

2011-03-12 - Confoo 2011 presentation
Slides are available from the commandlinefu presentation at Confoo 2011: http://presentations.codeinthehole.com/confoo2011/
2011-01-04 - Moderation now required for new commands
To try and put and end to the spamming, new commands require moderation before they will appear on the site.
2010-12-27 - Apologies for not banning the trolls sooner
Have been away from the interwebs over Christmas. Will be more vigilant henceforth.
2010-09-24 - OAuth and pagination problems fixed
Apologies for the delay in getting Twitter's OAuth supported. Annoying pagination gremlin also fixed.
Hide

Tags

Hide

Functions

Hide

Credits

Site by David Winterbottom (user root).

The 1 millionth fibonacci number

Terminal - 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
2009-09-10 09:00:44
User: Escher
Functions: echo time
-136
Up
Down
The 1 millionth fibonacci number

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 | Add to favourites | Report as malicious

Alternatives

There are 2 alternatives - vote for the best!

Terminal - Alternatives
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
2009-09-10 08:58:47
User: Escher
Functions: echo time
-134
Up
Down
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 | Comments (5) | Add to favourites | Report as malicious

Know a better way?

If you can do better, submit your command here.

What others think

My C version is faster. Stop posting duplicates.

Comment by hank 193 weeks ago

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

Comment by linuxrawkstar 193 weeks 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.

Comment by Escher 193 weeks 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...

Comment by sklm 193 weeks 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.

Comment by Escher 193 weeks 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!!!

Comment by sklm 193 weeks ago

Well now. Someone has a voting script...

Comment by SuperFly 193 weeks ago

can this be made faster by using multiple CPUs ?

Comment by alperyilmaz 192 weeks and 6 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.

Comment by Escher 192 weeks and 6 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.

Comment by sitaram 192 weeks and 5 days 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.

Comment by alvinx 192 weeks and 3 days ago

Your point of view

You must be signed in to comment.

Related sites and podcasts