+- QB64 Phoenix Edition (https://qb64phoenix.com/forum)
+-- Forum: Chatting and Socializing (https://qb64phoenix.com/forum/forumdisplay.php?fid=11)
+--- Forum: General Discussion (https://qb64phoenix.com/forum/forumdisplay.php?fid=2)
+--- Thread: Faster addition in string math. Now with multiplication! (/showthread.php?tid=784)
Faster addition in string math. Now with multiplication! - Pete - 08-18-2022
RE: Faster addition in string math. - SMcNeill - 08-18-2022
Change to DIM AS _UNSIGNED _INTEGER64 a, b -- you can add 18 digits at a time.
RE: Faster addition in string math. - Pete - 08-18-2022
(08-18-2022, 08:16 PM)SMcNeill Wrote: Change to DIM AS _UNSIGNED _INTEGER64 a, b -- you can add 18 digits at a time.
My goof. I thought _integer64 was not affecting it, but I'm not used to using the new multi-variable DIM method, so I tried...
DIM a, b AS _INTEGER64
instead of...
DIM AS _INTEGER64 a, b
As you posted. Tried that, and it worked, thanks; however....
I can get 18 digits with that just fine. Hey, interesting about adding the _UNSIGNED. It worked for addition, but blows up for subtraction.
Code: (Select All)
DIM AS _UNSIGNED _INTEGER64 a, b, c
WIDTH 130, 42
_SCREENMOVE 0, 0
a$ = "12345"
b$ = "9999"
'a$ = "986064865096859658629068509685926859068559628695645692662625654605600654654111"
'b$ = "90334052236956578596728693574835692623537583457435345236254653969569966222"
op$ = "-"
DO
i&& = i&& + 1
x1$ = MID$(a$, LEN(a$) - i&& + 1, 1)
x2$ = MID$(b$, LEN(b$) - i&& + 1, 1)
SELECT CASE op$
CASE "+"
a = VAL(x1$) + VAL(x2$) + c
IF a > 9 THEN a = a - 10: c = 1 ELSE c = 0
PRINT x1$;: LOCATE , 25: PRINT x2$;: LOCATE , 50: PRINT VAL(x1$) + VAL(x2$);: LOCATE , 75: PRINT c;: LOCATE , 90: PRINT a
CASE "-"
a = VAL(x1$) - VAL(x2$) - c
IF a < 0 THEN a = a + 10: c = 1 ELSE c = 0
PRINT x1$;: LOCATE , 25: PRINT x2$;: LOCATE , 50: PRINT VAL(x1$) - VAL(x2$);: LOCATE , 75: PRINT c;: LOCATE , 90: PRINT a
END SELECT
z$ = LTRIM$(STR$(a)) + z$
LOOP UNTIL i&& >= LEN(a$) AND i&& >= LEN(b$)
' Remove leading zeros for subtraction.
PRINT
IF op$ = "+" THEN PRINT VAL(a$) + VAL(b$), "QB64 VAL()." ELSE PRINT VAL(a$) - VAL(b$), "QB64 VAL()."
PRINT " "; z$, "String Math."I included the variable c in the DIM statement, but it made no difference. The a variable is the one getting screwed up during subtraction. Switch to addition, op$ = "+" and it works. Remove _UNASSIGNED and it works, too. So something is weird with _UNASSIGNED and subtraction, even when it is one-digit at a time, as in the above example.
Pete
RE: Faster addition in string math. - SMcNeill - 08-18-2022
Here's the trick for subtracting string math -- it's just addition !!
-3 - 3... if the signs are the same, you just add the values and keep the sign. -3 + -3
3 - 4 or 4 - 3... if signs are different, the result will always be the sign of the largest number.
3 - 4 is 3 + -4. 4 is larger than 3, so we use the sign on the 4 for the result. (-) The swap a and b so a is 4, b is 3, and subtract up to 18 digits at a time.
That's all there is to it.
RE: Faster addition in string math. - SMcNeill - 08-18-2022
01234567890 (leading zero for forum formatting.)
-9876543210
=========
Sign is -, as 9876543210 > 1235667890.
09876543210
-1234567890
==========
Take 3 digits from top, 2 digits from bottom. Subtract 210 - 90 = 120. Right 2 digits is answer, substitute left digit back up top for carryover.
098765431
-12345678
=========
???????????20
Continue process, but with 18/17 digits at a time for unsigned int64 limits.
RE: Faster addition in string math. - SMcNeill - 08-18-2022
I think from the way your code looks @Pete, what you need the most is a few helper functions like the following:
Code: (Select All)
Screen _NewImage(1280, 720, 32)
_Define A-Z As _FLOAT
Randomize Timer
For i = 1 To 10
a$ = Str$(10 * Rnd) 'let's use some non-matching values here so that we get a good range
b$ = Str$(-1000000000000 * Rnd)
Print a$, b$, "Original"
FixNumbers a$, b$
Print a$, b$, "Normalized"
Print "---------------"
Next
Sleep
Sub FixNumbers (a$, b$)
'first remove scientific notation and spaces from both
a$ = _Trim$(N2S$(a$)): b$ = _Trim$(N2S$(b$))
'then find the decimal position for both and normalize the expressions
d1 = InStr(a$, "."): d2 = InStr(b$, ".")
If d1 <> 0 Then 'break down the left and right side of the decimal point for ease of processing (this is a$)
lefta$ = Left$(a$, d1 - 1)
righta$ = Mid$(a$, d1)
Else
lefta$ = a$
End If
If d2 <> 0 Then 'break down the left and right side of the decimal point for ease of processing (this is b$)
leftb$ = Left$(b$, d2 - 1)
rightb$ = Mid$(b$, d2)
Else
leftb$ = b$
End If
'normalize the right side of our expressions
l1 = Len(righta$): l2 = Len(rightb$)
If l1 < l2 Then
addzero = l2 - l1
If l1 = 0 Then righta$ = ".": addzero = addzero - 1
righta$ = righta$ + String$(addzero, "0")
ElseIf l1 > l2 Then
addzero = l1 - l2
If l2 = 0 Then rightb$ = ".": addzero = addzero - 1
rightb$ = rightb$ + String$(addzero, "0")
End If
'strip off any plus/minus signs from the two numbers.
If Left$(lefta$, 1) = "-" Then signa$ = "-": lefta$ = Mid$(lefta$, 2)
If Left$(leftb$, 1) = "-" Then signb$ = "-": leftb$ = Mid$(leftb$, 2)
If Left$(lefta$, 1) = "+" Then signa$ = "": lefta$ = Mid$(lefta$, 2)
If Left$(leftb$, 1) = "+" Then signb$ = "": leftb$ = Mid$(leftb$, 2)
'normalize the left side of our expressions
l1 = Len(lefta$): l2 = Len(leftb$)
If l1 < l2 Then
addzero = l2 - l1
lefta$ = String$(addzero, "0") + lefta$
ElseIf l1 > l2 Then
addzero = l1 - l2
leftb$ = String$(addzero, "0") + leftb$
End If
'and then put it all together
a$ = signa$ + lefta$ + righta$
b$ = signb$ + leftb$ + rightb$
End Sub
Function N2S$ (exp$) 'scientific Notation to String
t$ = LTrim$(RTrim$(exp$))
If Left$(t$, 1) = "-" Or Left$(t$, 1) = "N" Then sign$ = "-": t$ = Mid$(t$, 2)
dp = InStr(t$, "D+"): dm = InStr(t$, "D-")
ep = InStr(t$, "E+"): em = InStr(t$, "E-")
check1 = Sgn(dp) + Sgn(dm) + Sgn(ep) + Sgn(em)
If check1 < 1 Or check1 > 1 Then N2S = exp$: Exit Function 'If no scientic notation is found, or if we find more than 1 type, it's not SN!
Select Case l 'l now tells us where the SN starts at.
Case Is < dp: l = dp
Case Is < dm: l = dm
Case Is < ep: l = ep
Case Is < em: l = em
End Select
l$ = Left$(t$, l - 1) 'The left of the SN
r$ = Mid$(t$, l + 1): r&& = Val(r$) 'The right of the SN, turned into a workable long
If InStr(l$, ".") Then 'Location of the decimal, if any
If r&& > 0 Then
r&& = r&& - Len(l$) + 2
Else
r&& = r&& + 1
End If
l$ = Left$(l$, 1) + Mid$(l$, 3)
End If
Select Case r&&
Case 0 'what the heck? We solved it already?
'l$ = l$
Case Is < 0
For i = 1 To -r&&
l$ = "0" + l$
Next
l$ = "0." + l$
Case Else
For i = 1 To r&&
l$ = l$ + "0"
Next
End Select
N2S$ = sign$ + l$
End Function
Function DWD$ (exp$) 'Deal With Duplicates
'To deal with duplicate operators in our code.
'Such as -- becomes a +
'++ becomes a +
'+- becomes a -
'-+ becomes a -
t$ = exp$
Do
bad = 0
Do
l = InStr(t$, "++")
If l Then t$ = Left$(t$, l - 1) + "+" + Mid$(t$, l + 2): bad = -1
Loop Until l = 0
Do
l = InStr(t$, "+-")
If l Then t$ = Left$(t$, l - 1) + "-" + Mid$(t$, l + 2): bad = -1
Loop Until l = 0
Do
l = InStr(t$, "-+")
If l Then t$ = Left$(t$, l - 1) + "-" + Mid$(t$, l + 2): bad = -1
Loop Until l = 0
Do
l = InStr(t$, "--")
If l Then t$ = Left$(t$, l - 1) + "+" + Mid$(t$, l + 2): bad = -1
Loop Until l = 0
Loop Until Not bad
DWD$ = t$
End FunctionPresto-whammo, I autmoagically normalize my two strings so that they're the same length (minus signs which are processed independently as I showed up above.)
Since everything now lines up neatly, there's no real issue in processing them. We just grab large chunks of each string, take the value of them, and build our answer one chunk at a time until we're finished -- with the trick to efficiency being to grab as large of a chunk that we can process each time as possible.
RE: Faster addition in string math. - Pete - 08-19-2022
Actually, I already had all of that needed stuff in my old routine, but I'm attempting to shave a few lines off by using a sightly different method here, plus adding in the 18 digits at a time method for speed improvement.
Code: (Select All)
DIM AS _INTEGER64 a
WIDTH 130, 42
_SCREENMOVE 0, 0
DO
LINE INPUT "Number: "; a$
IF a$ = "" THEN EXIT DO ' Quit.
LINE INPUT "+ or -: "; op$
LINE INPUT "Number: "; b$
a1$ = a$: b1$ = b$
IF op$ = "-" THEN
IF LEFT$(b$, 1) = "-" THEN b$ = MID$(b$, 2) ELSE b$ = "-" + b$
END IF
s = 18
IF INSTR(a$, ".") <> 0 OR INSTR(b$, ".") <> 0 THEN
decimal% = -1
IF INSTR(a$, ".") <> 0 THEN
dec_a&& = LEN(MID$(a$, INSTR(a$, ".") + 1))
a$ = MID$(a$, 1, INSTR(a$, ".") - 1) + MID$(a$, INSTR(a$, ".") + 1)
END IF
IF INSTR(b$, ".") <> 0 THEN
dec_b&& = LEN(MID$(b$, INSTR(b$, ".") + 1))
b$ = MID$(b$, 1, INSTR(b$, ".") - 1) + MID$(b$, INSTR(b$, ".") + 1)
END IF
' Line up decimal places by inserting trailing zeros.
IF dec_b&& > dec_a&& THEN
j&& = dec_b&&
a$ = a$ + STRING$(dec_b&& - dec_a&&, "0")
ELSE
j&& = dec_a&&
b$ = b$ + STRING$(dec_a&& - dec_b&&, "0")
END IF
END IF
IF LEFT$(a$, 1) = "-" OR LEFT$(b$, 1) = "-" THEN
IF LEFT$(a$, 1) = "-" AND LEFT$(b$, 1) = "-" THEN
sign$ = "--": a$ = MID$(a$, 2): b$ = MID$(b$, 2)
ELSE
IF LEFT$(a$, 1) = "-" THEN a$ = MID$(a$, 2): sign_a$ = "-"
IF LEFT$(b$, 1) = "-" THEN b$ = MID$(b$, 2): sign_b$ = "-"
IF ABS(VAL(a1$)) < ABS(VAL(b1$)) THEN
IF LEN(sign_b$) THEN sign$ = "-": SWAP a$, b$
ELSE
IF LEN(sign_a$) THEN sign$ = "-": SWAP sign_a$, sign_b$
END IF
END IF
END IF
z$ = ""
DO
i&& = i&& + s
x1$ = MID$(a$, LEN(a$) - i&& + 1, s)
x2$ = MID$(b$, LEN(b$) - i&& + 1, s)
a = VAL(sign_a$ + x1$) + VAL(sign_b$ + x2$) + c
IF x1$ + x2$ = "" AND c = 0 THEN EXIT DO ' Prevents leading zeros.
c = 0
IF a > VAL(STRING$(s, "9")) THEN a = a - 10 ^ (s): c = 1
IF a < 0 THEN a = a + 10 ^ (s): c = -1
z$ = LTRIM$(STR$(a)) + z$
REM PRINT x1$;: LOCATE , 15: PRINT x2$;: LOCATE , 30: PRINT VAL(x1$) - VAL(x2$);: LOCATE , 45: PRINT c;: LOCATE , 60: PRINT a, z$: SLEEP
LOOP
IF decimal% THEN
z$ = MID$(z$, 1, LEN(z$) - j&&) + "." + MID$(z$, LEN(z$) - j&& + 1)
END IF
' Remove any leading zeros.
DO
IF LEFT$(z$, 1) = "0" THEN z$ = MID$(z$, 2) ELSE EXIT DO
LOOP
IF z$ = "" THEN z$ = "0"
z$ = LEFT$(sign$, 1) + z$
IF op$ = "+" THEN PRINT " " + LTRIM$(STR$(VAL(a1$) + VAL(b1$))), "QB64 VAL()." ELSE PRINT " " + LTRIM$(STR$(VAL(a1$) - VAL(b1$))), "QB64 VAL()."
PRINT " "; z$, "String Math."
PRINT
sign$ = "": sign_a$ = "": sign_b$ = "": i&& = 0: j&& = 0: decimal% = 0: c = 0
LOOP
SYSTEMFingers crossed, few to no bugs.
Thanks for the inspiration,
Pete
RE: Faster addition in string math. - SMcNeill - 08-19-2022
I haven't tested it extensively yet, but here's a quick string add and string subtract routine for math:
Code: (Select All)
Screen _NewImage(1280, 720, 32)
'a$ = "-10000000000000000000123.256"
'b$ = " 60000000000000000000000.111"
a$ = " 100000000000000000000000000"
b$ = "-000000000000000000000000001.1"
Print a$
Print b$
Print StringAdd(a$, b$)
Print StringSubtract(a$, b$)
Function StringAdd$ (tempa$, tempb$)
a$ = tempa$: b$ = tempb$ 'don't alter our original numbers
Dim As _Unsigned _Integer64 a, b, c 'to hold our values
'first fix the numbers to notmalize their lengths
FixNumbers a$, b$
'find the signs and strip them off
If Left$(a$, 1) = "-" Then sa$ = "-": a$ = Mid$(a$, 2)
If Left$(b$, 1) = "-" Then sb$ = "-": b$ = Mid$(b$, 2)
'find the decimal position
dp = InStr(a$, ".")
If dp > 0 Then 'remove the decimal place from our numbers. We can put it back later, in its proper position
righta$ = Mid$(a$, dp + 1)
rightb$ = Mid$(b$, dp + 1)
a$ = Left$(a$, dp - 1) + righta$
b$ = Left$(b$, dp - 1) + rightb$
End If
'our strings are now nothing but numbers with no signs and no decimals to deal with. Let's start adding!
'are we adding or really subtracting?
If sa$ <> sb$ Then 'we're subtracting the two values if the signs aren't the same.
Select Case a$
Case Is < b$: s$ = sb$: Swap a$, b$ 'our sign is going to be determiined by b$
Case Is = b$ 'if the two values are the same and are subtracting, our result is zero!
StringAdd$ = "0" 'How easy was that?
Exit Function
Case Else: s$ = sa$ 'our sign is determined by a$
End Select
Do
lb = Len(b$)
a = Val(Right$(a$, 18)): a$ = Left$(a$, Len(a$) - 18)
b = Val(Right$(b$, 18)): b$ = Left$(b$, Len(b$) - 18)
If borrow Then b = b + 1 'in case we had to borrow a digit for the last subtraction
If a < b Then
If lb < 18 Then a = a + 10 ^ lb Else a = a + 10 ^ 18
borrow = -1
Else
borrow = 0
End If
c = a - b
temp$ = _Trim$(Str$(c))
answer$ = String$(18 - Len(temp$), "0") + temp$ + answer$
Loop Until Len(a$) = 0
'remove leading 0's
Do Until Left$(answer$, 1) <> "0"
answer$ = Mid$(answer$, 2)
Loop
'remember to add in the decimal place before finished
dp = Len(righta$)
If dp > 0 Then
answer$ = Left$(answer$, Len(answer$) - dp) + "." + Right$(answer$, dp)
End If
StringAdd$ = s$ + answer$
Exit Function
End If
Do
a = Val(Right$(a$, 18)): a$ = Left$(a$, Len(a$) - 18)
b = Val(Right$(b$, 18)): b$ = Left$(b$, Len(b$) - 18)
c = a + b + carryover
temp$ = _Trim$(Str$(c))
If Len(temp$) > 18 Then 'see if we have an answer that is more than 18 digits
temp$ = Right$(temp$, 18) 'keep 18 digits
carryover = 1 'store one for carry over
Else
carryover = 0 'no carryover
End If
answer$ = String$(18 - Len(temp$), "0") + temp$ + answer$
Loop Until Len(a$) = 0
If carryover Then answer$ = "1" + answer$
'remember to add in the decimal place before finished
If dp > 0 Then
dp = Len(tempa$) - dp
answer$ = Left$(answer$, Len(answer$) - dp) + "." + Right$(answer$, dp)
End If
'remove leading 0's
Do Until Left$(answer$, 1) <> "0"
answer$ = Mid$(answer$, 2)
Loop
StringAdd$ = sa$ + answer$
End Function
Function StringSubtract$ (tempa$, tempb$)
a$ = tempa$: b$ = tempb$
FixNumbers a$, b$
If Left$(b$, 1) = "-" Then b$ = Mid$(b$, 2) Else b$ = "-" + b$
StringSubtract$ = StringAdd$(a$, b$)
End Function
Sub FixNumbers (a$, b$)
'first remove scientific notation and spaces from both
a$ = _Trim$(N2S$(a$)): b$ = _Trim$(N2S$(b$))
'then find the decimal position for both and normalize the expressions
d1 = InStr(a$, "."): d2 = InStr(b$, ".")
If d1 <> 0 Then 'break down the left and right side of the decimal point for ease of processing (this is a$)
lefta$ = Left$(a$, d1 - 1)
righta$ = Mid$(a$, d1)
Else
lefta$ = a$
End If
If d2 <> 0 Then 'break down the left and right side of the decimal point for ease of processing (this is b$)
leftb$ = Left$(b$, d2 - 1)
rightb$ = Mid$(b$, d2)
Else
leftb$ = b$
End If
'normalize the right side of our expressions
l1 = Len(righta$): l2 = Len(rightb$)
If l1 < l2 Then
addzero = l2 - l1
If l1 = 0 Then righta$ = ".": addzero = addzero - 1
righta$ = righta$ + String$(addzero, "0")
ElseIf l1 > l2 Then
addzero = l1 - l2
If l2 = 0 Then rightb$ = ".": addzero = addzero - 1
rightb$ = rightb$ + String$(addzero, "0")
End If
'strip off any plus/minus signs from the two numbers.
If Left$(lefta$, 1) = "-" Then signa$ = "-": lefta$ = Mid$(lefta$, 2)
If Left$(leftb$, 1) = "-" Then signb$ = "-": leftb$ = Mid$(leftb$, 2)
If Left$(lefta$, 1) = "+" Then signa$ = "": lefta$ = Mid$(lefta$, 2)
If Left$(leftb$, 1) = "+" Then signb$ = "": leftb$ = Mid$(leftb$, 2)
'normalize the left side of our expressions
l1 = Len(lefta$): l2 = Len(leftb$)
If l1 < l2 Then
addzero = l2 - l1
lefta$ = String$(addzero, "0") + lefta$
ElseIf l1 > l2 Then
addzero = l1 - l2
leftb$ = String$(addzero, "0") + leftb$
End If
'and then put it all together
a$ = signa$ + lefta$ + righta$
b$ = signb$ + leftb$ + rightb$
End Sub
Function N2S$ (exp$) 'scientific Notation to String
t$ = LTrim$(RTrim$(exp$))
If Left$(t$, 1) = "-" Or Left$(t$, 1) = "N" Then sign$ = "-": t$ = Mid$(t$, 2)
dp = InStr(t$, "D+"): dm = InStr(t$, "D-")
ep = InStr(t$, "E+"): em = InStr(t$, "E-")
check1 = Sgn(dp) + Sgn(dm) + Sgn(ep) + Sgn(em)
If check1 < 1 Or check1 > 1 Then N2S = exp$: Exit Function 'If no scientic notation is found, or if we find more than 1 type, it's not SN!
Select Case l 'l now tells us where the SN starts at.
Case Is < dp: l = dp
Case Is < dm: l = dm
Case Is < ep: l = ep
Case Is < em: l = em
End Select
l$ = Left$(t$, l - 1) 'The left of the SN
r$ = Mid$(t$, l + 1): r&& = Val(r$) 'The right of the SN, turned into a workable long
If InStr(l$, ".") Then 'Location of the decimal, if any
If r&& > 0 Then
r&& = r&& - Len(l$) + 2
Else
r&& = r&& + 1
End If
l$ = Left$(l$, 1) + Mid$(l$, 3)
End If
Select Case r&&
Case 0 'what the heck? We solved it already?
'l$ = l$
Case Is < 0
For i = 1 To -r&&
l$ = "0" + l$
Next
l$ = "0." + l$
Case Else
For i = 1 To r&&
l$ = l$ + "0"
Next
End Select
N2S$ = sign$ + l$
End Function
Function DWD$ (exp$) 'Deal With Duplicates
'To deal with duplicate operators in our code.
'Such as -- becomes a +
'++ becomes a +
'+- becomes a -
'-+ becomes a -
t$ = exp$
Do
bad = 0
Do
l = InStr(t$, "++")
If l Then t$ = Left$(t$, l - 1) + "+" + Mid$(t$, l + 2): bad = -1
Loop Until l = 0
Do
l = InStr(t$, "+-")
If l Then t$ = Left$(t$, l - 1) + "-" + Mid$(t$, l + 2): bad = -1
Loop Until l = 0
Do
l = InStr(t$, "-+")
If l Then t$ = Left$(t$, l - 1) + "-" + Mid$(t$, l + 2): bad = -1
Loop Until l = 0
Do
l = InStr(t$, "--")
If l Then t$ = Left$(t$, l - 1) + "+" + Mid$(t$, l + 2): bad = -1
Loop Until l = 0
Loop Until Not bad
DWD$ = t$
End FunctionAs I mentioned before, all my subtraction routine is, is just addition with an inverted sign!
Code: (Select All)
Function StringSubtract$ (tempa$, tempb$)
a$ = tempa$: b$ = tempb$
FixNumbers a$, b$
If Left$(b$, 1) = "-" Then b$ = Mid$(b$, 2) Else b$ = "-" + b$
StringSubtract$ = StringAdd$(a$, b$)
End Function18 digit chunks at a time, so it processes fairly quickly as far as string routines go with math.
Note: When dealing with multiplication, you can only handle 9 characters at a time. 100 * 100 = 10,000... You have to add the zeros to determine how large a result you can hold in one chunk.
I tried to comment the processes above fairly well, so hopefully they won't be too hard to understand and follow for anyone who's interested in playing around and learning about using strings to do math.
RE: Faster addition in string math. - Pete - 08-19-2022
@SMcNeill
Nice! Eerie how similar the code looks to my former add-subtract string math routine. I get a kick how some coders style and naming is familiar to me, while others is foreign, yet both, when coded properly achieve the same results.
In my prior routine I used similar +- combos in a select case to direct the program flow.
So I did some testing. Zero + Zero = "". So a single statement to make a null string = "0" could be added to address this situation.
Now the weird one. See screen shot. I tested some smaller decimals, and they worked, but this one failed...
RE: Faster addition in string math. - SMcNeill - 08-19-2022
The subtraction on the last one seems as if it's probably right, but the addition needs to be looked at a little closer. Something has glitched out there for certain!