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.
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.
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
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:
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:
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
There are 3 alternatives - vote for the best!
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
If you can do better, submit your command here.
You must be signed in to comment.
I already pwnd you with C.
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.
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
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.
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.