1

整数x、y、およびnの場合、（xとyのみが指定されます）x n = yかどうかをテストしますか？x = 8、y = 512の場合、n = 3であるため、これは真です。ただし、x=8およびy=500の場合、nは約2.98（整数ではない）である必要があるため、ステートメントはfalseと評価されます。このテストを行うには、対数を使用するのが最善の方法ですか？

ある整数が別の整数の累乗であるかどうかを確認すると、いくつかの解決策が提供されます。

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)

log（y、x）= log x y

特に大きな数の場合、どちらの方法がより速く評価されますか？

4

6 に答える 6

4

対数関数は浮動小数点近似を使用しているため、わずかな不正確さがあるため、対数法にはさらに注意が必要です。たとえば、3 10 = 59049ですが、次のようになります。

log(59049, 3)
   ===> 9.999999999999998

これを（答えが最も近い整数に「十分に近い」かどうかを確認することによって）補償できるかどうかは、xとyの範囲によって異なります。yが232未満の場合、対数が比例して整数に最も近い値になると思います（真の答えは整数ではありません）。

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

したがって、これよりも小さいイプシロンを選択すると、対数法を自信を持って使用できます。

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の許容範囲が大きい場合は、イプシロンの適切な値を見つける必要があります。ただし、注意してください。yが十分に大きい場合、倍精度浮動小数点に適切なイプシロンがない可能性があります。たとえば、yが2 48 − 1まで大きくなる可能性がある場合は、そのようになります。

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

したがって、 yが十分に大きい場合、対数に依存することはできません。後で、チェックとしてべき乗を明示的に実行する必要があります。

于 2012-12-12T19:37:15.663 に答える
1

適度に小さい入力の場合、3番目の方法が最適であると確信しています。（ただし、完全性のチェックにはもっと注意する必要があります。）

思考のためのいくつかの食べ物：

  1. xその累乗をおおよそ非常に高速に計算しsqrt(y)（つまり、O（M（log y））時間）、次にこの累乗でmod（O（M（log y）log log y）時間）して、次の2つのサブ問題を取得できます。半分のサイズ。

  2. 対数のかなり貧弱な近似を使用して、のかなり厳しい境界を取得できますn。の定数内にある整数を知っている場合は、のlog_x(y)定数の累乗をチェックするだけで済みxます。これらのチェックは、EdwardFalkの回答に例示されている「2乗と乗算の手法」を使用して最も速く実行されます。

  3. の境界がかなり広い場合でも、n適度なサイズのランダムな素数を法として算術演算を使用して、候補のセットを大幅に絞り込むことができますn。中国の剰余定理と一緒に適度なサイズのいくつかのランダムな素数を法として算術を使用して、可能性nをゼロまたは非常に効率的に1つに絞り込むことができるはずです。

2番目のアイデアで実行する：y近似値を取得するために必要なのはlog y、せいぜい定数だけであることに注意してください。他のすべては肉汁です。FPUを使用して上位53ビットの対数を取得し、数値の長さを使用して調整してから、時間内で最も近い整数を確認できるはずですO(M(log y))。3番目のアイデアでは、ランダム化を使用してx^n == y、O(log y)時間内に最適かどうかを確認できます。

于 2012-12-12T19:47:04.303 に答える
1

b ^ e = nであるbとeが存在する場合、数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は完全な立方根であり、完全5度の根でもあります。

私のブログに実装があります。

于 2012-12-12T19:01:43.573 に答える
1

数値が大きい場合、ログは高速になる可能性がありますが、ベンチマークする必要があります。これには、doubleへの変換とその逆の変換が含まれ、問題になる可能性があります。

私はこれがより良い解決策かもしれないと思います：

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 に答える
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 に答える
0

ベンチマークを行わずに、何が起こっているのかを目で確認するだけで、これが最速になるはずです。

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

（ただし、説明からxとyの意味を逆にしたことに注意してください。また、nは完全に異なります）

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

これは除算とモジュロ（基本的に2番目の除算）を実行しているため、2倍の作業を実行しますが、ループを早く終了できるため、勝つ可能性があります。

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

これは本質的に悪である浮動小数点を使用します（ただし、最近のCPUチップでは浮動小数点がより良く高速になっています）。ただし、それが全体であるかどうかを知る必要がある場合は、それが偶数か奇数かをテストします。

于 2012-12-12T19:00:28.663 に答える