The Computation of the Square Root of 𝑥

I came across an apparently simple yet intriguing coding problem:

Given a non-negative integer 𝑥, compute and return the square root of 𝑥.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Well, at first I didn’t see the “note,” and I thought it would just be a one-liner thing:

def mySqrt(self, x):  
    return int(x ** 0.5 // 1)

Then someone pointed out that I should avoid using **. Calculating a square root without using any built-in exponent function or operator? Here comes the fun with coding!

Without an exponent operator, you may want to “guess” the square root of an integer as taught in my Grade 9 math class. But how would you tell the computer to make a guess? What is the reference range? One method I could think of is the Bakhshali method:

Bakhshali method

𝑥₀ is the initial estimate. 𝑥_𝑛 is the 𝑛-th estimate, which is increasingly closer to the square root of 𝑆.

So in Python 3, we can write a few more lines of code to “guesstimate” the square root of an integer without employing the exponent operator:

def mySqrt(self, x):  
    if x < 2:  
        return x  

    x0 = x  
    a1 = (x - x0 * x0) / (2 * x0)  
    b1 = x0 + a1  
    x1 = b1 - (a1 * a1) / (2 * b1)  

    while abs(x1 - b1) >= 0.1:  
        x0 = x1  
        a1 = (x - x0 * x0) / (2 * x0)  
        b1 = x0 + a1  
        x1 = b1 - (a1 * a1) / (2 * b1)  

    return int(x1)

An alternative approach is using the Babylonian method:

Babylonian method

The code looks a bit snappier than with the Bakhshali method:

def mySqrt(self, x):  
    if x < 2:  
        return x  

    x0 = x  
    x1 = (x0 + x / x0) / 2  

    while abs(x0 - x1) >= 0.1:  
        x0 = x1  
        x1 = (x0 + x / x0) / 2  

    return int(x1)

This would be an interesting problem to solve for a job interview. :-)

Happy coding!