在C语言中计算分数指数

Question

在C语言中计算分数指数

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的导数。

发布于physicsforums 那种方法的问题在于，如果我想计算 5.2^0.33333，我需要找到这个方程的根 x^10000 - 5.2^33333 = 0。我得到了巨大的数字，并且大多数时候会出现inf和nan错误。

有人能给我解决这个问题的建议吗？或者，有人能提供另一种计算 a^n 的算法吗？

- user3787097

2

@R..没有什么很好的理由这样做。我只是为了好玩，看看我能做什么。这不是作业或者其他什么。我已经毕业了，编程是我的爱好。但是我可以想象，如果我正在编程一个原始的微控制器，它可能没有这些功能。 - user3787097

@R Sahu 嗯，"牛顿法...但不是用来计算...sqrt(x)"。激励工程师的最好方式就是说某件事情做不到。http://en.wikipedia.org/wiki/Newton's_method - chux - Reinstate Monica

1

评估5.2^0.001意味着解决x^1000 = 5.2。然后t1 = x^3给出了5.2^0.003。t2 = t1^10 = x^30给出了5.2^0.03。t3 = t2^10 = x^300给出了5.2^0.3。最后t1t2t3给出了5.2^0.333。听起来像是x^333。 - Cheers and hth. - Alf

@Cheersandhth.-Alf非常好的建议。但是，x ^ 1000，其中x例如为5，已经是一个巨大的数字---> 9.33x10 ^ 698 我认为我不能使用那种方法。 - user3787097

我已经实现了这样的功能并多次使用它。它提供了一个类，用于存储任意大小的自然数，以及一个类，用于存储任意大小的有理数（使用自然数分子和自然数分母）。这两个类支持C++提供的任何算术运算。有理数类还通过自然指数实现了幂和根。如果您想计算有理指数的幂，则可以通过指数的分子进行幂运算，通过指数的分母进行根运算。请参阅 https://github.com/barakman/Num。 - barak manos

显示剩余8条评论

3个回答

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;
}

- David C. Rankin

关于倒数平方根：从个人经验和测试来看，使用3次牛顿迭代就足以达到浮点/单精度的机器精度。而双精度版本则需要4次迭代。10次迭代只是（无用的）过度杀伤力。 - Federico

2

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

- Pradhan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nominal Animal · Accepted Answer

看起来你的任务是计算

⎛ 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的幂）用作除法中的分母; 您将得到除以零错误。个人建议检查结果是否应该为正或负，并且在大小方面小于或大于一；总共有两条规则来选择安全的初始y。

有问题吗？