查找数字的第n个根的算法

Question

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

Answer 1

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

这适用于几乎整个整数范围(因为IEEE754 8字节doubles可以int精确地表示整个32位范围,这是几乎每个系统上使用的表示和大小).我怀疑任何基于整数的算法在非古代硬件上都更快.包括ARM.嵌入式控制器(微波洗衣机类)可能没有浮点硬件.但问题的这一部分未得到详细说明.

Answer 2

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

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

如果你想计算像sqrt(2)到100个小数位的东西,这个方法也适用于任意精度定点数学...

Answer 3

在谈到C程序时,我质疑你对" 算法 "的使用.程序和算法不一样(算法是数学的; C程序预计会实现某种算法).

但是在目前的处理器上(比如最近的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);
   }
 }

(我做了一个开关,因为许多处理器都有硬件要计算sqrt,有些处理器有硬件要计算cbrt......所以你应该在相关时更喜欢这些......).

我不确定负数的第n个根通常是否有意义.所以我的 root函数需要一些unsigned x并返回一些unsigned数字.