extract_sqrt.rs

fn extract_sqrt(mut n: u64) -> (u64, u64) {
    let mut blocks = [0u8; 32];
    let mut i = 0;
    let mut ret = 0u64;
    while n != 0 {
        blocks[i] = (n & 0b11) as u8;
        n >>= 2;
        i += 1;
    }
    let mut q = 0;
    let mut a = 0;
    let mut r = 0;
    let mut z = 0u64;
    while i != 0 {
        i -= 1;
        z = (z - r) * 4 + (blocks[i] as u64);
        q = (q * 2 + a) + a;
        for a_ in 0..0b11 {
            if z < (q * 2 + a_) * a_ {
                a = a_ - 1;
                break;
            }
        }
        r = (q * 2 + a) * a;
        ret = ret * 2 + a;
    }
    (ret, z - r)
}

fn main() {
    assert_eq!(extract_sqrt(5), (2, 1));
    assert_eq!(extract_sqrt(10), (3, 1));
    assert_eq!(extract_sqrt(25), (5, 0));
}