czardas Posted December 25, 2013 Share Posted December 25, 2013 (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. ; 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 operator64 ArrayWorkshop Link to comment Share on other sites More sharing options...

czardas Posted December 26, 2013 Author Share Posted December 26, 2013 (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 December 26, 2013 by czardas operator64 ArrayWorkshop Link to comment Share on other sites More sharing options...

## Recommended Posts

## 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