python - 如何在Python中使用小数有效计算立方根

Question

我对Python中的decimal模块很陌生，我想知道计算立方根(或任何真正的根)最有效的方法是什么。我尝试了 num ** (Decimal(1)/Decimal(3) 但花了相当长的时间。例如，下面的代码在运行 python 3 的 Intel i5 处理器上大约需要 20 秒:

from decimal import *

getcontext().prec = 10000
a0 = Decimal(3.0)

import time
beg = time.time()
cuber = a0**(Decimal(1)/Decimal(3))
end = time.time()
print(end-beg)

我知道可以做更好的事情，因为只需编写一个简单的牛顿算法即可缩短运行时间(请参见下面的代码)。 所以，我的问题是什么是获取小数整数根的好方法(最好是内置的)？

快速牛顿法，速度更快(~0.2 秒)如下:

def cube_root( A):
    guess = (A-Decimal(1))/Decimal(3)
    x0 = (Decimal(2) * guess + A / Decimal(guess*guess) )/Decimal(3.0)
    while 1:
        xn =(Decimal(2) * x0 + A / Decimal(x0*x0) )/Decimal(3.0)
        if xn == x0:
            break
        x0 = xn
    return xn

beg = time.time()
print(cuber - cube_root(a0))
end = time.time()
print(end-beg)

在我的系统上，上述所有代码的示例输出是:

23.898984670639038
0E-9999
0.10790443420410156

Answer 1

对于这样的低阶立方根，牛顿将是您最好的选择。我通过删除内部测试使循环更加高效，并且速度提高了大约 5%。删除冗余的 Decimal 转换又获得了 2-3% 的效果。

def cube_root( A): 
    d1 = Decimal(1)
    d2 = Decimal(2)
    d3 = Decimal(3)

    x0 = (A-d1)/d3
    xn = (d2 * x0 + A / Decimal(x0*x0) ) / d3

    while xn != x0:
        x0 = xn
        xn = (d2 * x0 + A / Decimal(x0*x0) ) / d3

    return xn