Fibonacci With Case

fib(){ case $1 in 0)echo 0;;1)echo 1;;[0-9]*)echo $[$(fib $[$1-2])+$(fib $[$1-1])];;*)exit 1;;esac;}
Returns the '$1'th Fibonacci number.
Sample Output
$ fib 2
1
$

2
By: kzh
2010-06-28 19:41:44

These Might Interest You

  • 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
  • Another combination of seq and awk. Not very efficient, but sufficiently quick. Show Sample Output


    14
    seq 50| awk 'BEGIN {a=1; b=1} {print a; c=a+b; a=b; b=c}'
    kaan · 2009-03-24 20:39:24 1
  • 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
  • recursive version, "pure" AWK Show Sample Output


    5
    awk 'func f(n){return(n<2?n:f(n-1)+f(n-2))}BEGIN{while(a<24){print f(a++)}}'
    unefunge · 2010-11-24 10:40:08 2

What Others Think

recursively finding fibonacci sequences is a really good way to freeze any system up use a for loop for a more efficient calculation
amanharan · 416 weeks and 2 days ago
If one were worried about efficiency, then one should not use a shell script. This was quick to write. Thanks for the input.
kzh · 416 weeks and 2 days ago
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 faster
fpunktk · 416 weeks and 2 days ago
fpunktk: 93th and some others afterwards are negative, why is that?
alperyilmaz · 416 weeks and 2 days ago
I had never really used bash case statements before and was trying them out. If I really wanted to use large numbers, I would have done: python -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
kzh · 416 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.

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: