2

问题：BigInt 除法的一个好的和有效的算法？

尝试：多项式长除法，整数除法（溢出余数），二进制长除法（好不好？不确定，这就是我在下面的帖子中的内容），商猜测除法（大商减法太多）。

我一直在尝试编写 BigInt 部门的代码。我最新的算法使用二进制除法，但我认为这不是最好的方法。

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

我正在使用的语言不支持传递诸如数组或各种数据类型之类的项目。我被整数和布尔值和全局数组以及在函数顶部声明的局部数组所困。

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

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

数字在除数和余数数组的末尾变得更小。它们在股息数组的开头较小。

最终答案存储在 binaryDividendBuffer 中，大小为 binaryDividendBufferSize（商），余数大小为剩余大小（余数）。这东西适用于 0 个错误，但我觉得它真的很糟糕：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
4

0 回答 0