fineconstant / dynamic-programming-jmh-jvm Goto Github PK

// Improved implementation of Fast doubling method, borrowed from here:
// https://www.nayuki.io/res/fast-fibonacci-algorithms/FastFibonacci.java
object FibonacciDoubling {
  import java.math.BigInteger

  def apply(n: Int): BigInt = {

    @tailrec
    def _fibonacciSmall(n: Int, hb: Int, nMinusTwo: Long, nMinusOne: Long): Long = {
      hb match {
        case 0 => nMinusTwo
        case _ =>
          val a = nMinusTwo * ((nMinusOne << 1) - nMinusTwo)
          val b = nMinusTwo * nMinusTwo + nMinusOne * nMinusOne
          n & hb match {
            case 0 => _fibonacciSmall(n, hb >>> 1, a, b)
            case _ => _fibonacciSmall(n, hb >>> 1, b, a + b)
          }
      }
    }

    @tailrec
    def _fibonacciLarge(n: Int, hb: Int, nMinusTwo: BigInteger, nMinusOne: BigInteger): BigInteger = {
      hb match {
        case 0 => nMinusTwo
        case _ =>
          val a = nMinusTwo.multiply(nMinusOne.shiftLeft(1).subtract(nMinusTwo))
          val b = nMinusTwo.multiply(nMinusTwo).add(nMinusOne.multiply(nMinusOne))
          n & hb match {
            case 0 => _fibonacciLarge(n, hb >>> 1, a, b)
            case _ => _fibonacciLarge(n, hb >>> 1, b, a.add(b))
          }
      }
    }

    val hb = Integer.highestOneBit(n)
    if (n <= 92) _fibonacciSmall(n, hb, 0L, 1L)
    else _fibonacciLarge(n, hb, BigInteger.ZERO, BigInteger.ONE)
  }
}