负平方根的二分算法

Question

我有一个正整数平方根的二分循环。尝试负平方根时，它会陷入无限循环。我已经将它缩小到将 ans 设置为 -12 然后对其进行平方，但我无法弄清楚如何修复循环以使其保留。任何帮助将不胜感激。

下面有问题的代码：

x = -25
epsilon = 0.01
numGuesses = 0
low = 1.0
high = x
ans = (high + low)/2.0
if x >= 1.0:
    while abs(ans**2 - x) >= epsilon:
        print("low = " + str(low) + " high + " + str(high) + " ans = " + str(ans))
        numGuesses += 1
        if ans**2 < x:
            low = ans
        else:
            high = ans
        ans = (high + low)/2.0
else:       
    while abs(ans**2 - x) >= epsilon:
        print("low = " + str(low) + " high + " + str(high) + " ans = " + str(ans))
        numGuesses += 1
        if abs(ans**2) < x:
            low = ans

        else:
            high = ans
        ans = (high + low)/2.0

print("numGuesses = " + str(numGuesses))
print(str(ans) + " is close to square root of " + str(x))

Answer 1

最简单的方法是设置一个sign标志：将x翻转为正，设置sign = False然后求+25的平方。当你收敛时，检查sign：如果是False，那么你的值是虚数。

您当前的代码试图收敛到一个实根，永远不会对负数有效。

Answer 2

感谢 Prune，我得到的答案如下：

x = -25
if x < 0:
    flag = False
else:
    flag = True 
if flag is False:
    x = abs(x)

epsilon = 0.01
numGuesses = 0
low = 1.0
high = x
ans = (high + low)/2.0
if x >= 1.0:
    while abs(ans**2 - x) >= epsilon:
        print("low = " + str(low) + " high + " + str(high) + " ans = " + str(ans))
        numGuesses += 1
        if ans**2 < x:
            low = ans
        else:
            high = ans
        ans = (high + low)/2.0

if flag is False:
    ans = -ans
    x = -x    
print("numGuesses = " + str(numGuesses))
print(str(ans) + " is close to square root of " + str(x))

Answer 3

x = -37
epsilon = 0.01
num_guess = 0
low = 0.0
high = abs(x)

ans = ((low + high)/2.0)

while abs(ans**3-abs(x)) >= epsilon:
    #print("low = " + str(low) + " high " + str(high) + " ans = " + str(ans))
    if ans**3 < abs(x):
        low = ans
    else :
        high = ans
    ans = ((low + high)/2.0)
    num_guess += 1 

if x < 0:
    ans = -ans
print("Steps taken during bisecction search: ",num_guess)
print("The cube root of " + str(x) + " is " + str(ans))

也许你可以在代码中输入的所有 x 中打印 abs()

Answer 4

您的问题是如何修复循环以使其保留？简单的答案是：您不需要。

解决这个问题的方法部分是数学部分是软件设计。

从数学上讲，您无法计算负数的平方根并得到实数。有两种可能的解决方案：

切换到复数。但我怀疑你的二分算法是否会起作用。
当您不需要复数或者当您的问题域无法理解复杂的结果时，不要对负数执行计算。

您绝不能做的是编写生成负数结果的代码。当然，从算法上讲，您可以这样做，因为包括您自己在内的几个答案都表明了这一点。但这是一个非常糟糕的想法，出于以下软件设计的考虑。

您的代码将成为更大软件的一部分，并且会有一些其他代码调用您的函数。数学在这里给了你一个提示：用负数调用你的函数是调用方错误。但是由于您的功能将 return some （数学上无用）导致您的软件项目中的此类错误可能会在很长很长时间内被发现。但总有一天它会产生丑陋的失败，温暖而舒适地隐藏在你创造的阴霾中，让人很难找到它。

好的，抱歉，解决方案是：当您的函数使用负参数调用时引发异常。

负平方根的二分算法

Bisection algorithm for negative square roots

python

infinite-loop