Calculating square roots using binary search

Question

I'm trying to find the square root of a number (num) using binary search in Rust. I'm new to Rust, but I've done quite a bit of programming in other languages, though. I'm more interested in how to generally improve this, as I'm not familiar with Rust best-practices and simaler than I am about the algorithm, although I don't mind advice on that*. Here's how this generally works:

1. Take the number we're trying to find the root of
2. Set current_guess to 1/2 of the number to take the square root of
3. While current_guess squared is not within a specified tolorance, repeat the following steps until it is within the desired tolorance:
4. Calculate the difference between the current guess squared and the input number. That is how far off our number squared is from the target number
5. If our number squared is within the tolorance, done. Else, if our number is two low, multiply it by 1.5 to make it bigger. If it is too high, divide it by two. Repeat until solved.

And of course the code. It is ran with a normal cargo run.

fn main() {
    println!("The square root of 16129 is approximately {}", sqrt(16129.0, 0.01));
}

fn sqrt(num: f64, tolorance: f64) -> f64 {
    // the number we will try next
    let mut current_guess = num / 2.0;

    // how far off our current guess is
    let mut current_difference: f64;
    loop {
        current_difference = current_guess.powi(2) - num;

        if current_difference.abs() <= tolorance {
            // if our answer is within the accepted tolorance range
            return current_guess;
        } else if current_difference < tolorance {
            // if our current guess is too small
            current_guess *= 1.5;
        } else if current_difference > tolorance {
            // if our current guess is too big
            current_guess *= 0.5;
        }
    }
}

The current output of my code is

   Compiling square-root v0.1.0 (C:\[redacted]\square-root)
    Finished dev [unoptimized + debuginfo] target(s) in 1.65s
     Running `target\debug\square-root.exe`
127.00000413730865

And that is the right answer. Of course, I could make it more precise by making the tolerance smaller. *I have nothing against making that part better, just my goal was to get a feel for Rust more than finding square roots. So I'm more interested in good ways to improve the code, but I don't mind critiques of the algorithm.

Answer 1

You're not using binarysearch here, but a form of Newton's Method. This will work, and is the appropriate algorithm for floating point numbers, but unlike binarysearch, it takes no advantage of the sorted nature of the number space you're searching in.

Here's how binarysearch is described in Wikipedia:

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful

You choose a 'pivot', normally in the middle. See if the number you're searching for is greater than the pivot, then repeat the process to the right, if it's smaller, repeat the process on the left. In your case, you would compare with the square of the pivot instead.

Answer 2

fn sqrt(num: f64, tolorance: f64) -> f64 {

It is spelled tolerance

What if num is negative? You should probably panic throw on error or some such.

    // the number we will try next
    let mut current_guess = num / 2.0;

    // how far off our current guess is
    let mut current_difference: f64;
    loop {
        current_difference = current_guess.powi(2) - num;

There's no reason to declare current difference outside of the loop. Instead, just say let current_difference here.

        if current_difference.abs() <= tolorance {
            // if our answer is within the accepted tolorance range
            return current_guess;
        } else if current_difference < tolorance {

I would suggest checking for whether the number is negative or positive here rather than comparing to tolerance.

            // if our current guess is too small
            current_guess *= 1.5;
        } else if current_difference > tolorance {
            // if our current guess is too big
            current_guess *= 0.5;
        }

Multiplying by 1.5 or .5 is unfamiliar to me. It is not obvious to me that this algorithm will converge.

    }
}

Answer 3

Not familiar with rust but there are a few improvements. when writing the code usually we go for the happy scenario, in the case of enterprise applications users may enter parameters which are not in our happy scenario, for example calculating square root of a negative number. thus you need to add validations for given parameters and throw error in case of need.

when multiplying by 1.5 and .5 you can also have that numbers saved as a constant because we do not want hard coded numbers in the code. but of course that's in the case of large-scale apps.