cesartl

fun fibobacciMemo(n: BigInteger): BigInteger {
    var nMinus2 = BigInteger.ZERO
    var nMinus1 = BigInteger.ONE
    if (n <= BigInteger.ONE) {
        return n
    }
    var i = BigInteger.ZERO
    while (i < n) {
        i += BigInteger.ONE
        nMinus1 += nMinus2

cesartl

object Fibonacci {
    private val companionMatrix = Matrix22(0, 1, 1, 1)

    fun fibonacciFast(n: BigInteger): BigInteger {
        val m = Matrix22.monoid().run {
            combineTimes(companionMatrix, n)
        }
        return m.x01
    }
}

cesartl

interface Matrix22Monoid : Monoid<Matrix22> {
    override fun empty(): Matrix22 = Matrix22.identity
    override fun Matrix22.combine(b: Matrix22): Matrix22 {
        val (l00, l01, l10, l11) = this
        val (r00, r01, r10, r11) = b
        return Matrix22(
            l00 * r00 + l01 * r10,
            l00 * r01 + l01 * r11,
            l10 * r00 + l11 * r10,
            l10 * r01 + l11 * r11

cesartl

data class Matrix22(
    val x00: BigInteger,
    val x01: BigInteger,
    val x10: BigInteger,
    val x11: BigInteger
) {
    companion object {
        val identity = Matrix22(BigInteger.ONE, BigInteger.ZERO, BigInteger.ZERO, BigInteger.ONE)
    }
}

cesartl

/**
 * Exponentiation by squaring
 * https://en.wikipedia.org/wiki/Exponentiation_by_squaring
 */
fun <T> Monoid<T>.combineTimes(m: T, k: BigInteger): T {
    if (k == BigInteger.ZERO) {
        return empty()
    }
    if (k == BigInteger.ONE) {
        return m

cesartl

public interface Monoid<A> : Semigroup<A>
    public abstract fun empty(): A
}

cesartl

class FooSemigroup : Semigroup<Foo>{
  override fun Foo.combine(f: Foo): Foo{
      return ...
  }
}

cesartl

public class Foo extends Semigroup<Foo>{
  @Override
  public Foo combine(Foo other){
    return ...
  }

cesartl

interface HasBinaryOp<T>{
  T combine(T other);
  
  T empty();
}

cesartl

public interface Semigroup<A> {
    public abstract fun A.combine(b: A): A
}