4

右シフトや最下位ビットのチェックなどの操作を効率的に実行できるように、大きな基数 B の数値を格納する最良の方法は何ですか?

実際、私はインタビューの質問に出くわしました。

Given two numbers N and K such that 0<=N<=1000 and 0<=K<=1000^1000. I need 
to check that whether N^N = K or not. For example:

if N=2 and K=4 , 2^2 = 4 so return true;
if N=3 and K=26 , 3^3 != 26 so return false

私が考えていたのは、 を考えるとbase N number system、その中のN^Nに相当する1 followed by N zeroということです。たとえば - N = 2 の場合、2^2 = 100 (基数 2)、N=3 の場合、3^3 = 1000 (基数 3)。その後、かどうかを判断する関数を簡単に作成できますK = N^N。

int check(unsigned long int N, unsigned long int K) 
{
    unsigned long int i;
    for (i=0; i<N; i++) 
    {
        if (K%N != 0) //checking whether LSB is 0 or not in base N number system 
           return 0;
        K = K/N; //right shift K by one. 
    }
    return (K==1);
}

現在、この関数には 2 つの大きな問題があります。

1) An unsigned long int is not sufficient to store large numbers of range 0 
to 1000^1000.
2) The modulus and the division operations makes it every less efficient.

効率的にするために、右シフトを実行して最下位ビット操作を効率的にチェックできるように、大きな基数 N の数値を表す方法を探しています。誰もそのようなことに遭遇したことがありますか？または、この問題を効率的に解決する他の方法を知っている人はいますか?

4

5 に答える 5

2

面接官によっては、受け入れられる回答がいくつかあります。そして、これらのいずれかが受け入れられない場合は、面接担当者がすぐに別の提案をしてくれることを願っています。

  • を使用し、の代わりに を使用gmpして除算とモジュラスを実行するか、単に計算して と比較します。これは機能する最も簡単なことです。mpz_tunsigned longN^NK
  • 入力が基数 10 であり、最初にバイナリに変換するよりもそれに固執する方が速いと考えられる場合は、おそらく基数 2 ではなく基数 10 を内部表現として使用して、独自の大きな数のライブラリを作成します。もちろん、完全な算術ライブラリである必要はありません。本当に必要なのは剰余除算だけです。
  • 開始前に実行できるいくつかの高速テストを発明して、何らかの点Kでどこにも近くないときに多くの作業を回避します。N^Nたとえば、log(K) / Nが にほぼ等しいかどうかをテストlog(N)します。ログは、入力に最も便利な基数で取得されます。または、 がまたはのような便利な数で割り切れる回数Kをテストします。正確にの回数だけ割り切れない場合は、明らかに間違っています。または、またはのようないくつかの小さな数を法として等しいかどうかをテストしますN210KNNULONG_MAX1000000. 残念ながら、この種のことは、それらが等しくない特定のケースを高速化するだけであり、それらが等しいケースを含む他のすべてを遅くします. したがって、期待する入力によっては、逆効果になる可能性があります。

マクドウェラの答えが最善かもしれないし、そうでないかもしれない、私にはわからない。素数を生成する必要があるのは (プログラムを作成するとき) 1 回だけであり、1009 から始まる 1000 個の素数で十分であることが特に有望ですN <= 1000。素数が大きいほど、必要な作業が少なくなるため、特に の平方根よりも大きくならない場合は作業が少なくなりますULONG_MAX。二乗または同等の指数を使用してN^N各素数をモジュロKし、入力の基数に関係なく一度に数桁を計算します。

本当にフラッシュするために、事前に選択した素数ごとに、p任意の除数に対して機能する一般的な整数モジュラス演算よりも高速なモジュロ p 演算を記述できます (またはコンパイラに記述させます)。つまり、適切なコンパイラを使用すると、コンパイル時に の値が不明である場合i % 1009よりも高速になる可能性がありますが、実行時に 1009 であることが判明します。関数ポインタを介して。したがって、それを利用するには、見栄えの悪い繰り返しコードが必要になる場合があります。i % jj

于 2012-06-13T18:30:47.697 に答える
2

等価性をチェックするために、実際には高精度の演算を行う必要はありません - http://en.wikipedia.org/wiki/Chinese_reminder_theoremを使用できます。積が N^N より大きいことを確認するのに十分な素数を見つけてから、N^N を各素数のモジュロ K に対して順番にチェックします。

実際には、Java BigInteger パッケージを使用して単純な計算を行うことになるでしょう。

于 2012-06-13T18:16:17.893 に答える
0

1000^1000 のうち「良い」値は 1000 個しかないため (そしてそれらは互いに非常に離れているため)、最初に対数近似を使用してNを推測できます。その後、最大で 1 つの正確なチェックが必要になります (たとえば、いくつかの bignum ライブラリを使用)。

この対数は正確である必要はなく、strlen()で十分に近似することもできます。

于 2012-06-14T10:39:22.620 に答える
0

0<=N<=1000 および 0<=K<=1000^1000 となる 2 つの数値 N および K が与えられます。N^N = K かどうかを確認する必要があります。

多くは、コードに提供されたときにこれらの数値がどのように格納されるかに依存します。それらがテキスト形式であると仮定すると、そのままにして、N^N 値を格納する 1001 個の文字列の配列を作成します。これらの文字列の 1 回限りの作成のような任意精度の算術コマンド ライン プログラムを使用bcして、ループ内で呼び出すことができます。

于 2012-06-14T08:55:33.610 に答える
0

なぜ数値を基数 N に変換したいのですか?

N で割り続けることができます。そのような割り算を N 回行った後に 1 が得られた場合、それは N^N です。そうでなければそうではありません。

K を文字列として格納し、除算演算を実装する必要があります。

divide(k,n):
  c = ''
  a = ''
  for i in k:
    c = c+i
    a = a+ str(int(c)/ int(n))
    c = str(int(c) % int(n))
 return a

これはPythonで、Cで同様のものを実装できます

于 2012-06-13T18:11:33.153 に答える