Exhaustive enumeration technique in Python to find the square root of a number

Question

Is there a better technique than the following to exhaustively enumerate the square root of numbers between 0 and 1? I have tried to implement Newton's method, but as it converges quadratically, using it would be unreasonable. I also understand that I can use math.sqrt.

x = 0.25
epsilon = 0.01
step = epsilon ** 2
guess = 0
ans = 0.0

while abs(ans ** 2 - x) >= epsilon and ans * ans <= x:
  ans += step
  guess += 1

print(f"number of guesses = {guess}")
if abs(ans ** 2 - x) >= epsilon:
  print(f"Failed on square root of {x}")
else:
  print(f"{ans} is close to the square root of {x}")

In this implementation, I get the following output:

number of guesses = 4899
0.48989999999996237 is close to the square root of 0.25

How should I be thinking of approximation solutions that are also efficient in terms of time and space complexity?

Answer 1

Adding a small value (epsilon) to the estimate is not how Newton's method is usually implemented.

Here's a version that returns the estimate and the number of guesses made:

def mySqrt(a, dp=4):
    guesses = 0
    if a > 0 and dp > 0:
        epsilon = 0.1 ** dp
        x = a / 2 # initial arbitrary estimate
        while True:
            guesses += 1
            y = (x + a / x) / 2
            if abs(y - x) <= epsilon:
                return y, guesses
            x = y
    return float('nan'), 0

print(mySqrt(0.5, dp=6))
print(mySqrt(0.5))

Output:

(0.7071067811865475, 6)
(0.7071067812624661, 5)

Thus, in this case, the square root of 0.5 is estimated to an accuracy of 6 and 4 (the default) decimal places in just 6 and 5 iterations respectively