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

by

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.

More Related Contents:

  1. How do I make a function involving futures tail recursive?
  2. Scala: Write a function to swap a number in place without using temporary variables
  3. What is a “context bound” in Scala?
  4. Understanding implicit in Scala
  5. Do scala constructor parameters default to private val?
  6. Composing Option with List in for-comprehension gives type mismatch depending on order
  7. What do all of Scala’s symbolic operators mean?
  8. NullPointerException in Scala Spark, appears to be caused be collection type?
  9. How to define a custom aggregation function to sum a column of Vectors?
  10. Better way to convert a string field into timestamp in Spark
  11. If an Int can’t be null, what does null.asInstanceOf[Int] mean?
  12. Stream vs Views vs Iterators
  13. How to use Scala’s this typing, abstract types, etc. to implement a Self type?
  14. No configuration setting found for key ‘akka.version’
  15. Run custom task automatically before/after standard task
  16. scala – Any vs underscore in generics
  17. How to force IntelliJ IDEA to reload dependencies from build.sbt after they changed?
  18. Scala : fold vs foldLeft
  19. How do I access default parameter values via Scala reflection?
  20. How does the fibonacci recursive function “work”?
  21. In scala 2 or 3, is it possible to debug implicit resolution process in runtime?
  22. How do I cast a variable in Scala?
  23. Why to use empty parentheses in Scala if we can just use no parentheses to define a function which does not need any arguments?
  24. Scala: Parallel collection in object initializer causes a program to hang
  25. Why does Scala support shadow variables? [closed]
  26. Differences between these three ways of defining a function in Scala
  27. How can I connect to a postgreSQL database into Apache Spark using scala?
  28. How to serve uploaded files in Play!2 using Scala?
  29. Scalaz Bind[Seq] typeclass
  30. How to instantiate an instance of type represented by type parameter in Scala

Leave a Comment