3

大きな数とは何か、そしてそれらを処理するために使用される一般的なアルゴリズムは何かと考えていました。Coders at Work でこの用語が言及されているのを聞いた.インタビューで、大きな数を扱うライブラリを作成するように求められた.

4

3 に答える 3

5

大きな数は通常、浮動小数点数（非常に大きな数を格納することもできますが、精度が非常に制限されます）とは対照的に、完全精度の整数または小数です。それらは主に暗号化で使用されます。RSAキーを例にとってみましょう。これらは1024または2048ビット（約300または600の10進数）の整数です。力ずくの計算を使用して暗号化を破ることを不可能にするために、それらは長くする必要があります。

ライブラリが提供する必要があるのは、これらの数値を格納し、それらに対して計算を実行するためのサポートです（たとえば、加算、乗算、残りの整数除算）

于 2010-01-15T13:03:27.287 に答える
2

gmpのようなbignumライブラリがあります-いくつかは任意の精度を提供します（...メモリが処理できる限り）、いくつかは単にばかげた制限があります-基数256バイト、仮数256バイトの浮動小数点変数。

この方法は、FPUの通常のソフトウェアエミュレーションと非常によく似ており、計算ごとにさらに多くのバイトのデータを繰り返すだけで、操作は紙での計算方法に似ています。256バイトの整数を使用している場合は、通常の256base256桁の数値として扱うことができます。

単純な256バイト整数の加算（完全に最適化されていません...数値は長さなどを保持する必要があります）

unsigned char x[256];
unsigned char y[256];
unsigned char sum[256];
int overflow=0,tmp;
for(unsigned char i=0;i<256;i++)
{
  tmp = x[i] + y[i] + ovr;
  sum[i] = tmp % 256;
  overflow = tmp / 256;
}
于 2010-01-15T13:20:24.303 に答える
1

これらは、事前定義されたサイズの数値 (4 ビット整数型など) とは異なり、可変ビット長の数値です。

大きな数を扱う高速な C++ ライブラリの例はNTLで、特に数論と暗号化アプリケーションにも使用されます。もう 1 つの有名なツールは、デフォルトで無制限の精度で動作するunix bc計算機です。Haskell のような一部の関数型言語も、このタイプの数値を使用します。

多数の算術演算を処理するために使用されるアプローチの例は、乗算に使用されるカラツバ アルゴリズムです。興味があれば、NTL のドキュメントでさらに多くの情報を見つけることができます ;)

于 2010-01-15T13:07:47.577 に答える