C语言 求一个数的 n 次方根的算法

Algorithm to find nth root of a number

提问by user567879

I am looking for an efficient algorithm to find nth root of a number. The answer must be an integer. I have found that newtons method and bisection method are popular methods. Are there any efficient and simple methods for integer output?

我正在寻找一种有效的算法来查找数字的 n 次方根。答案必须是整数。我发现牛顿法和二分法是流行的方法。整数输出是否有任何有效且简单的方法？

回答by rubenvb

#include <math.h>
inline int root(int input, int n)
{
  return round(pow(input, 1./n));
}

This works for pretty much the whole integer range (as IEEE754 8-byte doubles can represent the whole 32-bit intrange exactly, which are the representations and sizes that are used on pretty much every system). And I doubt any integer based algorithm is faster on non-ancient hardware. Including ARM. Embedded controllers (the microwave washing machine kind) might not have floating point hardware though. But that part of the question was underspecified.

这几乎适用于整个整数范围（因为 IEEE754 8 字节double可以int精确表示整个 32 位范围，这是几乎每个系统上使用的表示和大小）。而且我怀疑任何基于整数的算法在非古代硬件上都更快。包括ARM。不过，嵌入式控制器（微波洗衣机类）可能没有浮点硬件。但问题的那部分没有具体说明。

回答by guest

I know this thread is probably dead, but I don't see any answers I like and that bugs me...

我知道这个帖子可能已经死了，但我没有看到任何我喜欢的答案，这让我很烦恼......

int root(int a, int n) {
    int v = 1, bit, tp, t;
    if (n == 0) return 0; //error: zeroth root is indeterminate!
    if (n == 1) return a;
    tp = iPow(v,n);
    while (tp < a) {    // first power of two such that v**n >= a
        v <<= 1;
        tp = iPow(v,n);
    }
    if (tp == a) return v;  // answer is a power of two
    v >>= 1;
    bit = v >> 1;
    tp = iPow(v, n);    // v is highest power of two such that v**n < a
    while (a > tp) {
        v += bit;       // add bit to value
        t = iPow(v, n);
        if (t > a) v -= bit;    // did we add too much?
        else tp = t;
        if ( (bit >>= 1) == 0) break;
    }
    return v;   // closest integer such that v**n <= a
}
// used by root function...
int iPow(int a, int e) {
    int r = 1;
    if (e == 0) return r;
    while (e != 0) {
        if ((e & 1) == 1) r *= a;
        e >>= 1;
        a *= a;
    }
    return r;
}

This method will also work with arbitrary precision fixed point math in case you want to compute something like sqrt(2) to 100 decimal places...

如果您想将 sqrt(2) 之类的值计算为 100 位小数，此方法也适用于任意精度的定点数学...

回答by Basile Starynkevitch

I question your use of "algorithm" when speaking of C programs. Programs and algorithms are not the same (an algorithm is mathematical; a C program is expected to be implementingsome algorithm).

我质疑您在谈到C 程序时对“算法”的使用。程序和算法是不一样的（算法是数学的；C 程序预计会实现一些算法）。

But on current processors (like in recent x86-64 laptops or desktops) the FPUis doing fairly well. I guess (but did not benchmark) that a fast way of computing the n-th root could be,

但是在当前的处理器上（比如最近的 x86-64 笔记本电脑或台式机），FPU的表现相当不错。我猜（但没有进行基准测试）计算第 n 个根的快速方法可能是，

 inline unsigned root(unsigned x, unsigned n) {
   switch (n) {
     case 0: return 1;
     case 1: return x;
     case 2: return (unsigned)sqrt((double)x);
     case 3: return (unsigned)cbrt((double)x);
     default: return (unsigned) pow (x, 1.0/n);
   }
 }

(I made a switch because many processors have hardware to compute sqrtand some have hardware to compute cbrt..., so you should prefer these when relevant...).

（我做了一个转换，因为许多处理器有硬件来计算sqrt，有些处理器有硬件来计算cbrt......，所以你应该在相关时更喜欢这些......）。

I am not sure that n-th root of a negative number makes sense in general. So my rootfunction takes some unsigned xand returns some unsignednumber. ?

我不确定负数的 n 次方根在一般情况下是否有意义。所以我的 root函数需要一些unsigned x并返回一些unsigned数字。?

回答by Todd Lehman

Here is an efficient general implementation in C, using a simplified version of the "shifting nth root algorithm" to compute the floor of the nth root of x:

这是 C 语言中的一个有效的通用实现，使用“移位 n 次方根算法”的简化版本来计算x的n次方根的下限：

uint64_t iroot(const uint64_t x, const unsigned n)
{
  if ((x == 0) || (n == 0)) return 0;
  if (n == 1) return x;

  uint64_t r = 1;
  for (int s = ((ilog2(x) / n) * n) - n; s >= 0; s -= n)
  {
    r <<= 1;
    r |= (ipow(r|1, n) <= (x >> s));
  }

  return r;
}

It needs this function to compute the nth power of x(using the method of exponentiation by squaring):

它需要这个函数来计算x的n次方（使用平方取幂的方法）：

uint64_t ipow(uint64_t x, unsigned n)
{
  if (x <= 1) return x;

  uint64_t y = 1;
  for (; n != 0; n >>= 1, x *= x)
    if (n & 1)
      y *= x;
  return y;
}

and this function to compute the floor of base-2 logarithm of x:

这个函数用于计算x 的以 2 为底的对数的底：

int ilog2(uint64_t x)
{
  #if __has_builtin(__builtin_clzll)
    return 63 - ((x != 0) * (int)__builtin_clzll(x)) - ((x == 0) * 64);
  #else
    int y = -(x == 0);
    for (unsigned k = 64 / 2; k != 0; k /= 2)
      if ((x >> k) != 0)
        { x >>= k; y += k; }
    return y;
  #endif
}

Note: This assumes that your compiler understands GCC's __has_builtintest and that your compiler's uint64_ttype is the same size as an unsigned long long.

注意：这假设您的编译器理解 GCC 的__has_builtin测试，并且您的编译器的uint64_t类型与unsigned long long.

回答by Vitthal Jadhav

For fastest n'th root algorithm by using vedic mathematics Refer http://www.slideshare.net/jadhavvitthal1989/vjs-root-algorithm-final

对于使用吠陀数学最快的 n 次根算法，请参阅http://www.slideshare.net/jadhavvitthal1989/vjs-root-algorithm-final

Same algorithm can be extended to compute root of algebraic equation.

相同的算法可以扩展到计算代数方程的根。