Fibonacci 1-liners

October 1, 2010
By

(This article was first published on Revolutions, and kindly contributed to R-bloggers)

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.

To leave a comment for the author, please follow the link and comment on his blog: Revolutions.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags:

Comments are closed.