1

大きな数値に対して算術演算を実行するアルゴリズムが必要です(これは、float、double int、またはその他のデータ型の範囲をはるかに超えています)。私は C でコードを書く必要があります。ここで調べてみました: Knuth, Donald, The Art of Computer Programming, ISBN 0-201-89684-2, Volume 2: Seminumerical Algorithms, Section 4.3.1: The Classical Algorithms but我慢できなかった。コードではなくアルゴリズムが必要です。

4

5 に答える 5

3

カラツバアルゴリズムは、大きな数に対して算術演算を実行するのに最適だと思います。nが十分に大きい場合、別の一般化であるSchönhage–Strassenアルゴリズムはさらに高速です。Karatsuba または Karatsuba_Multiplicationでアルゴリズムを探すことができます

于 2012-03-13T10:18:26.213 に答える
3

さらに、私の知る限り、単純な線形 O(n) アルゴリズムよりもはるかに優れたものは得られません。つまり、1 桁ずつ追加するだけです。とにかく、入力全体を読み取る必要がある可能性が高いため、少なくとも線形です。定数を下げるためにさまざまなトリックを実行できる場合があります。

基本的な長い乗算アルゴリズムの二次的な性質により、主な問題は乗算になります。ここに示すいくつかのはるかに高速な方法のいずれかを検討することをお勧めします。カラツバ法はうまく実装するのが少し難しいですが、おそらく利益をもたらす最も簡単で重要なアルゴリズムです。それ以外の場合は、 Schönhage-Strassen のアルゴリズムやFürer のアルゴリズムなどの高速フーリエ変換方法をもう少し調べる必要があります。

Big O表記も参照してください。

于 2011-08-05T07:12:02.803 に答える
2

非常に大きな数に対して算術演算を実行するアルゴリズムはありません。算術演算は同じままです。必要なのはhttp://www.codeproject.com/KB/cs/BigInt.aspxのようなクラスです

于 2011-08-05T12:13:54.167 に答える
1

Riesel による本素数と因数分解のためのコンピューター手法には、多倍精度演算用の読みやすいコードを含む付録があります。

于 2011-08-05T12:05:09.957 に答える
0

アルゴリズムだけについては、Knuth vol 2 または Crandall and Pomerance をお読みください。コーディングについては、カラツバまたはフーリエ変換に進む前に、最初に明らかなアルゴリズムを機能させることをお勧めします。

于 2011-08-05T10:53:27.137 に答える