// 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)
}
}