質問: BigInt 除算の優れた効率的なアルゴリズムは?
試みたもの: 多項式の長除算、int による除算 (オーバーフロー剰余)、2 進長除算 (何か良いかどうかはわかりませんが、以下の投稿にあるものです)、商推測除算 (大きな商での減算が多すぎます)。
私はしばらく BigInt 除算をコーディングしようとしています。私の最新のアルゴリズムは 2 進数除算を使用していますが、これが最善の方法だとは思いません。
そこで、どのようなアルゴリズムが存在するかについていくつかのアイデアを探しています。）。
私が使用している言語は、配列やさまざまなデータ型などのアイテムの受け渡しをサポートしていません。関数の先頭で宣言されたローカル配列だけでなく、整数とブール値、グローバル配列にもこだわっています。
高速化のために 32768 のワード サイズで作業していますが、たまたま 2^15 です。このため、基数 2 への変換とその逆を迅速かつ効率的に行うことができます。そのため、バイナリ除算アルゴリズムのアプローチを試すことにしました。
私の最初のアプローチでは、状況によっては残りがオーバーフローしましたが、非常に高速でした。私の次のアプローチは、多項式の長除算のアイデアでした。商のアイデアも試してみましたが、引き算が多すぎるため、非常に大きな数では失敗します。全体として、安っぽいバイナリ除算アルゴリズムが最善の策であると思います。|。
数値は、除数配列と剰余配列の終わりに向かって小さくなります。それらは、被除数配列の先頭に向かって小さくなっています。
最終的な答えは、サイズが binaryDividendBufferSize (商) で、剰余がサイズ余剰サイズ (剰余) で binaryDividendBuffer に格納されます。このことはバグなしで動作しますが、私はそれが本当に悪いと感じています:o.
globals
private static integer array binaryDividendBuffer //division binary buffer #1 (to be divided)
private static integer binaryDividendBufferSize //division binary count #1
private static integer array binaryBufferDivisor //division binary buffer #2 (to divide)
private static integer binaryBufferDivisorSize //division binary count #2
endglobals
コード：
local integer currentDividendDigit = binaryDividendBufferSize //to be divided int digit count
local integer tempDigit2 //temp digit 2
local integer tempDigit3 //temp digit 3
local integer array remainder //remainder
local integer remainderSize = 0 //remainder count
local boolean remainderLessThanDividend //is the remainder < divisor?
local integer binaryBufferDividendDigitOffset //subtract -1 or 0 (shift the divisor by 1 bit for extra digit)
local boolean gatheredDigits //were bits gatheredDigits?
loop
//gather bits equal to the length of the divisor only if the current remainder isn't equal to length of divisor and there are bits remaining
set gatheredDigits = false
set gatheredDigits = remainderSize != binaryBufferDivisorSize and 0 != currentDividendDigit
if (gatheredDigits) then
loop
exitwhen remainderSize == binaryBufferDivisorSize or 0 == currentDividendDigit
set currentDividendDigit = currentDividendDigit - 1
set remainder[remainderSize] = binaryDividendBuffer[currentDividendDigit]
set remainderSize = remainderSize + 1
set binaryDividendBuffer[currentDividendDigit] = 0
endloop
endif
//if the remainder is smaller than the divisor and there are no bits left to gather, exit
if (remainderSize < binaryBufferDivisorSize and 0 == currentDividendDigit) then
set binaryDividendBuffer[currentDividendDigit] = 0
exitwhen true
endif
//compare the remainder and the divisor to see which one is greater
set tempDigit2 = 0
set remainderLessThanDividend = false
loop
set remainderLessThanDividend = remainder[tempDigit2] < binaryBufferDivisor[tempDigit2]
set tempDigit2 = tempDigit2 + 1
exitwhen tempDigit2 == binaryBufferDivisorSize or remainderLessThanDividend or remainder[tempDigit2] > binaryBufferDivisor[tempDigit2]
endloop
//if remainderLessThanDividend and there are bits remaining, add an additional bit
//set the dividend's current bit to 0 IF bits were gatheredDigits (division taking place)
//if bits weren't gatheredDigits, then setting it to 0 will set an already divided bit
if (remainderLessThanDividend) then
exitwhen 0 == currentDividendDigit
if (gatheredDigits) then
set binaryDividendBuffer[currentDividendDigit] = 0
endif
set currentDividendDigit = currentDividendDigit - 1
set remainder[remainderSize] = binaryDividendBuffer[currentDividendDigit]
set remainderSize = remainderSize + 1
set binaryBufferDividendDigitOffset = -1 //shift divisor's bits by 1 to account for extra digit in remainder
else
set binaryBufferDividendDigitOffset = 0 //don't shift as there is no extra digit in remainder
endif
//subtract
set binaryDividendBuffer[currentDividendDigit] = 1
set tempDigit2 = remainderSize
loop
set tempDigit2 = tempDigit2 - 1
//if only subtract if the divisor actually has a bit to do subtracting (remainder might have 1 more bit than divisor)
if (tempDigit2 + binaryBufferDividendDigitOffset > -1) then
//if the remainder's current bit is remainderLessThanDividend than the divisor's bit, borrow
if (remainder[tempDigit2] < binaryBufferDivisor[tempDigit2 + binaryBufferDividendDigitOffset]) then
set remainder[tempDigit2 - 1] = remainder[tempDigit2 - 1] - 1
set remainder[tempDigit2] = remainder[tempDigit2] + 2
endif
//subtract them
set remainder[tempDigit2] = remainder[tempDigit2] - binaryBufferDivisor[tempDigit2 + binaryBufferDividendDigitOffset]
endif
exitwhen 0 == tempDigit2
endloop
//cut out all of the 0s in front of the remainder and shift it over
//000033 -> 33
//this first loop goes through all of the 0s
loop
exitwhen 0 != remainder[tempDigit2] or tempDigit2 == remainderSize
set tempDigit2 = tempDigit2 + 1
endloop
//this loop removes the 0s by shifting over
if (0 < tempDigit2) then
if (tempDigit2 == remainderSize) then
set remainderSize = 0
set remainder[0] = 0
else
set tempDigit3 = 0
set remainderSize = remainderSize-tempDigit2
loop
set remainder[tempDigit3] = remainder[tempDigit3+tempDigit2]
set remainder[tempDigit3+tempDigit2] = 0
set tempDigit3 = tempDigit3 + 1
exitwhen tempDigit3 == remainderSize
endloop
endif
endif
exitwhen 0 == currentDividendDigit
endloop
//cut out all of the 0s in front of dividend
loop
exitwhen 0 != binaryDividendBuffer[binaryDividendBufferSize]
set binaryDividendBufferSize = binaryDividendBufferSize - 1
endloop