Algorithm notes on the back of used envelopes bound in a ring binder

• 1. Go to a brute force solution
• 2. Go to Newton's method aka. Babylonian method solutions
• 3. Go to digit-by-digit calculation solutions
• 4. Go to a bisection method solution
• 5. Go to Maclaurin series approximation

1. Brute force

use std::time::Instant;

fn square_root_brute(aa: u32) -> u32 {
    let mut a = 0u32;
    while a as u64 * a as u64 <= aa as u64 {
        a += 1;
    }
    a - 1
}

fn main() {
    let timer = Instant::now();
    for i in 0u32..100 {
        assert_eq!((i as f64).sqrt() as u32, square_root_brute(i));
    }
    for i in 2_147_395_500u32..2_147_395_601 {
        assert_eq!((i as f64).sqrt() as u32, square_root_brute(i));
    }
    println!("Time elapsed {:?}", timer.elapsed());
}

• 1. Go to a brute force solution
• 2. Go to Newton's method aka. Babylonian method solutions
• 3. Go to digit-by-digit calculation solutions
• 4. Go to a bisection method solution
• 5. Go to Maclaurin series approximation

2. Newton's method

• https://tour.golang.org/flowcontrol/8

use std::time::Instant;

fn square_root_newton(a: u32) -> u32 {
    let mut x = 1f32;
    let mut x_next: f32;
    loop {
        x_next = (x + a as f32 / x) / 2f32;
        if (x - x_next).abs() < 0.1 {
            break x_next as u32;
        }
        x = x_next;
    }
}

fn main() {
    let timer = Instant::now();
    for i in 0u32..100 {
        assert_eq!((i as f32).sqrt() as u32, square_root_newton(i));
    }
    for i in 2_147_395_500u32..2_147_395_601 {
        assert_eq!((i as f32).sqrt() as u32, square_root_newton(i));
    }
    println!("Time elapsed {:?}", timer.elapsed());
}

use std::time::Instant;

fn square_root_newton(a: u32) -> u32 {
    let mut x = 1f64;
    let mut x_next: f64;
    loop {
        x_next = (x + a as f64 / x) / 2f64;
        if (x - x_next).abs() < 0.1 {
            break x_next as u32;
        }
        x = x_next;
    }
}

fn main() {
    let timer = Instant::now();
    for i in 0u32..100 {
        assert_eq!((i as f64).sqrt() as u32, square_root_newton(i));
    }
    for i in 2_147_395_500u32..2_147_395_601 {
        assert_eq!((i as f64).sqrt() as u32, square_root_newton(i));
    }
    println!("Time elapsed {:?}", timer.elapsed());
}

use std::time::Instant;

fn square_root_newton(a: u32) -> u32 {
    let mut x = 1u64;
    let mut x_next: u64;
    loop {
        x_next = (x + a as u64 / x) / 2;
        if x == x_next || x_next * x_next <= a as u64 {
            break x_next as u32;
        }
        x = x_next;
    }
}

fn main() {
    let timer = Instant::now();
    for i in 0u32..100 {
        assert_eq!((i as f64).sqrt() as u32, square_root_newton(i));
    }
    for i in 2_147_395_500u32..2_147_395_601 {
        assert_eq!((i as f64).sqrt() as u32, square_root_newton(i));
    }
    println!("Time elapsed {:?}", timer.elapsed());
}

• The Go Playground

• 1. Go to a brute force solution
• 2. Go to Newton's method aka. Babylonian method solutions
• 3. Go to digit-by-digit calculation solutions
• 4. Go to a bisection method solution
• 5. Go to Maclaurin series approximation

3. Digit-by-digit calculation

use std::time::Instant;

fn subtract_largest_block_from_carry(carry: &mut u32, divisor: &mut u32, x: &mut u32) {
    for i in (0u32..10).rev() {
        let block = (*divisor + i) * i;
        if block > *carry {
            continue;
        }
        *carry -= block;
        *divisor += i * 2;
        *x += i;
        break;
    }
}

fn square_root_digit_by_digit(mut a: u32) -> u32 {
    let mut digits = vec![];
    while a > 0 {
        digits.push(a % 100);
        a /= 100;
    }
    let (mut x, mut divisor, mut carry) = (0u32, 0u32, 0u32);
    for &n in digits.iter().rev() {
        carry = carry * 100 + n;
        divisor *= 10;
        x *= 10;
        subtract_largest_block_from_carry(&mut carry, &mut divisor, &mut x);
    }
    x
}

fn main() {
    let timer = Instant::now();
    for i in 0u32..100 {
        assert_eq!((i as f64).sqrt() as u32, square_root_digit_by_digit(i));
    }
    for i in 2_147_395_500u32..2_147_395_601 {
        assert_eq!((i as f64).sqrt() as u32, square_root_digit_by_digit(i));
    }
    println!("Time elapsed {:?}", timer.elapsed());
}

use std::time::Instant;

fn square_root_digit_by_digit(mut a: u32) -> u32 {
    let mut x = 0u32;
    let mut bit: u32 = 0b01000000000000000000000000000000;
    while bit > a {
        bit >>= 2;
    }
    while bit != 0 {
        let block = x + bit;
        x >>= 1;
        if a >= block {
            a -= block;    
            x += bit;
        }
        bit >>= 2;
    }
    x
}

fn main() {
    let timer = Instant::now();
    for i in 0u32..100 {
        assert_eq!((i as f64).sqrt() as u32, square_root_digit_by_digit(i));
    }
    for i in 2_147_395_500u32..2_147_395_601 {
        assert_eq!((i as f64).sqrt() as u32, square_root_digit_by_digit(i));
    }
    println!("Time elapsed {:?}", timer.elapsed());
}

• 1. Go to a brute force solution
• 2. Go to Newton's method aka. Babylonian method solutions
• 3. Go to digit-by-digit calculation solutions
• 4. Go to a bisection method solution
• 5. Go to Maclaurin series approximation

4. Bisection method

use std::time::Instant;
use std::cmp::Ordering;

fn square_root_bisection(a: u32) -> u32 {
    let (mut top, mut bottom) = (a.clone() as f64, 0f64);
    loop {
        if top - bottom < 0.00001 {
            break top as u32;
        }
        let median = bottom + (top - bottom) / 2f64;
        match (&(a as f64)).partial_cmp(&(median * median)).unwrap() {
            Ordering::Less => top = median,
            Ordering::Equal => return median as u32,
            Ordering::Greater => bottom = median,
        }
    }
}

fn main() {
    let timer = Instant::now();
    for i in 0u32..100 {
        assert_eq!((i as f64).sqrt() as u32, square_root_bisection(i));
    }
    for i in 2_147_395_500u32..2_147_395_601 {
        assert_eq!((i as f64).sqrt() as u32, square_root_bisection(i));
    }
    println!("Time elapsed {:?}", timer.elapsed());
}

• 1. Go to a brute force solution
• 2. Go to Newton's method aka. Babylonian method solutions
• 3. Go to digit-by-digit calculation solutions
• 4. Go to a bisection method solution
• 5. Go to Maclaurin series approximation

5. Maclaurin series approximation

It's also applicable for logarithm