# The 1 millionth fibonacci number

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
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`
Sample Output
```19532821287077577316320149475962563324435429965918733969534051945716\
...
54385552378378141386675079286837205802043347225419033684684301719893\
411568996526838242546875

(over two hundred thousand digits, too long to display fully!)

real	0m6.614s
user	0m5.888s
sys	0m0.024s

```

-135
2009-09-10 09:00:44

## 1 Alternatives + Submit Alt

• 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

-136
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
· 2009-09-10 08:58:47

### What Others Think

My C version is faster. Stop posting duplicates.
hank · 742 weeks ago
Stop it Escher. You're just spamming now. Quit posting this and more variants. We get it already!
linuxrawkstar · 742 weeks ago
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.
Escher · 742 weeks ago
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...
sklm · 741 weeks and 6 days ago
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.
Escher · 741 weeks and 6 days ago
"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!!!
sklm · 741 weeks and 6 days ago
Well now. Someone has a voting script...
SuperFly · 741 weeks and 6 days ago
can this be made faster by using multiple CPUs ?
alperyilmaz · 741 weeks and 6 days ago
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.
Escher · 741 weeks and 5 days ago
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.
sitaram · 741 weeks and 5 days ago
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.
alvinx · 741 weeks and 3 days 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 · 56 weeks and 2 days ago
pugpuppies95 · 18 weeks and 2 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.