Find square root of a number

Given a number N, find its square root upto a precision P.

squareRoot(N,P) = k

Example:

squareRoot(3,2) = 1.73

squareRoot(25,3) = 5.0

Brute Force Approach

The brute force approach is to iterate over the natural numbers from 1 to N and check if their squares are equal to N. This approach will suffice if N is a perfect square. But if N is not a perfect square, the brute force approach is carried out in two steps,

1. While iterating from 1 to N, find the closest integer such that (closest+1)*(closest+1) is greater than N,

int close = 1;

for (int i=1;i<=N;i++)
{ // break if i*i is greater than N
    If( i*i > N ){
        close = i-1;
        break;
    }
}
// Check if N is a perfect square. If it is, then return close.
if(close*close == N) return close;

2. Now iterate for the fractional part upto the given precision P as shown below.

double increment = 0.1
for(int i=0;i<P;i++)
{ // increment close until “close” is greater than N.

    while(close*close<=N){
        close += increment;
    }
    // when close*close is greater than N, remove the latest increment.
    close -= increment;
    // Go for further precision
    increment /= 10;

}
return close;

The time complexity of the above approach is the sum of the complexity of the integral part and the fractional part i.e  $O(N) + ≍O(10P)$.

Using Binary Search

The efficient approach is to use a binary search between 1 to N. The below thumb rule is useful to know if the problem can be solved using a binary search.

Thumb Rule: If a function f increases or decreases at every point on increasing or decreasing the input value N, then probably we can use binary search to solve those problems. In our case, the function is f(N) = sqrt(N) and on increasing/decreasing N, f(N) also increases/decreases.

Eg.

f(1) = 1
f(3) = 1.73
f(9) = 3

And so on.

Steps/Algorithm  to follow:

1. Initialize low = 1 and high = N.

2. Convert P to the order of its precision value in decimal format. For eg. if P=2, the order is 0.01. Assign its value to a variable prec.

3. While low is less than or equal to high, repeat steps from 4 to 7.

4. Find the middle number between low and high i.e. mid and assign it to a variable sqrt.

5. Check if mid*mid is close enough to N such that their absolute difference error is less than prec.

6. If step 5 condition is true, exit the loop and go to step 8.

7. Check if mid*mid exceeds N. If it is, then reduce high to mid. Or, if mid*mid is less than N, then increase low to mid.

8. Convert sqrt such that it has the exact precision after the decimal point. (In many cases, sqrt will have more accurate value than desired. Therefore, this step is necessary.)

9. Return sqrt.

• C++
• Python
• Java

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

double squareRoot(double N, int P)
{
    double low = 1;
    double high = N;
    double prec = pow(10, -P);
    double sqrt = 1;

    while (low <= high)
    {
        double mid = (low + high) / 2;
        sqrt = mid;

        // if the difference between square of current mid and N is less than precision, then break.
        if (fabs(mid * mid - N) <= prec)
            break;

        // decrementing high if answer lies between current low and mid
        else if (mid * mid > N)
            high = mid;

        // incrementing low if answer lies between mid and current high.
        else
            low = mid;
    }
    return round(sqrt * pow(10, P)) / pow(10, P);
}

# Square Root Method
def squareRoot(N, P):
    low = 1
    high = N
    prec = 10 ** (-P)

    while low <= high:
        mid = (low + high) / 2
        sqrt = mid

        # if the difference between square of current mid and N is less than precision, then break.
        if abs(mid * mid - N) <= prec:
            break

        # decrementing high if answer lies between current low and mid
        elif mid * mid > N:
            high = mid

        # incrementing high if answer lies between mid and current high.
        else:
            low = mid
    return round(sqrt, P)

double squareRoot(double N, int P) {
  double low = 1;
  double high = N;
  double prec = Math.pow(10, -P);
  double sqrt = 1;

  while (low <= high) {
    double mid = (low + high) / 2;
    sqrt = mid;

    // if the difference between square of current mid and N is less than precision
    // value, then break.
    if (Math.abs(mid * mid - N) <= prec)
      break;

    // decrementing high if answer lies between current low and mid
    else if (mid * mid > N)
      high = mid;

    // incrementing high if answer lies between mid and current high.
    else
      low = mid;
  }
  return Math.round(sqrt * Math.pow(10, P)) / Math.pow(10, P);
}

The time complexity of the binary search approach is $O(log2(N) + log2(10P))$.