009_power.sio

//@ run-pass
// HumanEval 009: Fast Exponentiation
//
// Compute x^n using binary exponentiation (exponentiation by squaring).
// O(log n) multiplications. Handles non-negative exponents only.

fn power(base: i64, exp: i64) -> i64 with Mut, Div, Panic {
    if exp == 0 { return 1 }
    var result: i64 = 1
    var b = base
    var e = exp
    while e > 0 {
        if e % 2 == 1 {
            result = result * b
        }
        b = b * b
        e = e / 2
    }
    result
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: x^0 = 1
    assert(power(5, 0) == 1)
    assert(power(0, 0) == 1)

    // Test 2: x^1 = x
    assert(power(7, 1) == 7)

    // Test 3: 2^10 = 1024
    assert(power(2, 10) == 1024)

    // Test 4: 3^5 = 243
    assert(power(3, 5) == 243)

    // Test 5: 5^3 = 125
    assert(power(5, 3) == 125)

    // Test 6: 2^20 = 1048576
    assert(power(2, 20) == 1048576)

    // Test 7: 10^6 = 1000000
    assert(power(10, 6) == 1000000)

    // Test 8: 1^anything = 1
    assert(power(1, 100) == 1)

    // Test 9: 0^positive = 0
    assert(power(0, 5) == 0)

    println("009_power: ALL TESTS PASSED")
    0
}