3

我正在尝试评估 a^n，其中 a 和 n 是有理数。我不想使用任何预定义的函数，例如sqrt()或pow()

所以我正在尝试使用牛顿法来获得使用这种方法的近似解：

3^0.2 = 3^(1/5) ，所以如果 x = 3^0.2，x^5 = 3。

解决这个问题的最好方法（没有计算器但仍然使用基本的算术运算）可能是使用“牛顿法”。牛顿求解方程 f(x)= 0 的方法是建立一个数字序列 xn，通过将 x0 作为一些初始“猜测”，然后 xn+1= xn- f(xn/f '(xn) 其中 f '(x) 是 f 的导数。

发表在物理论坛上

这种方法的问题是，如果我想计算5.2^0.33333，我需要找到这个方程的根x^10000 - 5.2^33333 = 0。我最终得到了大量的数字，并且大多数时候都会inf出错nan。

有人可以就如何解决这个问题给我建议吗？或者，有人可以提供另一种算法来计算 a^n 吗？

4

3 回答 3

8

看来你的任务是计算

⎛ xN ⎞(aN / aD)
⎜⎼⎼⎼⎼⎟           where xN,xD,aN,aD ∈ ℤ,  xD,aD ≠ 0
⎝ xD ⎠

仅使用乘法、除法、加法和减法，建议使用牛顿法。

我们试图求解的方程（对于y）是

             (aN / aD)
y = (xN / xD)            where y ∈ ℝ

牛顿法找到函数的根。如果我们想用它来解决上面的问题，我们从左边减去右边，得到一个函数，其零给我们想要的y ：

                  (aN/aD)
f(y) = y - (xN/xD)        = 0

帮助不大。我想这就是你得到的？这里的重点是暂时不要形成该函数，因为我们没有办法计算有理数的有理幂！

首先，让我们确定aD和xD都是正数。如果aD为负，我们可以简单地通过否定aN和aD来做到这一点（因此aN / aD的符号不会改变），如果xD为负，则同时否定xN和xD。请记住，根据定义，xD或aD都不是零。然后，我们可以简单地将两边都提高到aD次方：

 aD            aN     aN     aN
y   = (xN / xD)   = xN   / xD

我们甚至可以通过将两边都乘以最后一项来消除除法：

 aD     aN     aN
y   × xD   = xN

现在，这看起来很有希望！我们从中得到的功能是

        aD   aN     aN
f(y) = y   xD   - xN

牛顿法也需要导数，这显然是

f(y)            aD   aN
⎼⎼⎼⎼ = df(y) = y   xD   y / aD
 dy

牛顿方法本身依赖于迭代

             f(y)
y    = y  - ⎼⎼⎼⎼⎼⎼
 i+1    i    df(y)

如果你算出数学，你会发现迭代只是

                                 aD
                y[i]      y[i] xN
y[i+1] = y[i] - ⎼⎼⎼⎼ + ⎼⎼⎼⎼⎼⎼⎼⎼⎼⎼⎼⎼⎼⎼
                 aD           aD   aN
                       aD y[i]   xD

您不需要将所有y值保存在内存中；记住最后一个就足够了，当它们的差异足够小时就停止迭代。

您仍然有上面的幂运算，但现在它们只是整数幂运算，即

  aD
xN   = xN × xN × .. × xN
       ╰───────┬───────╯
              aD times

您可以非常简单地做到这一点，例如只需将参数乘以所需的次数，例如在 C 中，

double ipow(const double base, const int exponent)
{
    double result = 1.0;
    int    i;
    for (i = 0; i < exponent; i++)
        result *= base;
    return result;
}

有更有效的方法来进行整数求幂，但是上面的函数应该是完全可以接受的。

最后一个问题是选择初始y以便收敛。您不能使用 0，因为（的幂）y用作除法中的分母；你会得到零误差除法。就个人而言，我会检查结果是否应该是正数或负数，以及小于或大于 1 的数量级；总体上有两条规则来选择一个安全的初始y。

问题？

于 2014-07-04T05:36:49.700 回答
2

您可以使用广义二项式定理。代入y=1和x=a-1。您可能希望根据所需的精度在足够的项之后截断无限级数。为了能够将术语数量与准确性联系起来，您需要确保这些x^r术语的绝对值在减少。因此，根据 and 的值a，n您应该应用公式来计算 and 之一，a^n并a^(-n)使用它来获得所需的结果。

于 2014-07-04T04:01:02.343 回答
2

将整数乘以幂的解决方案是：

int poweri (int x, unsigned int y)
{
    int temp;
    if (y == 0)
        return 1;

    temp = poweri (x, y / 2);
    if ((y % 2) == 0)
        return temp * temp;
    else
        return x * temp * temp;
}

但是，平方根并不能提供干净的封闭解决方案。可以在wikipedia-square root和Wolfram Mathworks Square Root Algorithms找到很多背景知识两者都提供了几种满足您需求的方法，您只需选择适合您目的的方法。

稍作修改，来自维基百科的这个例程（修改为返回平方根并提高准确性）返回一个令人惊讶的准确平方根。是的，会有关于使用联合的咆哮，并且它仅在整数和浮点存储等效的情况下有效，但如果您正在破解自己的平方根，这相对有效：

float sqrt_f (float x)
{
        float xhalf = 0.5f*x;
        union
        {
            float x;
            int i;
        } u;
        u.x = x;
        u.i = 0x5f3759df - (u.i >> 1);
        /* The next line can be repeated any number of times to increase accuracy */
        // u.x = u.x * (1.5f - xhalf * u.x * u.x);
        int i = 10;
        while (i--)
            u.x *= 1.5f - xhalf * u.x * u.x;

        return 1.0f / u.x;
}
于 2014-07-04T06:21:23.803 回答