线性时间内的完美功率检测

发布于 11-10 09:50 字数 483 浏览 6 评论 0原文

我正在尝试编写一个 C 程序,给定一个正整数 n(> 1),检测是否存在数字 x 和 r,以便 n = x^r

这就是我到目前为止所做的:

while (c>=d) {
    double y = pow(sum, 1.0/d);
    if (floor(y) == y) {
        out = y;
        break;
    }

    d++;
}

在上面的程序中,“c " 是指数 (r) 的最大值,“d”将从等于 2 开始。 Y 是要检查的值,变量“out”设置为稍后输出该值。基本上,脚本的作用是检查 y 的平方根是否存在:如果不存在,他会尝试使用平方根等等......当他找到它时,他将 y 的值存储在“out”中,以便: y = out^d

我的问题是,有没有更有效的方法来找到这些值?我在网上找到了一些文档,但这比我高中代数复杂得多。我怎样才能以更有效的方式实现这一点?

谢谢!

I'm trying to write a C program which, given a positive integer n (> 1) detect whether exists numbers x and r so that n = x^r

This is what I did so far:

while (c>=d) {
    double y = pow(sum, 1.0/d);
    if (floor(y) == y) {
        out = y;
        break;
    }

    d++;
}

In the program above, "c" is the maxium value for the exponent (r) and "d" will start by being equal to 2. Y is the value to be checked and the variable "out" is set to output that value later on. Basically, what the script does, is to check if the square roots of y exists: if not, he tries with the square cube and so on... When he finds it, he store the value of y in "out" so that: y = out^d

My question is, is there any more efficient way to find these values? I found some documentation online, but that's far more complicated than my high-school algebra. How can I implement this in a more efficient way?

Thanks!

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

漫漫岁月2024-11-17 09:50:15

在您的评论之一中,您表示您希望它与巨大的数字兼容。在这种情况下,您可能需要引入 GMP 库,它支持任意大数的操作,其中之一检查它是否是完美幂

它是开源的,因此如果您不想引入整个库,您可以查看源代码并了解他们是如何做到的。

In one of your comments, you state you want this to be compatible with gigantic numbers. In that case, you may want to bring in the GMP library, which supports operations on arbitrarily large numbers, one of those operations being checking if it is a perfect power.

It is open source, so you can check out the source code and see how they do it, if you don't want to bring in the whole library.

浪菊怪哟2024-11-17 09:50:15

如果n适合固定大小(例如32位)整数变量,则最佳解决方案可能只是对这些数字的列表进行硬编码并对其进行二进制搜索。请记住,在 int 范围内,大致有

  • sqrt(INT_MAX) 完美平方
  • cbrt(INT_MAX) 完美立方
  • 等。

在 32 位中,大约是 65536 + 2048 + 256 + 128 + 64 + ... < 70000。

If n fits in a fixed-size (e.g. 32-bit) integer variable, the optimal solution is probably just hard-coding the list of such numbers and binary-searching it. Keep in mind, in int range, there are roughly

  • sqrt(INT_MAX) perfect squares
  • cbrt(INT_MAX) perfect cubes
  • etc.

In 32 bits, that's roughly 65536 + 2048 + 256 + 128 + 64 + ... < 70000.

葮薆情2024-11-17 09:50:15

您需要 r 基 对数,使用恒等式来计算它 自然对数

所以:

log_r(x) = log(x)/log(r)

所以你需要计算:(

x = log(n)/log(r)

在我的脖子上木头,这是高中数学,这立即解释了我必须查找我是否正确记住了该身份:))

You need the r-base logarithm, use an identity to calculate it using the natural log

So:

log_r(x) = log(x)/log(r)

So you need to calculate:

x = log(n)/log(r)

(In my neck of the wood, this is highschool math. Which immediately explains my having to look up whether I remembered that identity correctly :))

情仇皆在手2024-11-17 09:50:15

计算 y 之后,

double y = pow(sum, 1.0/d);

您可以获得最接近的整数,并且可以使用自己的幂函数来检查
与 sum 相等的条件。

int x = (int)(y+0.5);
int a = your_power_func(x,d);
if (a == sum)
     break;

我想这样你就可以确认一个数字是否是其他数字的整数幂。

After you are calculating y in

double y = pow(sum, 1.0/d);

you can get the nearest int to it and you can use your own power function to check for the
equality condition with sum.

int x = (int)(y+0.5);
int a = your_power_func(x,d);
if (a == sum)
     break;

I guess this way you can confirm whether a number is integer power of some other number or not.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文