What is the fastest way to write Fibonacci functio

问题:

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?

回答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.

回答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.

回答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.

回答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) + " "))
   }
}

回答5:

A little simpler tail Recursive solution that can calculate Fibonacci for large values of n. The Int version is faster but is limited, when n > 46 integer overflow occurs

def tailRecursiveBig(n :Int) : BigInt = {

      @tailrec
       def aux(n : Int, next :BigInt, acc :BigInt) :BigInt ={

         if(n == 0) acc
          else aux(n-1, acc + next,next)
       }

      aux(n,1,0)
    }

回答6:

This has already been answered, but hopefully you will find my experience helpful. I had a lot of trouble getting my mind around scala infinite streams. Then, I watched Paul Agron's presentation where he gave very good suggestions: (1) implement your solution with basic Lists first, then if you are going to generify your solution with parameterized types, create a solution with simple types like Int's first.

using that approach I came up with a real simple (and for me, easy to understand solution):

  def fib(h: Int, n: Int) : Stream[Int] = { h  #:: fib(n, h + n) }
  var x = fib(0,1)
  println (s"results: ${(x take 10).toList}")

To get to the above solution I first created, as per Paul's advice, the "for-dummy's" version, based on simple lists:

  def fib(h: Int, n: Int) : List[Int] = {
    if (h > 100) {
      Nil
    } else {
      h :: fib(n, h + n)
    }
  }

Notice that I short circuited the list version, because if i didn't it would run forever.. But.. who cares? ;^) since it is just an exploratory bit of code.

回答7:

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

回答8:

The code below is both fast and able to compute with high input indices. On my computer it returns the 10^6:th Fibonacci number in less than two seconds. The algorithm is in a functional style but does not use lists or streams. Rather, it is based on the equality \phi^n = F_{n-1} + F_n*\phi, for \phi the golden ratio. (This is a version of "Binet's formula".) The problem with using this equality is that \phi is irrational (involving the square root of five) so it will diverge due to finite-precision arithmetics if interpreted naively using Float-numbers. However, since \phi^2 = 1 + \phi it is easy to implement exact computations with numbers of the form a + b\phi for a and b integers, and this is what the algorithm below does. (The "power" function has a bit of optimization in it but is really just iteration of the "mult"-multiplication on such numbers.)

    type Zphi = (BigInt, BigInt)

    val phi = (0, 1): Zphi

    val mult: (Zphi, Zphi) => Zphi = {
            (z, w) => (z._1*w._1 + z._2*w._2, z._1*w._2 + z._2*w._1 + z._2*w._2)
    }

    val power: (Zphi, Int) => Zphi = {
            case (base, ex) if (ex >= 0) => _power((1, 0), base, ex)
            case _                       => sys.error("no negative power plz")
    }

    val _power: (Zphi, Zphi, Int) => Zphi = {
            case (t, b, e) if (e == 0)       => t
            case (t, b, e) if ((e & 1) == 1) => _power(mult(t, b), mult(b, b), e >> 1)
            case (t, b, e)                   => _power(t, mult(b, b), e >> 1)
    }

    val fib: Int => BigInt = {
            case n if (n < 0) => 0
            case n            => power(phi, n)._2
    }

EDIT: An implementation which is more efficient and in a sense also more idiomatic is based on Typelevel's Spire library for numeric computations and abstract algebra. One can then paraphrase the above code in a way much closer to the mathematical argument (We do not need the whole ring-structure but I think it's "morally correct" to include it). Try running the following code:

import spire.implicits._
import spire.algebra._

case class S(fst: BigInt, snd: BigInt) {
  override def toString = s"$fst + $snd"++"φ"
}

object S {
  implicit object SRing extends Ring[S] {
    def zero = S(0, 0): S
    def one = S(1, 0): S
    def plus(z: S, w: S) = S(z.fst + w.fst, z.snd + w.snd): S
    def negate(z: S) = S(-z.fst, -z.snd): S
    def times(z: S, w: S) = S(z.fst * w.fst + z.snd * w.snd
                            , z.fst * w.snd + z.snd * w.fst + z.snd * w.snd)
  }
}

object Fibo {

  val phi = S(0, 1) 
  val fib: Int => BigInt = n => (phi pow n).snd

  def main(arg: Array[String]) {
    println( fib(1000000) )
  }

}