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.


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.

Universal configuration monitoring and system of record for IT.
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

May 19, 2015 - A Look At The New Commandlinefu
I've put together a short writeup on what kind of newness you can expect from the next iteration of clfu. Check it out here.
March 2, 2015 - New Management
I'm Jon, I'll be maintaining and improving clfu. Thanks to David for building such a great resource!
Hide

Top Tags

Hide

Functions

Psst. Open beta.

Wow, didn't really expect you to read this far down. The latest iteration of the site is in open beta. It's a gentle open beta-- not in prime-time just yet. It's being hosted over at UpGuard (link) and you are more than welcome to give it a shot. Couple things:

  • » The open beta is running a copy of the database that will not carry over to the final version. Don't post anything you don't mind losing.
  • » If you wish to use your user account, you will probably need to reset your password.
Your feedback is appreciated via the form on the beta page. Thanks! -Jon & CLFU Team

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 7 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 363 weeks and 3 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.

Comment by Escher 363 weeks and 3 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

Comment by embe 363 weeks 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 363 weeks 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 362 weeks and 5 days ago

Your point of view

You must be signed in to comment.