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

Question

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?

Solution 1

for me the simplest defines a recursive inner tail function:

def fib: Stream[Long] = {
  def tail(h: Long, n: Long): Stream[Long] = h #:: tail(n, h + n)
  tail(0, 1)
}

This doesn't need to build any Tuple objects for the zip and is easy to understand syntactically.

Solution 2

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.

Solution 3

Scala does have memoization in the form of Streams.

val fib: Stream[BigInt] = 0 #:: 1 #:: fib.zip(fib.tail).map(p => p._1 + p._2)

scala> fib take 100 mkString " "
res22: String = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 ...

Stream is a LinearSeq so you might like to convert it to an IndexedSeq if you're doing a lot of fib(42) type calls.

However I would question what your use-case is for a fibbonaci function. It will overflow Long in less than 100 terms so larger terms aren't much use for anything. The smaller terms you can just stick in a table and look them up if speed is paramount. So the details of the computation probably don't matter much since for the smaller terms they're all quick.

If you really want to know the results for very big terms, then it depends on whether you just want one-off values (use Landei's solution) or, if you're making a sufficient number of calls, you may want to pre-compute the whole lot. The problem here is that, for example, the 100,000th element is over 20,000 digits long. So we're talking gigabytes of BigInt values which will crash your JVM if you try to hold them in memory. You could sacrifice accuracy and make things more manageable. You could have a partial-memoization strategy (say, memoize every 100th term) which makes a suitable memory / speed trade-off. There is no clear anwser for what is the fastest: it depends on your usage and resources.

Solution 4

This could work. it takes O(1) space O(n) time to calculate a number, but has no caching.

object Fibonacci {
    def fibonacci(i : Int) : Int = {      
        def h(last : Int, cur: Int, num : Int) : Int = {
            if ( num == 0) cur
            else h(cur, last + cur, num - 1)
        }

        if (i < 0) - 1
        else if (i == 0 || i == 1) 1
        else h(1,2,i - 2)
   }

   def main(args: Array[String]){
      (0 to 10).foreach( (x : Int) => print(fibonacci(x) + " "))
   }
}

Solution 5

The answers using Stream (including the accepted answer) are very short and idiomatic, but they aren't the fastest. Streams memoize their values (which isn't necessary in iterative solutions), and even if you don't keep the reference to the stream, a lot of memory may be allocated and then immediately garbage-collected. A good alternative is to use an Iterator: it doesn't cause memory allocations, is functional in style, short and readable.

def fib(n: Int) = Iterator.iterate(BigInt(0), BigInt(1)) { case (a, b) => (b, a+b) }.
                           map(_._1).drop(n).next

View more solutions

Comments

[agilesteel]

Check out this.

[ziggystar]

+1 I remember deriving this formula in an exercise for linear algebra. It was the most fun exercise of the course.

[Raphael]

If you want to go down that path, why not use the closed formula?

[Landei]

Because the scope of Binet's formula is limited by the decimal precision of the root, and because it is not really clear if calculating the n-th power of a real number is faster than the formula above working on integers.

[Xorlev]

I approve of this solution, as far as I know it does end up being the fastest solution in terms of total operations when simplifying the matrix as far as possible.

[Enrico Susatyo]

Thanks for the answer Luigi. Your code is in fact very similar to Scala's implementation of fib in Stream.scala (lampsvn.epfl.ch/trac/scala/browser/scala/trunk/src///librar‌​y/…) line:47 to 51. I do agree that it depends on my use of fibonacci numbers and I completely agree that Landei's solution will be better if I want to just compute a one off value. Thanks so much!

[Enrico Susatyo]

BTW, what does the #:: operator mean? I'm trying to find it in the Scala library but couldn't find it anywhere...

[Luigi Plinge]

@Enrico If you look under the search box on the Scaladoc, there is an alphabetic index. To the left of A is #, which you can use to look up symbolic methods. #:: is a method on ConsWrapper, which is a type member of the Stream object. But there's an implicit conversion, so essentially it's a method on Stream. It creates a new Stream from the existing Stream with the argument at its head (just like :: for List), and since it ends in : is right-associative. Example: 0 #:: Stream(1,2,3) is the same as Stream(1,2,3).#::(0) and equates to Stream(0,1,2,3).

[Luigi Plinge]

This also equates to Stream.cons(0, Stream(1,2,3)), which is another way of constructing Streams, using the Stream singleton.

[Luigi Plinge]

You should change def fib to val fib, since a def will produce a new Stream every time and you don't benefit from memoization. Then you won't have to worry about the the one-time cost of a couple of nanoseconds to create some tuples :)

[Jed Wesley-Smith]

Whether the Stream is kept around and reused isn't a concern of the definition. The OP's question is specifically about the fastest Fibonacci, so the reduction in intermediate object creations is relevant.

[Luigi Plinge]

The speed difference is unmeasurably small and hence irrelevant for a single function call. The only way to measure it would be to benchmark a few million calls to your fib function. In which case the version with def will be hundreds of times slower than with val (and also slower than Landei's solution).

[Jed Wesley-Smith]

Stream memoizes the produced values, if you are reusing the Stream over and again then the cost of the original value function is amortized. Defining the above as a val means that all computed values are strongly referenced and are only GCed when the outer scope is – a def delegates reuse to another place. As far as costs go, the only relevant cost here is for the tail function, where this one is slightly more efficient.

[Enrico Susatyo]

Hmmm is it just me or does the scaladoc not available for the # page? dl.dropbox.com/u/2774926/… I understand your explanation of #:: though, but the # would have been very useful if it was working...

[Luigi Plinge]

@Enrico I use the downloaded docs, but for me the shortcut link there fails for some reason too. You can locate the relevant folder on your drive and make a separate bookmark for the # index page.

[linuS]

I don't understand why this answer was downvoted. This tail recursive method is equivalent to using while loop and calculates nth fibonacci number in exactly n function calls. This method is calls itself significantly less number of times than the memoized version that uses f(n-1) + f(n-2) formula. Also, with tail recursion, the function stack is reused resulting in speed gain. So, this simple tail recursive method should be faster. So, why the downvote?

[michau]

If we don't want to reuse the stream, this won't be an effective solution, because a lot of memory may be allocated and then immediately garbage-collected. A posted an answer using Iterator, which doesn't have this problem.

[Jed Wesley-Smith]

Iterators are not at all functional, they maintain an internal state that is modified when calling next. Your solution does indeed allocate (a+b) creates a new BigInt instance, and you drop the first n elements to get to the nth one – ie. you get no opportunity for reuse, and must produce N + 2 BigInts every time you want to get the nth one.

[michau]

@JedWesley-Smith If you assign an iterator to a variable and do something with it, that's not functional, I agree. But here the state is not exposed. Non-functional tools can be used in a functional way.

[michau]

@JedWesley-Smith You're right, BigInts are allocated; there's no way to avoid that in a functional solution that adds these numbers. But according to my tests Iterator gets to very high Fibonacci numbers without any problem, while the solutions using Stream lead to out-of-memory errors, even if the reference to the beginning of the stream is not kept. Maybe with an ideal compiler there would be no difference between using Stream and Iterator, but in practice it looks like Iterator is better both in terms of memory consumption and speed.

[Jarek Przygódzki]

A slightly cleaner version: val fib: Stream[Int] = 0 #:: 1 #:: (fib zip fib.tail).map { case(a, b) => a + b }