multiple ways to compute the fiboonacci sequence

fibonacci.kt

package gabrieljones

import com.google.common.math.BigIntegerMath
import java.math.BigDecimal
import java.math.BigInteger
import java.math.MathContext
import java.math.RoundingMode
import kotlin.coroutines.cancellation.CancellationException

fun main() {

  val fibonacciLazy: Sequence<BigInteger> = generateSequence(BigInteger.ZERO to BigInteger.ONE) { (a, b) -> b to a + b }.map { it.first }

  val fibonacciLambdas: Sequence<(Int)->BigInteger> = sequenceOf(
//    ::fibonacci,
    ::fibonacciMemoized,
    { fibonacciMemoizedTailRecursion(it) },
    { fibonacciLazy.drop(it +1).first() },
    { fibonacciGoldenRatio(it+1) },
  )
  val o = 3
  (o..o+10).forEach { n ->
    fibonacciLambdas
      .map {runCatchingNonFatal { it(n) } }
      .toList()
      .forEach { it.fold(
        {fi -> println("${BigIntegerMath.log10(fi, RoundingMode.HALF_EVEN)} $fi") },
        {e -> println("❌ $e") },
      ) }
  }
}

fun fibonacci(n: Int): BigInteger = if (n < 2) BigInteger.ONE else fibonacci(n - 1) + fibonacci(n - 2)

val memo = arrayListOf(BigInteger.ONE, BigInteger.ONE)

fun fibonacciMemoized(n: Int): BigInteger =
  if (n < memo.size) memo[n]
  else (fibonacciMemoized(n - 1) + fibonacciMemoized(n - 2)).also(memo::add)

val memoTR = arrayListOf(BigInteger.ZERO, BigInteger.ONE)

fun fibonacciMemoizedTailRecursion(n: Int, a: BigInteger = BigInteger.ONE, b: BigInteger = BigInteger.ONE): BigInteger =
  if (n < memoTR.size) memoTR[n]
  else {
    memoTR.add(b) //broken as this has to be called after the recursive call, but that then breaks the tail recursion
    fibonacciMemoizedTailRecursion(n - 1, b, a + b)
  }

val half = BigDecimal.valueOf(0.5)

fun fibonacciGoldenRatio(n: Int): BigInteger {
  val mc = MathContext((n / 4).coerceAtLeast(34), RoundingMode.HALF_EVEN)
  val sqrt5: BigDecimal = BigDecimal.valueOf(5).sqrt(mc)
  val phi: BigDecimal = sqrt5.add(BigDecimal.ONE).divide(BigDecimal.valueOf(2))
  return phi
    .pow(n)
    .divide(sqrt5, mc)
    .add(half)
    .toBigInteger()
}

inline fun <R> runCatchingNonFatal(block: () -> R): Result<R> {
  return try {
    Result.success(block())
  }
  catch (t: Throwable) {
    when (t) {
      // VirtualMachineError includes OutOfMemoryError and other fatal errors
      is VirtualMachineError, is ThreadDeath, is InterruptedException, is LinkageError, is CancellationException -> throw t
      else -> Result.failure(t)
    }
  }
}