# 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^{14}.

So, if you have to find a floor of square root of. say, 10^{18}, 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^{15}, 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 numberwhile (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 numberwhile (i+1)*(i+1) <= num {i+=1;}return i;}// Driver Codefn 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 ^{18}** in logarithmic time complexity.

### Algorithm

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

**Note :** I have taken 1.1×10^{9} as high because it can find the square root of all the numbers upto **10 ^{18}**, 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 itif 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 dividemid = (high+low)>>1;let mid_square = mid*mid;// If mid_square if equal to number, return midif 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 -1if 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**