Writing Your Own Sqrt Function
Function Input and Output :
Before talking about the function's algorithm, clarify the function’s input and output. The function takes an integer number as input and returns an integer number which is the square root of the input Number.
Basically, the requirement is to give the square root of the input number in integer form, if it is in float (decimal) then we will floor the value and make it an integer.
Algorithm of Function :
There are many ways to write the program for calculating the square root of an integer.
The approach I used is simple and easy to understand but only works for the function with such requirements as mentioned above.
The approach is the same as in Binary Search Approach. We just do a binary search for the number in the numbers less the input numbers. We know the square root of the number cannot be greater than half of the number. (e.g if N is the input number, the square root can’t be greater than N/2)
So we will binary search for the number, the square of which is equal to the input number (N). if we don’t find any such number we will return the number the square of which is close to the input number.
Code of the Function :
It sounds confusing in theory, so let’s talk about the code of the function. The code is the same as binary search with a little bit of changing.
If you don’t know the algorithm of binary search then read the below article first
The only change is that in a simple binary search if the number is not found we return the -1, while in this case we just return the number which is close to our desired number. (Our desired number is the number, the square of which is equal to the input number)
Here is the code of the function below in C++ Language
Space and Time Complexity :
Its space and Time Complexity is the same as the space and time complexity of Binary Search.
Time Complexity = O(long)
Space Complexity = O(1)
