The command is: gcc -x c -o /tmp/out - -lgmp <<< '#include <stdlib.h> #include <stdio.h> #include <string.h> #include <stdint.h> #include <gmp.h> void omg_i_love_leonardo_of_pisa(uint32_t num, mpz_t * result) { mpz_t retval, last, tmp; mpz_init(retval); mpz_init(last); mpz_init(tmp); uint32_t i = 1; if(num == 0) return; mpz_set_ui(retval, 1U); mpz_set_ui(last, 0U); for(; i < num; i++) { mpz_set(tmp, retval); mpz_add(retval, retval, last); mpz_set(last, tmp); } mpz_set(*result, retval); } int main() { uint32_t num; mpz_t fibo; mpz_init(fibo); omg_i_love_leonardo_of_pisa(1000001, &fibo); mpz_out_str(stdout, 10, fibo); printf("\n"); return 1; } ' && time /tmp/out
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
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
Returns the '$1'th Fibonacci number. Show Sample Output
only take the first field on each row to compute the fibo on this number Show Sample Output
Any thoughts on this command? Does it work on your machine? Can you do the same thing with only 14 characters?
You must be signed in to comment.
commandlinefu.com is the place to record those command-line gems that you return to again and again. 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.
Access to specific man page section
0disse0
1
List bash functions defined in .bash_profile or .bashrc
wilmoore
5
Plot frequency distribution of words from files on a terminal.
taliver
5
Search some text from all files inside a directory
zluyuer
2
Monitor a file's size
rbossy
1
Display formatted routes
servermanaged
1
Replace the content of an XML element
zlemini
1
Which processes are listening on a specific port (e.g. port 80)
indexsmithy
2
Copy an element from the previous command
dbbolton
16
Read almost everything (Changelog.gz, .tgz, .deb, .png, .pdf, etc, etc....)
prayer
2
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: