Integer ( Floor ) square root

of a whole number and program to find it in Rust Language

Introduction

Many times, we have to compute the integer or floor value of square root of a given very large number instead of exact square root.

You may argue that we can find the square root of a number using default sqrt() method, and then take its floor.

But, there is a catch. f64 type uses some bits to represent the floating digits. So, it reduces the accuracy of square roots of numbers greater than 10¹⁴.

So, if you have to find a floor of square root of. say, 10¹⁸, you will simply get inaccurate answers. This is a frequent cause of failing testcases in many questions, especially if 10 test cases are passing, and 11th gives wrong answer in solution involving square root of number >= 10¹⁵, this might be the issue.

So, in this article, we will see how to find Floor of square root of a number in Logarithmic time complexity using binary search in Rust Language.

Naive approach

Naive Approach would be to linearly check each and every number from 1 till we find a number whose square root is greater than the given number.

This will take O( sqrt(n) ) time complexity. Function using this approach is

fn square_root(num:usize) -> usize{
    let mut i = 0;

    // If the number is 0 or 1,
    if num <=1 {
        return num;
    }

    // Increase i, till square of i+1 is less than or equal to number
    while (i+1)*(i+1) <= num {
        i+=1;
    }
    return i;
}

Program With driver code

fn square_root(num:usize) -> usize{
    let mut i = 0;

    // If the number is 0 or 1,
    if num <=1 {
        return num;
    }

    // Increase i, till square of i+1 is less than or equal to number
    while (i+1)*(i+1) <= num {
        i+=1;
    }
    return i;
}

// Driver Code

fn main() {
    println!("{}", square_root(899));
    println!("{}", square_root(900));
    println!("{}", square_root(901));
}

Output

29
30
30

Time Complexity : O( n )
Space Complexity : O( 1 )

Efficient Binary Search Approach

We can optimize the above approach using binary search, and find the integer square root in Logarithmic time instead of Linear time.

Below algorithm can find the integer square root of numbers upto 10¹⁸ in logarithmic time complexity.

Algorithm

1. If the number is 0 or 1, return that number.
2. Take starting point ( or low ) to be 1 and ending point ( or high ) to be 1.1×10⁹ .
3. Find the mid-point of high and low. If mid×mid is equal to the number, return the mid.
4. If mid is less than the number, store the value of the mid, and set the low to mid+1.
5. Else, Set the high to mid -1.
6. Repeat steps 3 to 5 till high is not equal to low.
7. If high is equal to low, return the stored value of mid in step 4.

Note : I have taken 1.1×10⁹ as high because it can find the square root of all the numbers upto 10¹⁸, without overflowing.

Function

Here is the function using above algorithm

fn square_root(num:usize) -> usize{

    // If number is less than or equal to 1, return it
    if num<=1 { return num }

    // Take high and low, mid and ans .
    let mut low : usize = 1;
    let mut high : usize = 1_100_000_000;

    let mut mid;
    let mut ans = 0;


    while high>=low {
        // Right shift by 1 is equivalent to divide
        mid = (high+low)>>1;

        let mid_square = mid*mid;

        // If mid_square if equal to number, return mid
        if mid_square == num { return mid }

        // If mid_square is less than number, set ans to mid
        // And low to mid+1
        // Else, set high to mid -1
        if mid_square < num {
            ans = mid;
            low = mid+1;
        }else {
            high = mid-1;
        }
    }

    // In case the given number is not a prefect square,
    // Return stored ans, because it is floor of square root.
    return ans;
}

Use the same driver code.

Output

29
30
30

Time Complexity : O( log( n ) )
Space Complexity : O( 1 )

Note : Similarly, you can use the same program for Cube Root and other higher degree roots.

Conclusion

Many times, we have to compute the integer or floor value of square root of a given very large number instead of exact square root.

The default sqrt() method might become inaccurate for such large numbers. Hence, we have to use binary search method to compute such large square roots.

In this article, we saw how to find the integer or floor square root of very large number in logarithmic time complexity using binary search in Rust Language.

Here is the optimized function for easy access

fn square_root(num:usize) -> usize{
    if num<=1 { return num }
    let mut l : usize = 1;
    let mut h : usize = 1_100_000_000;
    let mut m;
    let mut ans = 0;
    while h>=l {
        m = (h+l)>>1;
        let m_s = m*m;
        if m_s == num { return m }
        if m_s < num { ans = m ; l = m+1; }
        else { h = m-1; }
    }
    return ans;
}

I suggest you to include it in your template.

Thank You