What is the fastest way to write Fibonacci function in Scala?

scala recursion fibonacci
Enrico Susatyo picture Enrico Susatyo · Sep 12, 2011 · Viewed 12.9k times · Source

I've looked over a few implementations of Fibonacci function in Scala starting from a very simple one, to the more complicated ones.

I'm not entirely sure which one is the fastest. I'm leaning towards the impression that the ones that uses memoization is faster, however I wonder why Scala doesn't have a native memoization.

Can anyone enlighten me toward the best and fastest (and cleanest) way to write a fibonacci function?

Answer

Landei picture Landei · Sep 12, 2011

The fastest versions are the ones that deviate from the usual addition scheme in some way. Very fast is the calculation somehow similar to a fast binary exponentiation based on these formulas:

F(2n-1) = F(n)² + F(n-1)²
F(2n) = (2F(n-1) + F(n))*F(n)

Here is some code using it:

def fib(n:Int):BigInt = {
   def fibs(n:Int):(BigInt,BigInt) = if (n == 1) (1,0) else {
     val (a,b) = fibs(n/2)
     val p = (2*b+a)*a
     val q = a*a + b*b
     if(n % 2 == 0) (p,q) else (p+q,p)
   }
   fibs(n)._1
}

Even though this is not very optimized (e.g. the inner loop is not tail recursive), it will beat the usual additive implementations.

Related questions

Scala - convert List of Lists into a single List: List[List[A]] to List[A]

What's the best way to convert a List of Lists in scala (2.9)? I have a list: List[List[A]] which I want to convert into List[A] How can that be achieved recursively? Or is there any other better way?

Read More
Reverse list Scala

Given the following code: import scala.util.Random object Reverser { // Fails for big list def reverseList[A](list : List[A]) : List[A] = { list match { case Nil => list case (x :: xs) => reverseList(xs) ::: List(x) } } // Works def reverseList2[A](…

Read More
How to call a method n times in Scala?

I have a case where I want to call a method n times, where n is an Int. Is there a good way to do this in a "functional" way in Scala? case class Event(name: String, quantity: Int, value: …

Read More