Algorithms based on the Fibonacci series implementation

gistfile1.txt

// Algorithms based on the Fibonacci series implementation: 1,1,2,3,5,8,13,21,34,55,...

def fib(n: Int): BigInt = {
  if (n < 1) 0 
  else if (n < 3) 1 
  else fib(n-1) + fib(n-2)
}

// Exponential (very slow, for n> 40 we can see that)

//n      32 33 34 35 36 37   38 39  40  41   42   43   44  45
//t (ms) 13 20 33 52 83 135 217 348 566 914 1479 2385 3867 6243

// Not recursive algorithm works fast:

def fib(n: Int): BigInt = {
  if (n < 1) 0
  else if (n < 3) 1
  else {
    var f1,f2 = BigInt(1)
    for(i <- 1 to n-2) {
      val f = f1+f2
      f1 = f2
      f2 = f
    }
    f2
  }
}

// Recursive (list generation, works fast)

def fib(n: Long) = {
  def go(l: List[BigInt]): List[BigInt] = {
    val s = l.size
    s match {
      case 0 | 1 => go(List(1,1))
      case _ => if (s < n) go(l:+(l(s-1)+l(s-2))) else l
    }
  }
  go(Nil)
}

// A list of numbers not greater than b: BigInt

def fib(b: BigInt) = {
  def go(l: List[BigInt]): List[BigInt] = {
    val s = l.size
    s match {
      case 0 | 1 => go(List(1,1))
      case _ => {
        val next = l(s-1)+l(s-2)       
        if (next > b) l else go(l:+next)
      }
    }
  }
  go(Nil)
}

// The infinite series of Fibonacci numbers (fast)

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

  /* Haskell ghci
    let f n = if n < 3 then 1 else f(n-1) + f(n-2)
    let fb = [f x | x <- [1..]]
  */