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?
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