ExpSquaring.kt

/**
 * 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
    }
    var y = empty()
    var x = m
    var n = k
    while (n > BigInteger.ONE) {
        if (n.testBit(0)) {
            // n is odd
            y = y.combine(x)
            x = x.combine(x)
            n -= BigInteger.ONE
        } else {
            // n is even
            x = x.combine(x)
        }
        n /= BigInteger.TWO
    }
    return x.combine(y)
}