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
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
Sample Output
14764850684189816403580140143363762977190377750284997600081715975272\
...
86184952971938819341683867271994735126240287405611087016153703798851\
46303000784

real	0m0.148s
user	0m0.128s
sys	0m0.004s


-136
By: Escher
2009-09-10 08:58:47

1 Alternatives + Submit Alt

  • 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


    -135
    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 13

What Others Think

I already pwnd you with C.
hank · 698 weeks and 2 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.
Escher · 698 weeks and 2 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
embe · 697 weeks and 6 days 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.
Escher · 697 weeks and 5 days 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.
Escher · 697 weeks and 4 days ago
Pug Puppies for Sale Near Me pugs puppies for sale teacup pugs for sale pug puppies for sale by owner pug puppies ohio PUG PUPPY FOR SALE NEAR ME PUG PUPPIES FOR SALE pug puppies for sale in kentucky Pug Puppies for Sale Under $500 Near Me pug puppies for sale in texas pug puppies for sale $200 pugs for sale near me under $500 pugs for sale under $400 near me pugs for sale near me puppies for sale near me under $500 pug puppies for sale under $1,000 near me pug for sale pug puppies for sale under $300 Brindle Pug Pitbull Pug Mix Pugs for sale cheap Cheap pug affordable pug puppies for sale near me black pugs for sale near me White Pugs for sale pug dog for sale free pug puppies pug puppies for sale in my area mn pug breeders pug puppies indiana pugs for sale michigan PUG PUPPY ADOPTION Pug puppies for sale Pug puppies for sale near me Pug puppies near me Pug Puppies for Sale Under $500 Near Me Cute Pug Puppies Black pug puppies Black pug puppies for sale pug puppies for adoption black pug puppies for sale near me chihuahua pug mix puppies how much is a pug puppy teacup pug puppies baby pug puppies pictures of pug puppies pug puppies for sale in Ohio pug puppies price pug mix puppies teacup pug puppies for sale best food for pug puppy newborn pug puppies pug puppies craigslist pug puppies for sale craigslist adorable pug puppies how much does a pug puppy cost Pitbull pug mix puppies pug pit mix puppy pug puppies for sale $200 pug puppies for sale in NJ Pug puppies for sale in Wisconsin pug puppy cost pug puppy food royal canin pug puppy royal canin pug puppy food fawn pug puppy pug puppies for sale florida pug puppies for sale in Indiana pug puppies for sale in KY pug puppies for sale in NC pug dog puppy AKC Registered Pug Puppies For sale cheap pug puppies for sale near me cheap pug puppies for sale in California cheap pug puppies for sale in nj Black Pug Puppies for sale pugs puppies for sale pug puppies indiana Amazing! This blog looks just like my old one! It's on a completely different subject but it has pretty much the same layout and design. Wonderful choice of colors!
rahimhh21 · 21 weeks ago
Since 2008, Perfect House Pug Puppies has been the leading Pug puppy breeder in the US, providing premium Pug puppies for sale. Each puppy exhibits the professionalism and knowledge that have set Perfect House Pug puppies apart from other pug puppy breeders. The professionals at Perfect House Pug Puppies are dedicated about finding their puppies loving, beloved homes where they can enjoy long, healthy lives. A companion that has been produced for quality, health, and temperament that satisfies the breed standard is guaranteed by Perfect House Pug puppies, the pug breeder that has set the benchmark for exceptional customer satisfaction. If you are looking to buy a baby pug, Black and white pugs, Mini pug puppies for sale, Black and tan pug for sale, Teacup pug puppies for sale, Female pug puppies, pug puppies for sale, pug puppies for sale near me, pug puppies for sale under $500 near me. Pug Puppies for Sale Near Me pugs puppies for sale teacup pugs for sale pug puppies for sale by owner pug puppies ohio PUG PUPPY FOR SALE NEAR ME PUG PUPPIES FOR SALE pug puppies for sale in kentucky Pug Puppies for Sale Under $500 Near Me pug puppies for sale in texas pug puppies for sale $200 pugs for sale near me under $500 pugs for sale under $400 near me pugs for sale near me puppies for sale near me under $500 pug puppies for sale under $1,000 near me pug for sale pug puppies for sale under $300 Brindle Pug Pitbull Pug Mix Pugs for sale cheap Cheap pug affordable pug puppies for sale near me black pugs for sale near me White Pugs for sale pug dog for sale free pug puppies pug puppies for sale in my area mn pug breeders pug puppies indiana pugs for sale michigan PUG PUPPY ADOPTION Pug puppies for sale Pug puppies for sale near me Pug puppies near me Pug Puppies for Sale Under $500 Near Me Cute Pug Puppies Black pug puppies Black pug puppies for sale pug puppies for adoption black pug puppies for sale near me chihuahua pug mix puppies how much is a pug puppy teacup pug puppies baby pug puppies baby pug puppies for sale pictures of pug puppies pug puppies for sale in Ohio pug puppies price pug mix puppies teacup pug puppies for sale best food for pug puppy newborn pug puppies pug puppies craigslist pug puppies for sale craigslist adorable pug puppies how much does a pug puppy cost Pitbull pug mix puppies pug pit mix puppy pug puppies for sale $200 pug puppies for sale in NJ Pug puppies for sale in Wisconsin pug puppy cost pug puppy food royal canin pug puppy royal canin pug puppy food fawn pug puppy pug puppies for sale florida pug puppies for sale in Indiana pug puppies for sale in KY pug puppies for sale in NC pug dog puppy AKC Registered Pug Puppies For sale cheap pug puppies for sale near me cheap pug puppies for sale in California cheap pug puppies for sale in nj Black Pug Puppies for sale pugs puppies for sale
Perfecthomepugs · 12 weeks and 4 days 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: