The Computation of the Square Root of 𝑥

Published
Tue ⋆ 2022-05-24 ⋆ 01:20 EDT

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 methodBakhshali method

𝑥0 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 methodBabylonian 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!

Next
Now – Wed ⋆ 2022-05-25 ⋆ 08:53 EDT
Previous
Status Update – Wed ⋆ 2022-03-02 ⋆ 02:25 EST