# _LongProduct

## Recommended Posts

_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 on other sites

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

## Create an account

Register a new account

• ### Recently Browsing   0 members

×

• Wiki

• Back

• #### Beta

• Git
• FAQ
×
• Create New...