[RESOLVED] Optimize multiplication of large numbers

[dee-u]

This is the method courtesy from anhn, I just wish to optimize its speed.

Or perhaps if there is a faster method then I would appreciate it if someone shares. =)

[anhn]

As in PM to you:

Try to use the same method but instead of groups of single digits, divide both number strings into arrays of 7-digit true Currency numbers then treat each of these numbers as a BIG_DIGIT for multiplying. That will speed up very much.

If use 14-digit numbers you can switch to Decimal (Variant) with less number of multiplyings (down to 25&#37 but with some overhead of Variant.

Even better if use VB.Net with unsigned(?) 64-bit integer.

[Logophobic]

Interestingly, I noticed a PM from dee-u referring me to this thread as I was about to post this reply.

This code, which uses bytes as in anhn's code, is nearly twice as fast as his.
Two major differences:
1) I'm converting the big-endian strings to little-endian arrays.
2) I'm doing the addition "on the fly", eliminating the need for a matrix.

Private Function BigMultiply(sNum1 As String, sNum2 As String) As String
  Dim bt1() As Byte
  Dim bt2() As Byte
  Dim bt3() As Byte
  Dim i As Long, j As Long, tmp As Byte
  
  bt1 = StrConv(StrReverse(sNum1), vbFromUnicode)
  For i = 0 To UBound(bt1): bt1(i) = bt1(i) - 48: Next
  bt2 = StrConv(StrReverse(sNum2), vbFromUnicode)
  For i = 0 To UBound(bt2): bt2(i) = bt2(i) - 48: Next
  
  ReDim bt3(UBound(bt1) + UBound(bt2) + 1)
  For j = 0 To UBound(bt1)
    If bt1(j) > 0 Then
      For i = 0 To UBound(bt2)
        tmp = bt1(j) * bt2(i) + bt3(i + j) + tmp
        bt3(i + j) = tmp Mod 10
        tmp = tmp \ 10
      Next i
      
      Do Until tmp = 0
        tmp = bt3(i + j) + tmp
        bt3(i + j) = tmp Mod 10
        tmp = tmp \ 10
      Loop
    End If
  Next j
  
  For i = 0 To UBound(bt3): bt3(i) = bt3(i) + 48: Next
  BigMultiply = StrReverse(StrConv(bt3, vbUnicode))
End Function

This code is a modification of the above, using Long instead of Byte and working in base-10000 (4-digit grouping) instead of base-10. It is about 20 times as fast as anhn's original code. The Mod operator does not allow for the 7-digit grouping that anhn suggests.

Private Function BigMultiplyLong(sNum1 As String, sNum2 As String) As String
  Dim lngArray1() As Long
  Dim lngArray2() As Long
  Dim lngArray3() As Long
  Dim strArray() As String
  Dim i As Long, j As Long, tmp As Long
  
  i = Len(sNum1) \ 4
  tmp = Len(sNum1) Mod 4
  If tmp <> 0 Then
    ReDim lngArray1(i)
    lngArray1(i) = CLng(Mid$(sNum1, 1, tmp))
    i = i - 1
  Else
    i = i - 1
    ReDim lngArray1(i)
  End If
  
  For j = tmp + 1 To Len(sNum1) Step 4
    lngArray1(i) = CLng(Mid$(sNum1, j, 4))
    i = i - 1
  Next j
  
  i = Len(sNum2) \ 4
  tmp = Len(sNum2) Mod 4
  If tmp <> 0 Then
    ReDim lngArray2(i)
    lngArray2(i) = CLng(Mid$(sNum2, 1, tmp))
    i = i - 1
  Else
    i = i - 1
    ReDim lngArray2(i)
  End If
  
  For j = tmp + 1 To Len(sNum2) Step 4
    lngArray2(i) = CLng(Mid$(sNum2, j, 4))
    i = i - 1
  Next j
  
  ReDim lngArray3(UBound(lngArray1) + UBound(lngArray2) + 1)
  tmp = 0 ' Thanks, Edgemeal
  For j = 0 To UBound(lngArray1)
    If lngArray1(j) > 0 Then
      For i = 0 To UBound(lngArray2)
        tmp = lngArray1(j) * lngArray2(i) + lngArray3(i + j) + tmp
        lngArray3(i + j) = tmp Mod 10000
        tmp = tmp \ 10000
      Next i
      
      If tmp > 0 Then
        lngArray3(i + j) = lngArray3(i + j) + tmp
        tmp = 0
      End If
    End If
  Next j
  
  j = UBound(lngArray3)
  ReDim strArray(j)
  For i = 0 To j - 1
    strArray(j - i) = Format(lngArray3(i), "0000")
  Next i
  If lngArray3(j) > 0 Then strArray(0) = Format(lngArray3(j), "0")
  BigMultiplyLong = Join(strArray, "")
End Function

[dee-u]

Perhaps we could use the following function as an alternative to mod?

Private Function getMod(ByVal a As Long, ByVal b As Long) As Long
    getMod = a - (b * Fix(a / b))
End Function

[dee-u]

I think I will proceed from here, thanks everyone, BigMultiplyLong should be sufficient.

[anhn]

@Logophobic, You are the best when come to optimization.
For a quick reply, I wrote the original function in about 5 minutes, as you see it just simulates "primary school method" and it works. I left some suggestions there for improving as I already did that a year ago but now I lost my code and haven't got time to redo it yet.

Grouping digits is a right choice as I mentioned. Of course, Mod only works with Long (or lower), when using with Currency or Decimal we have to use an equivalent calculation such as dee-u mentioned but use inline code instead of calling a function.
n = a - Int(a / b) * b
This has another little overhead with / but not much.

I even went to 14-digit grouping with Decimal sub-type and the speed was just a little bit better when compare with 7-digit grouping with Currency as there was a big overhead with Decimal Variant altho the number of multiplies was droped to only about 25%.

With any method used, another thing must be considered is trying to avoid String concatination at any cost, that is the most time consuming in the process.

[Edgemeal]

Stupid question but is there some minimal limit on how long the strings passed need to be? BigMultiplyLong seems to be wrong.

Debug.Print BigMultiplyLong("12", "12") 'return = 146
Debug.Print BigMultiply("12", "12") 'return = 144

Debug.Print BigMultiplyLong("123456789", "123456789") ' return = 15241578750190522
Debug.Print BigMultiply("123456789", "123456789")      'return = 15241578750190521

BigMultiplyLong("987654321123456789", "987654321123456789")' = 975461058033836303240512116750190523
BigMultiply("987654321123456789", "987654321123456789")    ' = 975461058033836303240512116750190521

[Logophobic]

AACK!! A BUUUUUGGGGG!!!!

The tmp variable needs to be zero when the loop starts, but because I used it earlier in the code, it is causing trouble. I overlooked the error because the lengths of the strings I tested were multiples of 100, which of course resulted in tmp having a value of zero (100 Mod 4). Reset tmp to zero before entering the loop.

Now that I've had time to work around the limitations of Mod, here is a further optimization. Replace this:

      For i = 0 To UBound(lngArray2)
        tmp = lngArray1(j) * lngArray2(i) + lngArray3(i + j) + tmp
        lngArray3(i + j) = tmp Mod 10000&
        tmp = tmp \ 10000&
      Next i

With this:

      For i = 0 To UBound(lngArray2)
        lngArray3(i + j) = lngArray1(j) * lngArray2(i) + lngArray3(i + j) + tmp
        tmp = lngArray3(i + j) \ 10000&
        lngArray3(i + j) = lngArray3(i + j) - tmp * 10000&
      Next i

The new code runs 20% to 30% faster. It also works with the 7-digit grouping using Double instead of Long, which proved to be even faster. Currency, on the other hand, was significantly slower. Decimal was roughly equivalent to Long and Double with small (100-digit) numbers, but clearly lost with larger (1000- and 10000-digit) numbers.

@anhn: The code I posted (using Byte arrays) is essentially the same as the arbitrary-precision arithmetic code that I wrote during and following the discussion that Ellis Dee linked to in the other thread.

[anhn]

Yeah! I saw the bug with tmp.

I don't know why but I use Excel VBA and see that your updated loop to replace Mod does not improve the speed if not a bit slower than the previous loop with Mod. I don't have a chance to test with VB6 IDE or compiled code.

This is my version with Double (with error checked) that can run nearly twice faster than your Long version in Excel VBA:

Private Function BigMultiplyDouble(ByVal sNum1 As String, ByVal sNum2 As String) As String
   Const TenPower7 As Double = 10000000#
   Dim arNum1()    As Double
   Dim arNum2()    As Double
   Dim arNum3()    As Double
   Dim c           As Double
   Dim sTemp       As String
   Dim i As Long, j As Long, k As Long
   Dim n1 As Long, n2 As Long, n3 As Long
   
   '-- return "" if sNum1 or sNum2 is invalid
   If sNum1 Like "*[!0-9]*" Then Exit Function
   If sNum2 Like "*[!0-9]*" Then Exit Function
   '-- remove leading 0's
   Do While Left$(sNum1, 1) = "0": sNum1 = Mid$(sNum1, 2): Loop
   Do While Left$(sNum2, 1) = "0": sNum2 = Mid$(sNum2, 2): Loop
   '-- return "0" either sNum1 or sNum2 = "" (or "0")
   If Len(sNum1) = 0 Or Len(sNum2) = 0 Then BigMultiplyDouble = "0": Exit Function
'   '-- swap to have Len(sNum2) < Len(sNum1)
'   If Len(sNum1) < Len(sNum2) Then sTemp = sNum1: sNum1 = sNum2: sNum2 = sTemp
   
   '-- split sNum1 to arNum1() of Double
   n1 = (Len(sNum1) - 1) \ 7
   ReDim arNum1(0 To n1)
   k = Len(sNum1) Mod 7
   i = n1
   If k Then
      arNum1(i) = CDbl(Mid$(sNum1, 1, k))
      i = i - 1
   End If
   For j = k + 1 To Len(sNum1) Step 7
      arNum1(i) = CDbl(Mid$(sNum1, j, 7))
      i = i - 1
   Next
      
   '-- split sNum2 to arNum2() of Double
   n2 = (Len(sNum2) - 1) \ 7
   ReDim arNum2(0 To n2)
   k = Len(sNum2) Mod 7
   i = n2
   If k Then
      arNum2(i) = CDbl(Mid$(sNum2, 1, k))
      i = i - 1
   End If
   For j = k + 1 To Len(sNum2) Step 7
      arNum2(i) = CDbl(Mid$(sNum2, j, 7))
      i = i - 1
   Next
      
   '-- final array with maximum of n3+1 elements
   n3 = n1 + n2 + 1
   ReDim arNum3(0 To n3)
   
   '-- multiplying process
   c = 0
   For i = 0 To n2
      If arNum2(i) > 0 Then
         For j = 0 To n1
            arNum3(i + j) = arNum3(i + j) + arNum1(j) * arNum2(i) + c
            If arNum3(i + j) > TenPower7 Then
               c = Int(arNum3(i + j) / TenPower7)
               arNum3(i + j) = arNum3(i + j) - c * TenPower7
            Else
               c = 0
            End If
         Next
         If c > 0 Then
            arNum3(i + n1 + 1) = arNum3(i + n1 + 1) + c
            c = 0
         End If
      End If
   Next
   
   '-- output result
   If arNum3(n3) = 0 Then n3 = n3 - 1
   k = 7 * n3 + Len(CStr(arNum3(n3)))
   BigMultiplyDouble = String$(k, "0")
   For i = 0 To n3
      sTemp = CStr(arNum3(i))
      Mid$(BigMultiplyDouble, k - i * 7 - Len(sTemp) + 1, Len(sTemp)) = sTemp
   Next

End Function

Stupid question but is there some minimal limit on how long the strings passed need to be?

Virtually there is no limit on the length of the number strings. That is only limited by the maximum length of a string the system can handle (is that ~ 2GB ?) or at least the maimum number of Long indexing (2^31-1) used in the code.

[Logophobic]

This is my version with Double (with error checked) that can run nearly twice faster than your Long version in Excel VBA

The most significant improvement there is ditching Join and building the result string with Mid. (I was going to do that.)

[dee-u]

Yeah! I saw the bug with tmp.

I don't know why but I use Excel VBA and see that your updated loop to replace Mod does not improve the speed if not a bit slower than the previous loop with Mod. I don't have a chance to test with VB6 IDE or compiled code.

This is my version with Double (with error checked) that can run nearly twice faster than your Long version in Excel VBA:

Private Function BigMultiplyDouble(ByVal sNum1 As String, ByVal sNum2 As String) As String
   Const TenPower7 As Double = 10000000#
   Dim arNum1()    As Double
   Dim arNum2()    As Double
   Dim arNum3()    As Double
   Dim c           As Double
   Dim sTemp       As String
   Dim i As Long, j As Long, k As Long
   Dim n1 As Long, n2 As Long, n3 As Long
   
   '-- return "" if sNum1 or sNum2 is invalid
   If sNum1 Like "*[!0-9]*" Then Exit Function
   If sNum2 Like "*[!0-9]*" Then Exit Function
   '-- remove leading 0's
   Do While Left$(sNum1, 1) = "0": sNum1 = Mid$(sNum1, 2): Loop
   Do While Left$(sNum2, 1) = "0": sNum2 = Mid$(sNum2, 2): Loop
   '-- return "0" either sNum1 or sNum2 = "" (or "0")
   If Len(sNum1) = 0 Or Len(sNum2) = 0 Then BigMultiplyDouble = "0": Exit Function
'   '-- swap to have Len(sNum2) < Len(sNum1)
'   If Len(sNum1) < Len(sNum2) Then sTemp = sNum1: sNum1 = sNum2: sNum2 = sTemp
   
   '-- split sNum1 to arNum1() of Double
   n1 = (Len(sNum1) - 1) \ 7
   ReDim arNum1(0 To n1)
   k = Len(sNum1) Mod 7
   i = n1
   If k Then
      arNum1(i) = CDbl(Mid$(sNum1, 1, k))
      i = i - 1
   End If
   For j = k + 1 To Len(sNum1) Step 7
      arNum1(i) = CDbl(Mid$(sNum1, j, 7))
      i = i - 1
   Next
      
   '-- split sNum2 to arNum2() of Double
   n2 = (Len(sNum2) - 1) \ 7
   ReDim arNum2(0 To n2)
   k = Len(sNum2) Mod 7
   i = n2
   If k Then
      arNum2(i) = CDbl(Mid$(sNum2, 1, k))
      i = i - 1
   End If
   For j = k + 1 To Len(sNum2) Step 7
      arNum2(i) = CDbl(Mid$(sNum2, j, 7))
      i = i - 1
   Next
      
   '-- final array with maximum of n3+1 elements
   n3 = n1 + n2 + 1
   ReDim arNum3(0 To n3)
   
   '-- multiplying process
   c = 0
   For i = 0 To n2
      If arNum2(i) > 0 Then
         For j = 0 To n1
            arNum3(i + j) = arNum3(i + j) + arNum1(j) * arNum2(i) + c
            If arNum3(i + j) > TenPower7 Then
               c = Int(arNum3(i + j) / TenPower7)
               arNum3(i + j) = arNum3(i + j) - c * TenPower7
            Else
               c = 0
            End If
         Next
         If c > 0 Then
            arNum3(i + n1 + 1) = arNum3(i + n1 + 1) + c
            c = 0
         End If
      End If
   Next
   
   '-- output result
   If arNum3(n3) = 0 Then n3 = n3 - 1
   k = 7 * n3 + Len(CStr(arNum3(n3)))
   BigMultiplyDouble = String$(k, "0")
   For i = 0 To n3
      sTemp = CStr(arNum3(i))
      Mid$(BigMultiplyDouble, k - i * 7 - Len(sTemp) + 1, Len(sTemp)) = sTemp
   Next

End Function

Virtually there is no limit on the length of the number strings. That is only limited by the maximum length of a string the system can handle (is that ~ 2GB ?) or at least the maimum number of Long indexing (2^31-1) used in the code.

Wow, that is exceedingly fast. Thank you so much and to all others who have contributed, they are really much appreciated. VBForums really rocks.

[Merri]

You may be interested of this class module.

[wqweto]

PSC submission in Merri's link above migrated to github:

BigMath 1.1 (updated July 8, 2007)

cheers,
</wqw>