Coders Packet

Finding Square Root of a number without using Pre-defined function in C++.

By Rahul Sah

In this article, we are going to learn how to find the square root of a non-perfect square number without using a predefined function in C++.

Square Root of a number

There are various ways of finding the square root of a number(perfect square number/any number). We will be seeing how to find square root using Binary Search with slight modification.
I would suggest go through a binary search algorithm before going forward in this article.

Explanation:

At every step, we find out the mid-value from start(initialized as 0) and end(initialized as number) and then check if it is the square root (in case of perfect square numbers) or whether we are reaching the square root within given precision by comparing current mid-value to previous mid-value (in case the number is not a perfect square).

Steps for finding the Square root :


Using modified binary search to find the square root.
A. Initialize, start = 0, end = number, mid = (start+end)/2.
B. Set prevMid = 0, as the previous mid value.
C. Find diff = absolute difference between prevMid and mid.
D. While mid is not the square root of number (i.e. mid*mid != number) and difference diff is greater than 0.0005,
repeat the following steps:
   i. If mid*mid > number, then the square root will be less than mid. So, set end = mid.
   ii. Else, the square root will be greater than mid. So, set start = mid.
   iii. Set prevMid = mid
   iv. Re-evaluate mid  = (start+end)/2.
   v. Re-evaluate diff from prevMid and mid.

Code 

Both methods are implemented below :

1.Babylanion Method 

2.Binary Search Method

double SquareRoot_1(double n) 
{ 
    double x = n; 
    double y = 1; 
    double e = 0.000001;
    while (x - y > e) { 
        x = (x + y) / 2; 
    	y = n / x; 
    } 
    return x; 
} 
double SquareRoot_2(double number) {
         
        bool isNegative = false;
        if(number < 0) {
            number = -number;
            isNegative = true;
        }
 
        if(number == 1) {
            return number;
        }
    double start,end,mid,prevMid,diff,precision;
        start = 0;
        end = number;
        mid = (start+end)/2;
        prevMid = 0;
        diff = abs(mid - prevMid);
        precision = 0.0005;
 
        while((mid*mid != number) && (diff > precision)) {
            if(mid*mid > number) {
                end = mid;
            } else {
                start = mid;
            }
            prevMid = mid;
            mid = (start+end)/2;
            diff =abs(mid - prevMid);
        }
         
        return mid;
}

In this way, we have seen how we can implement the Square Root function using the C++ language. Keep exploring, I hope it was easy enough to understand. If you have any doubt, feel free to ask in the comment section. All the best! Keep learning.

Thank you!

Regards,
Rahul Sah
Codespeedy Tech Pvt. Ltd.

Download project

Reviews Report

Submitted by Rahul Sah (rahulsah1436)

Download packets of source code on Coders Packet