The other day, as an excuse to play around with custom iterators, I created some completely over-engineered code to calculate the Fibonacci sequences. But surely such a simple function can be implemented in fewer than my 15 lines? (Rick Wicklin, who writes the SAS blog *The Do Loop*, thinks so too.) We could use such a function to more easily show that the ratio of successive Fibonacci numbers tends to the Golden Ratio.

Barry Rowlingson suggests this function to calculate the ratio between the nth and n+1th Fibonacci number:

> fibrat=function(n){a=1;b=1;for(i in 1:n){t=b;b=a;a=a+t};return(a/b)} > fibrat(99) [1] 1.618034

A slight tweak to Barry's code yields a function to calculate the Nth Fibonacci number in 55 characters:

fib=function(n){a=0;b=1;for(i in 1:n){t=b;b=a;a=a+t};a}

I can do it in 1 fewer characters with the closed-form solution:

fib=function(n){g=(1+sqrt(5))/2;(g^n-(1-g)^n)/sqrt(5)}

But given that this equation is written in terms of the Golden Ratio, using it to *derive* the Golden Ratio pretty much defeats the purpose.

jebyrnes suggests another means of calculating the Golden Ratio from fibonacci numbers, this time using the sapply function:

> fv<-c() > sapply(1:20, function(i) if(i<3){fv[i] <<- 1}else + {fv[i]<<-fv[i-1]+fv[i-2]})[-1]/fv[-length(fv)] [1] 1.000000 2.000000 1.500000 1.666667 1.600000 1.625000 1.615385 1.619048 [9] 1.617647 1.618182 1.617978 1.618056 1.618026 1.618037 1.618033 1.618034 [17] 1.618034 1.618034 1.618034

jebyrnes also pointed me to this page of Fibonacci 1-liners in many languages including C, Java and Python. Unless I'm mistaken, R is now very close to holding the record for shortest 1-liner.

Combining the two in function form:

Barry's is still a wee bit shorter, though.

Posted by: jebyrnes | October 01, 2010 at 10:56

Using the bad algorithm brings it down to 42 characters :)

f=function(n) if(n<2) n else f(n-1)+f(n-2)

Posted by: Ian Fellows | October 01, 2010 at 11:22

Ha! 41 characters and fast:

f=function(n){k=1:n;sum(choose(n-k,k-1))}

One of the benefits of R over other languages (at least for math) is the combination of vectorized functions, and the variety of built-in statistical algorithms. The above function uses both of these advantages.

we can then print with:

print(sapply(1:100,f))

But note that both this function and David's are wrong. They say that fib(0)==1. This is because in R, sequences can run backward (i.e. 1:0==c(1,0)). This is a common R gotcha. To fix this we need:

f=function(n){k=1:n;ifelse(n<1,0,sum(choose(n-k,k-1)))}

Which brings us back up to 55 characters

Posted by: Ian Fellows | October 01, 2010 at 12:03

Did you know that any two numbers (at least one nonzero)can be used to initialize a Fibonacci sequence and the ratio will STILL converge to the golden ratio? And the convergence is fast!

fibrat=function(n,a=1,b=1){for(i in 1:n){t=b;b=a;a=a+t};a/b}

fibrat(20)

fibrat(20, 4, 17)

fibrat(20, 3.14159, 2.71828)

Posted by: Rick Wicklin | October 01, 2010 at 12:26

That's really interesting, Rick, didn't know that! Thanks! (And thanks also for the shout-out on your blog.)

Posted by: David Smith | October 01, 2010 at 12:33

another function for calculating the Fibonacci sequence, just for fun

fibo<-function(n){

if(n<=2){ c(0,1) } else { tmp<-fibo(n-1); c(0,tmp)+c(0,1,tmp[1:(n-2)])}

}

Posted by: theresa | October 01, 2010 at 15:46

Ian fellows, not much of a challenge, the bad algorithm is even concise (33 chars) in C:

Posted by: FMark | October 01, 2010 at 22:55

There is a good set of solutions on Rosetta Code.

Posted by: Derek Jones | October 02, 2010 at 10:05

That's another interesting and eye opening post , even if a bit advanced for those of us inexperienced in trading.

I would appreciate a post on the basics everyone must remember be it a newbie or apro.

Posted by: Tweteduedge | November 23, 2010 at 06:45