The 1 millionth fibonacci number

gcc -x c -o /tmp/out - -lgmp <<< '#include <stdlib.h> ... SEE SAMPLE OUTPUT FOR FULL COMMAND
It's hard to beat C. This is just slightly faster than the bc version on my machine. real 0m26.856s user 0m25.030s sys 0m0.024s Requirements: libgmp headers, gcc.
Sample Output
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

-5
By: hank
2009-09-10 02:10:46

These Might Interest You

  • 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


    -134
    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
    Escher · 2009-09-10 09:00:44 11
  • 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


    -135
    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
    Escher · 2009-09-10 08:58:47 5
  • Returns the '$1'th Fibonacci number. Show Sample Output


    2
    fib(){ case $1 in 0)echo 0;;1)echo 1;;[0-9]*)echo $[$(fib $[$1-2])+$(fib $[$1-1])];;*)exit 1;;esac;}
    kzh · 2010-06-28 19:41:44 5
  • only take the first field on each row to compute the fibo on this number Show Sample Output


    -5
    gawk '{n=$1;a=0;b=1;c=1;for(i=1;i<n;i++){c=a+b;a=b;b=c};print c}' << eof
    unixmonkey13930 · 2010-11-26 08:36:30 0

What Others Think

Sorry Hank, you're 2 secs slower than the bc version on an atom 1.6Ghzs netbook. :) Nice try though. For the cash prize you need to use commonly available shell tools rather than custom c code (After all, I could probably install mathematica and beat bc!)
Escher · 454 weeks and 3 days ago
Also, ~12 secs slower than bc version on a Core 2 Duo (48 secs v 36 secs)
Escher · 454 weeks and 3 days ago
I voted this down because we're really stretching the limits of what is "command line fu" here. A few more like this and this place loses its charm. I wish people would try and stick to simlpe, short-ish, command lines. Even if the utility used is not a standard or default one (exiftool in one of the other recent posts, for instance), the *command* should be one you wouldn't mind typing or pasting if needed
sitaram · 454 weeks ago

What do you think?

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.

What's this?

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.

Share Your Commands



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: