CODEWITHSUNDEEP
scalafibonacci
user2947615
user2947615

Reputation: 497

Fibonnaci Sequence fast implementation

I have written this function in Scala to calculate the fibonacci number given a particular index n:

 def fibonacci(n: Long): Long = {
 if(n <= 1) n
 else
   fibonacci(n - 1) + fibonacci(n - 2)     
}

However it is not efficient when calculating with large indexes. Therefore I need to implement a function using a tuple and this function should return two consecutive values as the result.

Can somebody give me any hints about this? I have never used Scala before. Thanks!

Upvotes: 1

Views: 451

Answers (4)

dimitrisli
dimitrisli

Reputation: 21401

Update

Here's another solution again using Streams as below (getting Memoization for free) but a bit more intuitive (aka: without using zip/tail invocation on fibs Stream):

val fibs = Stream.iterate( (0,1) ) { case (a,b)=>(b,a+b)  }.map(_._1)

that yields the same output as below for:

fibs take 5 foreach println

Scala supports Memoizations through Streams that is an implementation of lazy lists. This is a perfect fit for Fibonacci implementation which is actually provided as an example in the Scala Api for Streams. Quoting here:

import scala.math.BigInt
object Main extends App {

  val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { n => n._1 + n._2 }

  fibs take 5 foreach println
}

// prints
//
// 0
// 1
// 1
// 2
// 3

Upvotes: 0

DaoWen
DaoWen

Reputation: 33019

Here's a simple tail-recursive solution:

def fibonacci(n: Long): Long = {
  def fib(i: Long, x: Long, y: Long): Long = {
    if (i > 0) fib(i-1, x+y, x)
    else x
  }
  fib(n, 0, 1)
}

The solution you posted takes exponential time since it creates two recursive invocation trees (fibonacci(n - 1) and fibonacci(n - 2)) at each step. By simply tracking the last two numbers, you can recursively compute the answer without any repeated computation.

Can you explain the middle part, why (i-1, x+y, x) etc. Sorry if I am asking too much but I hate to copy and paste code without knowing how it works.

It's pretty simple—but my poor choice of variable names might have made it confusing.

  • i is simply a counter saying how many steps we have left. If we're calculating the Mth (I'm using M since I already used n in my code) Fibonacci number, then i tells us how many more terms we have left to calculate before we reach the Mth term.
  • x is the mth term in the Fibonacci sequence, or Fm (where m = M - i).
  • y is the m-1th term in the Fibonacci sequence, or Fm-1 .

So, on the first call fib(n, 0, 1), we have i=M, x=0, y=1. If you look up the bidirectional Fibonacci sequence, you'll see that F0 = 0 and F-1 = 1, which is why x=0 and y=1 here.

On the next recursive call, fib(i-1, x+y, x), we pass x+y as our next x value. This come straight from the definiton:

Fn = Fn-1 + Fn-2

We pass x as the next y term, since our current Fn-1 is the same as Fn-2 for the next term.

On each step we decrement i since we're one step closer to the final answer.

Upvotes: 1

Chthonic Project
Chthonic Project

Reputation: 8366

I am assuming that you don't have saved values from previous computations. If so, it will be faster for you to use the direct formula using the golden ratio instead of the recursive definition. The formula can be found in the Wikipedia page for Fibonnaci number:

floor(pow(phi, n)/root_of_5 + 0.5)

where phi = (1 + sqrt(5)/2).

I have no knowledge of programming in Scala. I am hoping someone on SO will upgrade my pseudo-code to actual Scala code.

Upvotes: 0

Christian Fries
Christian Fries

Reputation: 16932

This question should maybe go to Mathematics.

There is an explicit formula for the Fibonacci sequence. If you need to calculate the Fibonacci number for n without the previous ones, this is much faster. You find it here (Binet's formula): http://en.wikipedia.org/wiki/Fibonacci_number

Upvotes: 2

Related Questions