5

大きな整数 (128 ビット) を処理できる除算アルゴリズムが必要です。ビットシフト演算子を介してそれを行う方法をすでに尋ねました。ただし、私の現在の実装では、より良いアプローチが必要なようです

基本的に、数字を 2long long unsigned intの形式で保存します

A * 2 ^ 64 + BとB < 2 ^ 64。

この数は で割り切れる24ので、 で割りたいです24。

私の現在のアプローチは、それを次のように変換することです

A * 2 ^ 64 + B     A             B
--------------  = ---- * 2^64 + ----
      24           24            24

           A               A mod 24                    B         B mod 24
= floor( ---- ) * 2^64 +  ---------- * 2^64 + floor( ---- ) +   ----------
           24               24.0                      24           24.0

ただし、これはバグです。

(floor はA / 24であり、modはであることに注意してくださいA % 24。通常の除算は に格納されlong double、整数は に格納されlong long unsigned intます。

24はバイナリで等しいので11000、2 番目の被加数は 4 番目の加数の範囲内で何かを変更してはなりません。これは、64 ビット左にシフトされるためです。

したがって、A * 2 ^ 64 + Bが 24 で割り切れ、B が割り切れない場合、非整数を返すため、バグがあることが簡単にわかります。

私の実装のエラーは何ですか?

4

5 に答える 5

13

これを行う最も簡単な方法は、128 ビットの数値を 4 つの 32 ビットの数値として扱うことです。

A_B_C_D = A*2^96 + B*2^64 + C*2^32 + D

そして、24 による長除算を行います。

E = A/24 (with remainder Q)
F = Q_B/24 (with remainder R)
G = R_C/24 (with remainder S)
H = S_D/24 (with remainder T)

どこでX_Yを意味しX*2^32 + Yます。次に、答えはE_F_G_H余りありTます。いつでも 64 ビット数値の除算のみが必要なので、これは整数演算でのみ実行できるはずです。

于 2009-11-27T13:12:09.273 に答える
2

これは逆乗算で解決できますか? 最初に注意すべきことは24 == 8 * 3、

a / 24 == (a >> 3) / 3

するとx = (a >> 3)、除算の結果は になり8 * (x / 3)ます。の値を見つけることが残っていますx / 3。

n剰余演算では、 のような数が存在すると述べていn * 3 == 1 (mod 2^128)ます。これは与える：

x / 3 = (x * n) / (n * 3) = x * n

定数を見つけることは残っていますn。ウィキペディアでこれを行う方法についての説明があります。また、128 ビットの数値に乗算する機能を実装する必要があります。

お役に立てれば。

/AB

于 2009-11-27T13:45:46.290 に答える
1

しないでください。

このようなことを行うためにライブラリを入手してください - 奇妙なエラーをデバッグするときにライブラリを選択したことに非常に感謝しています。

少し前に Snippets.org のサイトに C/C++ BigInt ライブラリがありましたが、Google も次のサイトを見つけました: http://mattmccutchen.net/bigint/

于 2009-11-27T12:49:04.640 に答える
1

long double「通常の除算」には使用しないでくださいが、そこにも整数を使用する必要があります。long double答えを正しく得るのに十分な有効数字がありません (そして、全体のポイントは整数演算でこれを行うことですよね?)。

于 2009-11-27T12:31:39.130 に答える
1

24 は 2 進数で 11000 に等しいため、2 番目の被加数は 4 番目の加数の範囲内で何かを変更してはなりません。これは、左に 64 ビットシフトされるためです。

あなたの式は実数で書かれています。(A mod 24) / 24 は任意の小数点以下の桁数 (1/24 はたとえば 0.041666666...) を持つことができるため、2^64 を掛けても、分解の第 4 項に干渉する可能性があります。

Y*2^64 が足し算で重みの低い 2 進数に干渉しないという特性は、Y が整数の場合にのみ機能します。

于 2009-11-27T12:32:32.867 に答える