How can I get Fibonacci(n) in an efficient way with Scala Actor?

Question

The algorithm is just like this.

    def fib(x: Int): BigInt = {
        x match {
            case 1 => BigInt(1)
            case 2 => BigInt(1)
            case x => fib(x-1) + fib(x-2)
        }
    }

I try to make the algorithm parallel with Actor in Scala. But my code is extremely slow compare with the one without Actor!

Is there a good way to make it work?

Answer 1

For not large size of n, the serial code will always be faster (Much much faster in cases of tail recursion). This is because calling a new function will be faster than starting a new actor. Plus there will contention among threads and context switches.

In the below code, I start a new actor for every n > 2. There can be many optimized ways, but I simply using the recurrence T(n) = T(n-1) + T(n-2) to serial one.

import akka.actor.Actor
import akka.actor.Props
import akka.actor.ActorSystem
import akka.event.Logging
import akka.actor.ActorRef
import akka.routing.RoundRobinRouter

object Fib extends App {

trait Fib
case class N(val n: Int) extends Fib

case class Ans(n: Int)
class FibN(listen: ActorRef) extends Actor {

var numOfResults = 0;
var ans = 0;
val log = Logging(context.system, this)

def receive = {
  case N(x) => {
    //println(self.path+"-Message N(x) "+x)
    val others = context.actorOf(Props(new FibN(self)).withRouter(RoundRobinRouter(2)), name = "Fibn:" + x)
    if(x==1 || x==2)
      listen ! new Ans(1)
    else if(x>2){
      others ! new N(x-1)
      others ! new N(x-2)
    }


  }

  case Ans(x) => {
    //println(self.path+" Ans(x) "+x+" numOfResults "+numOfResults+" from "+sender.path)
    numOfResults += 1
    ans = ans + x;
    if (numOfResults == 2){
      //println(self.path+"sending back to sender "+listen.path+" numOfResults "+numOfResults)
      listen ! Ans(ans)
    }


  }
  case _ => println(self.path+"Not valid")

}

}


class Listener extends Actor{
val log = Logging(context.system, this)
var st:Long = 0;
def receive = {
  case Ans(x) => {
    println(self.path+"\n\nAns is "+x+" time taken: "+(System.currentTimeMillis() - st))
    context.system.shutdown
  }
  case N(x) => {
    println(self.path+" Message Received "+x)
    val actor = context.actorOf(Props(new FibN(self)),"FibN")
    st = System.currentTimeMillis()
    actor ! new N(x)
  }
  case _ => println(self.path+" Invalid request")
 }
}

val system = ActorSystem("Fibanoccia")
val listener = system.actorOf(Props[Listener],"Listener")
listener ! new N(25)
}

This as expected was much slower. Unless n is very large, actor will always be slower for reasons mentioned. For larger 'n', this can be decomposed.

Answer 2

I don't know Scala but would you like to try this?

def fib(a:BigInt, b:BigInt, n: Int): BigInt = {
    n match {
        case 1 => BigInt(a) + BigInt(b)
        case x => fib(b, a + b, n - 1)
    }
}

I don't know the syntax but this concept may help. Using 0 and 1 as first two arguments. It is an O(n) algorithm.

And why not use fast power optimized matrix multiplication which has an excellent time complexity of O(log(n))?