编码 BigInt 除法

Question

问题：BigInt 除法有一个好的、高效的算法吗？

尝试过：多项式长除法、整数除法（溢出余数）、二进制长除法（有什么好处？不确定，这就是我在下面的帖子中所做的）、猜商除法（太多大商的减法）。

我尝试编写 BigInt 除法有一段时间了。我最新的算法使用二进制除法，但我不认为这是最好的方法。

所以我正在寻找一些关于可能存在哪些算法的想法； ）。

我正在使用的语言不支持传递数组或各种数据类型等项目。我陷入了整数、布尔值、全局数组以及在函数顶部声明的本地数组的困境。

为了提高速度，我使用的字大小为 32768，恰好是 2^15。正因为如此，我可以快速有效地转换为基数 2 并返回，这就是我决定尝试二进制除法算法方法的原因。

我的第一种方法在某些情况下会导致剩余部分溢出，但速度非常快。我的下一个方法是多项式长除法的想法。我也尝试了商的想法，尽管它在非常大的数字上会失败，因为涉及太多的减法。总的来说，我认为蹩脚的二元除法算法可能是最好的选择； |。

接近除数和余数数组末尾的数字会变小。它们在股息数组开始时较小。

最终答案存储在binaryDividendBuffer中，其大小为binaryDividendBufferSize（商），余数的大小为remainingSize（余数）。这个东西的 bug 为零，但我有一种感觉，它真的很糟糕: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