c - Perfect Power detection in linear time

Question

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!

score 3 · Accepted Answer

あなたのコメントの 1 つで、これを巨大な数と互換性を持たせたいと述べています。その場合、任意に大きな数の操作をサポートするGMP ライブラリを導入することをお勧めします。これらの操作の 1 つは、それが完全べき乗であるかどうかをチェックすることです。

これはオープンソースであるため、ライブラリ全体を取り込みたくない場合は、ソースコードをチェックアウトして、どのように動作するかを確認できます。

score 2 · Accepted Answer

n固定サイズ (32 ビットなど) の整数変数に収まる場合、最適な解決策はおそらく、そのような数値のリストをハードコーディングし、それをバイナリ検索することです。覚えておいてください、int範囲にはおおよそ

sqrt(INT_MAX)完全な正方形
cbrt(INT_MAX)完璧なキューブ
等

32 ビットでは、およそ 65536 + 2048 + 256 + 128 + 64 + ... < 70000 です。

score 0 · Accepted Answer

r-base logarithmが必要です。恒等式を使用して、自然対数を使用して計算します

そう：

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

したがって、次のように計算する必要があります。

x = log(n)/log(r)

(私の首には、これは高校の数学です。これは、私がそのアイデンティティを正しく覚えているかどうかを調べなければならないことをすぐに説明します:))

score 0 · Accepted Answer

でyを計算した後

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

それに最も近い int を取得でき、独自の累乗関数を使用して合計との等価条件をチェックできます。

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

このようにして、数値が他の数値の整数乗であるかどうかを確認できると思います。

c - Perfect Power detection in linear time

4 に答える 4

Related

Reference