英文:
Exhaustive enumeration technique in Python to find the square root of a number
问题
以下是您要翻译的内容：
是否有比以下方法更好的技巧来穷举计算介于0和1之间的数的平方根？我尝试过实现牛顿法，但由于其二次收敛，使用它将不合理。我还了解到我可以使用 `math.sqrt`。
```python
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}")
在这个实现中，我得到以下输出：
猜测次数 = 4899
0.48989999999996237 接近于0.25的平方根
我应该如何考虑同时具有时间和空间复杂性方面的高效近似解？
<details>
<summary>英文:</summary>
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`.
```python
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?
答案1
得分: 1
将估计值增加一个小值（epsilon）并不是牛顿法通常的实现方式。
以下是一个返回估计值和猜测次数的版本：
def mySqrt(a, dp=4):
guesses = 0
if a > 0 and dp > 0:
epsilon = 0.1 ** dp
x = a / 2 # 初始的任意估计值
while True:
guesses += 1
y = (x + a / x) / 2
if abs(y - x) <= epsilon:
return y, guesses
x = y
return float('nan'), 0
输出：
(0.7071067811865475, 6)
(0.7071067812624661, 5)
因此，在这种情况下，对于0.5的平方根分别在6和5次迭代中以6和4（默认值）位小数的精度进行了估计。
英文:
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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论