Fibonacci 1-liners

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.

Comments

[jebyrnes]

Combining the two in function form:

f=function(n) {a=0;b=1; sapply(1:n, function(i) {t=a+b;a<<-b;b<<-t;b/a})}

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

[Ian Fellows]

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

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

[Ian Fellows]

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

[Rick Wicklin]

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)

[David Smith]

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

[theresa]

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)])}
}

[FMark]

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

F(n){return n<2?n:F(n-1)+F(n-2);}

[Derek Jones]

There is a good set of solutions on Rosetta Code.

[Tweteduedge]

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.