•  05-07-2019
  •  | 
  •  

質問

大きな整数（128ビット）を処理できる除算アルゴリズムが必要です。 ビットシフト演算子を使用してそれを行う方法については既に質問しました。しかし、私の現在の実装では、より良いアプローチを求めているようです

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

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

この数は24で割り切れるので、A / 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はmodであり、A % 24はlong doubleであることに注意してください。通常の区分は11000に格納され、整数は<=>に格納されます。

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

したがって、<=>が24で割り切れ、Bが割り切れない場合、整数ではない数値を返すため、バグであることを簡単に示します。

実装のエラーは何ですか？

役に立ちましたか？

解決

これを行う最も簡単な方法は、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ビット数の除算のみが必要なので、これは整数演算でのみ実行可能です。

他のヒント

これは逆乗算でおそらく解決できますか？最初に注意することは、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

定数<=>を見つけることは残っています。これを行う方法については、 wikipedia に説明があります。また、128ビット数に乗算する機能を実装する必要があります。

これがお役に立てば幸いです。

/A.B。

<！> quot;通常の分割<！> quot;にlong doubleを使用しないでください。整数もあります。 <=>には正しい答えを得るのに十分な有効数字がありません（そして、とにかく整数演算でこれを行うのが正解ですか？）。

  

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

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

Y * 2 ^ 64が加算でより低い重みの2進数と干渉しないというプロパティは、Yが整数の場合にのみ機能します。

しないでください。

このようなことをするためにライブラリを手に入れてください-奇妙なエラーをデバッグするときに選んだことは信じられないほど感謝しています。

Snippets.orgのサイトにはC / C ++ BigIntライブラリが少し前にありましたが、Googleは次のことも明らかにしました。 http://mattmccutchen.net/bigint/

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top