没有除法的立方根的牛顿迭代

计算科学 算法 数值分析 特殊功能
2021-11-25 10:44:40

这是一个众所周知的技巧,可以避免计算平方根时的除法,以将牛顿法应用于求1/x,并且可能更广为人知的是,使用牛顿法求倒数而无需除法

在拯救 StackOverflow 线程时,从链接腐烂中有效地播种立方根的牛顿迭代,我想到立方根的无除法迭代也应该是可能的。

例如,如果我们要解决:

x3=a2

然后x=a2/3a3=ax. 上述方程的牛顿迭代很简单:

xn+1=xnxn3a23xn4=43xn13a2xn4

我们再次避免除法运算,至少如果分数常数是为 FP 乘法预先评估的。

所以类似的东西是可能的,但我在(诚然肤浅的)网络搜索中没有找到对这些方法的具体讨论。更重要的是,我怀疑一个聪明人已经发现了一个更好的想法,并且你们中的一个珍贵的同事已经看到或考虑过了。

1个回答

立方根并不像平方根那么重要(例如,对于归一化向量),所以这可能就是为什么很少讨论它们的原因。

一般来说,如果您将牛顿法应用于xαβ, 你得到迭代

(1α1)x+βαx1α,
所以你只需要选择方程α是负整数,不仅仅是立方根和平方根,这也适用于其他有理幂。

您的方案只需要 7 次迭代即可在区间上收敛到双精度a[12,1]从恒定的初始猜测开始1

在此处输入图像描述

另一个需要考虑的有趣事情是现有库实现的内容:

编辑另一种产生良好猜测的方法是从多项式近似开始a2/3在进行牛顿迭代之前。两项 Chebyshev 级数将迭代次数减少到 4 次,三项需要 3 次迭代,而 6 项需要两次迭代。在我的测试中,三项切比雪夫级数后跟 3 次迭代大约是13比哈雷还快。我还没有测试所有可能的组合,目前看来最快的是 6 项 Chebyshev 系列,然后是 1 个 Halley 迭代x3a; 我也只测试了区间[12,1],每个浮点数都可以通过分离尾数来减少。