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