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.

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

The absolutely fastest nth fibonacci number

Terminal - 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
2009-09-10 08:58:47
User: Escher
Functions: echo time
-136
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

Alternatives

There are 4 alternatives - vote for the best!

Terminal - Alternatives
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
-135

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

Know a better way?

If you can do better, submit your command here.

What others think

I already pwnd you with C.

Comment by hank 275 weeks 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.

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

Comment by embe 274 weeks and 4 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.

Comment by Escher 274 weeks and 4 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.

Comment by Escher 274 weeks and 2 days ago

Your point of view

You must be signed in to comment.

Related sites and podcasts