将巴比伦平方根算法推广至n次方根

Question

我一直在寻找计算根的算法，然后发现了巴比伦算法。我非常喜欢它，因为它简单易懂。但问题是它只能计算平方根，而我正在尝试编写一个函数可以计算任意幂次的根，只考虑正整数。

以下是该函数：

double functions::rot(double x, double y) {
    double z = x;
    double w = 1;
    double e = 0.000001; 
    while (z - w > e){
        z = (z + w) / 2;
        w = x / z;
    }
    return z;
}

y是指数。有没有办法修改这个算法，使得y成为根的指数？比如，如果y=3，那么就需要对三次方根进行运算。

- William Thomas

---

尝试将w = x/z更改为w=x/(z*z)，你会得到什么结果？ - n. m.

巴比伦方法的图形解释是调整矩形的边长直到得到一个正方形，同时保持给定的面积。你可以通过调整立方体、超立方体等其中一条边的长度，并同时调整其他边来使其更接近实际图形，从而轻松地将其抽象到更高维度。 - mszymborski

将w = x/z更改为w = x/(z*z)，当x = 64时，会得到3.812388。 - William Thomas

抱歉，应该将 z - w > e 更改为 std::abs(z-w) > e。 - n. m.

Answer 1

说要将w = x / z更改为w = x / z*z的评论只有1/3（双关语）是正确的。您还需要进行两个更改，我认为从这个Python代码中很明显：

def rot(x, y): # 
    z = x
    w = 1
    e = 0.000001
    while (z - w > e):
        z = ((y - 1) * z + w) / y
        w = x / (z ** (y - 1)) # a ** b is a to the power of b in Python
                               # you might want to use modular exponentiation in C++
                               # (or not if y is double...)
    return z


print(rot(64, 3)) # prints 4
print(rot(59, 6)) # prints 1.9730678338673044

这里有一个参考链接，建议你阅读一下，因为它提供了更深入的解释。

- IVlad

---

FYI 参考链接已损坏。这是参考文献的新位置：https://www.researchgate.net/publication/237415858_EXTENDING_THE_BABYLONIAN_ALGORITHM - Trashman

Answer 2

牛顿法类似于巴比伦法，可用于提取任意幂的根。我们假设k，即根，和n，即输入，都是正整数；分配u时的两个除法均为整数除法（忽略余数）：

function iroot(k, n)
    k1, u, s := k-1, n, n+1
    while u < s
        u := (u * k1 + n / (u ** k1)) / k
        s := u
    return s

警告：未测试的伪代码。函数iroot返回将整数n乘以自身k次不超过其结果的最大整数。

- user448810

---

尽管这个算法看起来不错，但我需要它接受和返回双精度浮点数，因为我不仅仅会使用整数作为输入。但根必须是正整数。 - William Thomas

你真的需要实数意义上的double类型，还是分数足够了？然后你可以先（或之后）取相应数字的幂。例如，x=n^(2/3)=root(n^2, 3)=root(n,3)^2。 - Daniel Jour