1

对于整数 x、y 和 n，（仅给出 x 和 y）测试 x n = y？如果 x = 8，y = 512，则 n = 3，所以这是真的。但如果 x = 8 和 y = 500，n 必须在 2.98 左右（不是整数），因此该语句评估为假。使用对数是进行此测试的最佳方法吗？

检查一个整数是否是另一个整数的整数幂提供了一些解决方案：

int n = y; while(n < x) n *= y; return n == x,

while (x%y == 0)  x = x / y
return x == 1

和对数方法（这是我的版本）：

return ((log(y, x) % 1) == 0) // log(expression, base)

日志(y, x) = 日志x y

哪种方法计算速度更快，尤其是对于大数字？

4

6 回答 6

4

对数方法需要更加小心，因为对数函数由于使用了浮点逼近，所以有少量的不准确性。例如 3 10 = 59049，但是：

log(59049, 3)
   ===> 9.999999999999998

您是否可以对此进行补偿（通过检查答案是否“足够接近”最接近的整数）取决于您的x和y的范围。如果y小于 2 32，那么我认为最接近的对数可以按比例得到一个整数（没有真正的答案是一个整数）是：

1 - log(4294967295, 65536) / 2
   ===> 1.049693665322593e-11

所以选择一个小于这个的 epsilon，你可以放心地使用对数方法：

n = log(y, x);
e = round(n);
if (abs(1 - n / e) < epsilon) {
    /* y == x to the power of e */
} else {
    /* y not a power of x */
}

如果y的允许范围更大，那么您必须为 epsilon 找到合适的值。但请注意：对于足够大的y ，双精度浮点中可能没有合适的 epsilon 。例如，如果y可以大到 2 48 − 1 那么就是这样，因为

log(281474976710655, 16777216)
   ===> 2.0 exactly

因此，对于足够大的y，您不能依赖对数：您需要在之后显式执行取幂作为检查。

于 2012-12-12T19:37:15.663 回答
1

对于相当小的输入，我相当确定您的第三种方法效果最好。（不过，您需要更加小心地检查完整性。）

一些值得思考的食物：

  1. 您可以计算一个x大致sqrt(y)非常快的幂（即 O(M(log y)) 时间），然后通过这个幂（在 O(M(log y) log log y) 时间）得到两个子问题大小的一半。

  2. 您可以对对数使用相当差的近似值来获得相当严格的n. 如果我知道一个在 的常数范围内的整数log_x(y)，那么我只需检查 的常数次方x。使用 Edward Falk 的回答中举例说明的“平方和乘法技术”可以最快地完成这些检查。

  3. 给定一个相当宽的界限n，您可以使用算术模一个适度大小的随机素数来显着缩小候选集n。应该可以使用算术模数几个中等大小的随机素数以及中国剩余定理来非常有效地将可能缩小n到零或一。

以第二个想法运行：请注意，我只需要最高位 就y可以得到一个近似值log y，最多是一个常数；其他一切都是肉汁。您应该能够使用 FPU 取前 53 位的对数，使用数字的长度进行调整，然后O(M(log y))及时检查最接近的整数。第三个想法让您可以使用随机化来检查是否及时x^n == y，O(log y)这是最佳的。

于 2012-12-12T19:47:04.303 回答
1

这种方法应该可以解决问题：

void toCheckPower(){
    Scanner sc=new Scanner(System.in);

    int n=sc.nextInt();
    System.out.println("No of which power is checked="+n);

    int pow=sc.nextInt();
    int num=pow;
    System.out.println("No to check power="+pow);
    int sum=1;

    while(sum<=pow){
        sum=sum*n;
        if(sum==pow){
            System.out.println(pow+" is a Power of "+n);
            break;
        }
        else if(sum>pow){
            System.out.println(pow+" is not a Power of "+n);
            break;
        }
     }
}
于 2014-07-08T07:59:47.587 回答
1

如果存在 a b和e其中b ^ e = n ，则数n是完美幂。例如 216 = 6^3 = 2^3 * 3^3 是完美幂，但 72 = 2^3 * 3^2 不是。如果数字n是完美幂，则指数e必须小于 log2 n，因为如果e大于则 2 ^ e将大于n. 此外，只需要测试素数 *e*s，因为如果一个数是复合指数的完美幂，它也将是复合分量的素因数的完美幂；例如，2^15 = 32768 = 32^3 = 8^5 是一个完美的立方根，也是一个完美的五次根。

我的博客上有一个实现。

于 2012-12-12T19:01:43.573 回答
1

对于大量数据，日志可能会更快，但您应该对其进行基准测试。这将涉及到 double 和 back 的转换，这可能是一个问题。

我认为这可能是一个更好的解决方案：

long y = 512;
long x = 8;
if (x <= 1) return false;
while (y>1) {
    // Find maximum x^(2^n) <= y
    long xp = x;   // x to some maximum power
    long xp2;      // experimental value of xp
    while ((xp2 = xp*xp) <= y)
      xp = xp2;
    if (y%xp != 0) return false;  // reject
    y /= xp;
}
return y == 1;

仍然有可以改进的方法，我只测试了几个案例，但它似乎有效。

于 2012-12-12T19:13:37.073 回答
0

如果没有基准测试，并且只是观察正在发生的事情，这个应该是最快的。

int n = y; while(n < x) n *= y; return n == x;

（但是请注意，您已经从描述中颠倒了 x & y 的含义，并且 n 完全不同）

while (x%y == 0)  x = x / y;

这是做除法和取模（本质上是第二次除法），所以它做了两倍的工作，但它可以更早地退出循环，所以它可能会赢。

return ((log(y, x) % 1) == 0)

这使用了本质上是邪恶的浮点（尽管浮点在现代 CPU 芯片中变得更好更快）。然而，当你需要知道它是否完整时，你做它的模数是测试它是偶数还是奇数。

于 2012-12-12T19:00:28.663 回答