Sign in to follow this  
Followers 0
czardas

_LongProduct

2 posts in this topic

#1 ·  Posted (edited)

_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.

;

; #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 by czardas

Share this post


Link to post
Share on other sites



#2 ·  Posted (edited)

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 by czardas

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0