Logarithmic-complexity power

logpow.rs

fn logpow(base: u32, exp: u32) -> u32 {
    let mut restexp = exp;
    let mut intlog = 0_u32;

    while restexp > 1 {
        restexp /= 2;
        intlog += 1;
    }

    restexp = exp - 2_u32.pow(intlog);
    
    let mut res = base;
    
    for _ in 0..intlog {
        res = res.pow(2);
    }
        
    for _ in 0..restexp {
        res *= base;
    }

    res
}

fn main() {
    assert_eq!(2_u32.pow(4), logpow(2, 4));
    assert_eq!(2_u32.pow(3), logpow(2, 3));


    for base in 1_u32..5_u32 {
        for exp in 1_u32..8_u32 {
            assert_eq!(base.pow(exp), logpow(base, exp));
        }
    }
}