_LongProduct

[czardas]

_LongProduct - Multiply two large integers using 'old school' long multiplication.

I wanted to have a go at this for a while. It's not breaking any new ground but it has been a useful exercise for me. I haven't looked at BigNum UDF functions in any detail - I really wanted to try this out for myself.

;

expandcollapse popup

; #FUNCTION# ====================================================================================================================
; Name...........: _LongProduct
; Description ...: Multiplies two large positive integers together using old school long multiplication method
; Syntax.........: _LongProduct($vInt1, $vInt2)
; Parameters ....: $vInt1  - First integer - can be a number or a string of digits
;                  $vInt2  - Second integer - as above
; Return values .: Success - Returns the product of the two numbers
;                  Failure - Sets @error to 1 if either parameter contains non digit characters
; Author ........: czardas
; Comments ......; A separate function must be created if you want to preprocess floating point numbers
; ===============================================================================================================================

Func _LongProduct($vInt1, $vInt2)
    If Not (StringIsDigit($vInt1) And StringIsDigit($vInt2)) Then Return SetError(1)

    Local $vTemp ; Reuseable placeholder
    If StringLen($vInt2) > StringLen($vInt1) Then
        ; Set $vInt2 to be the shortest numeric string to reduce array size later
        $vTemp = $vInt1
        $vInt1 = $vInt2
        $vInt2 = $vTemp
    EndIf

    Local $iBound = StringLen($vInt2), $sZeros = "0" ; Zero padding for the method of long multiplication

    While StringLen($sZeros) < $iBound
        $sZeros &= $sZeros ; Tens, hundreds, thousands etc...
    WEnd
    $sZeros = StringRight($sZeros, $iBound -1) ; Highest order of magnitude needed

    Local $aPartProduct[$iBound], $iCarryForward ; Placeholder for tens of units, hundreds, thousands etc...

    For $i = 1 To $iBound ; Starting with the most significant digit in $vInt2
        $aPartProduct[$i -1] = ""
        $iCarryForward = 0 ; Maximum possible value in this code section is 8 ==> 89 = 9*9+8

        For $j = StringLen($vInt1) To 1 Step -1
            ; Multiply every digit in $vInt2 by every digit in $vInt1
            $vTemp = StringMid($vInt2, $i, 1) * StringMid($vInt1, $j, 1)

            ; Add the tens of units left over from the previous calculation
            $vTemp += $iCarryForward
            $iCarryForward = Number(StringTrimRight($vTemp, 1)) ; This will be added on the next run

            ; Append the units
            $aPartProduct[$i -1] &= StringRight($vTemp, 1) ; Digits appear in reverse sequence
        Next
        $aPartProduct[$i -1] &= $iCarryForward

        ; Pad with the correct number of zeros
        $aPartProduct[$i -1] = StringRight($sZeros, $iBound - $i) & $aPartProduct[$i -1] & StringTrimRight($sZeros, $iBound - $i)
    Next
    $iCarryForward = 0 ; Reset this variable for the following process

    ; Take the sum of all the part products in the array
    Local $sProduct = ""
    For $i = 1 To StringLen($aPartProduct[0]) ; Starting with the least significant digit
        $vTemp = 0 ; Sum value
        For $j = 0 To UBound($aPartProduct) -1
            ; Add the digits from the units, tens of units, hundreds, thousands etc...
            $vTemp += StringMid($aPartProduct[$j], $i, 1)
        Next

        ; Add the value left over from the previous calculation
        $vTemp += $iCarryForward
        $iCarryForward = Number(StringTrimRight($vTemp, 1)) ; This will be added on the next run

        $sProduct = StringRight($vTemp, 1) & $sProduct ; Returns the digits in the correct order
    Next
    If $iCarryForward Then $sProduct = $iCarryForward & $sProduct

    If StringLeft($sProduct, 1) = "0" Then $sProduct = StringTrimLeft($sProduct, 1)
    Return $sProduct
EndFunc ;==> _LongProduct

;

Example

Local $i1 = "192801867453620948267810191872736619839409271"
Local $i2 = "99999999999999999999999999999999999999999989"
ConsoleWrite(_LongProduct($i1, $i2) & @LF)

Edited December 25, 2013 by czardas

[czardas]

I just did a comparison between this function and _BigNum_Mul() from the BigNum UDF. The difference in speed is quite large. _BigNum_Mul() wins hands down. I don't fully understand the process used by _BigNum_Mul() but it's nice to see that at least the results concur.

I was just thinking about this 'old school' method. It uses base 10 and works on individual digits - as a human would do. With a computer, this limitation can be removed to some degree. I wonder if it would be possible to work in base 10000000 and process 7 digits at a time - limits being imposed by AutoIt. I don't see why this can't be done - perhaps I'm missing something. It should increase speed by a significant factor, so I might try it one day.

I remember reading a book once about music theory. In this book it was suggested that replacing the older theory with modern theory had been a mistake; and musicians only realized this several hundered years later. The sentence went something like this:

When the major / minor system replaced the modes, they threw out the baby along with the bath water.

Edited December 26, 2013 by czardas