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
Another combination of seq and awk. Not very efficient, but sufficiently quick. Show Sample Output
only take the first field on each row to compute the fibo on this number Show Sample Output
recursive version, "pure" AWK 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.
Which processes are listening on a specific port (e.g. port 80)
indexsmithy
2
list files recursively by size
ysangkok
1
Which processes are listening on a specific port (e.g. port 80)
indexsmithy
2
find out how much space are occuipied by files smaller than 1024K (sic) - improved
bhepple
2
Recursively grep thorugh directory for string in file.
TheFox
8
use SHIFT + ALT to toggle between two keyboard layouts
retrodanny
2
Change a specific value in a path
zlemini
1
Copy 3 files from 3 different servers and adds server name tag to file copied
finku
1
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:
fib(){ k=0; l=1; for i in `seq 1 $1`; do t=$l; l=$(($l + $k)); k=$t; done; echo $k;}
also quick to write, but much fasterpython -c 'def fib(n):
if n not in fibs:fibs[n]=fib(n-1)+fib(n-2) return fibs[n] import sys;fibs={0:0,1:1};print fib(int(sys.argv[1]))' 7 13