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/
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:
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
There are 6 alternatives - vote for the best!
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
If you can do better, submit your command here.
You must be signed in to comment.
My C version is faster. Stop posting duplicates.
Stop it Escher. You're just spamming now. Quit posting this and more variants. We get it already!
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.
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...
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.
"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!!!
Well now. Someone has a voting script...
can this be made faster by using multiple CPUs ?
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.
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.
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.