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. =)
Printable View
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. =)
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%) but with some overhead of Variant.
Even better if use VB.Net with unsigned(?) 64-bit integer.
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.
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.Code: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
Code: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
Perhaps we could use the following function as an alternative to mod?
Code:Private Function getMod(ByVal a As Long, ByVal b As Long) As Long
getMod = a - (b * Fix(a / b))
End Function
I think I will proceed from here, thanks everyone, BigMultiplyLong should be sufficient.
@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.
Stupid question but is there some minimal limit on how long the strings passed need to be? BigMultiplyLong seems to be wrong. :confused:
Code: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
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:
With this:Code: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
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.Code: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
@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.
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:
Code: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.Quote:
Originally Posted by edgemeal
The most significant improvement there is ditching Join and building the result string with Mid. (I was going to do that.)Quote:
Originally Posted by anhn
Wow, that is exceedingly fast. Thank you so much and to all others who have contributed, they are really much appreciated. VBForums really rocks. :thumb:Quote:
Originally Posted by anhn
You may be interested of this class module.
PSC submission in Merri's link above migrated to github:
cheers,
</wqw>