ProdNumericStrings

FUNCTION: ProdNumericStrings(). Pass two integers in string format to this function and it will return the product of the two integers in string format.

Why use strings? This method enables very large numbers indeed to be manipulated. IBasic strings can be up to 254 characters in length. So products as large as 10²⁵⁴ - 1 are possible!

The numbers to be multiplied will be too large for IBasic to handle, even as unsigned integers, so they must be in string format. The product will have to be in string format for the same reason.

Declaring the function must be done like this:

declare ProdNumericStrings(mult1$: string, mult2$: string)

Here's the code:

sub prodStrings(mult1$, mult2$)
' Multiplies the numeric values of two integer
' strings and returns the product as a string.
def it1, it2, Lmult1, Lmult2: int
def i, L1, L2: int
def topMult, bottMult: int
def topSum, bottSum: int
def prodTopBott, carryProd: int
def sumTopBott, carrySum: int
def temp$, temp1$, temp2$, temp3$, temp4$, sum$: string
' intitialise product loop
Lmult1 = len(mult1$): Lmult2 = len(mult2$)
temp$ = ""
' main prod loop
for it1 = 1 to LMult1
    temp$ = string$(Lmult1 - it1, "0")
    bottMult = val(mid$(mult1$,it1,1))
    carryProd = 0
    for it2 = Lmult2 to 1 #-1
        topMult = val(mid$(mult2$,it2,1))
        prodTopBott = carryProd + topMult * bottMult
        if prodTopBott > 9
            carryProd = int(prodTopBott/10)
            prodTopBott = prodTopBott % 10
        else
            carryProd = 0
        endif
        temp$ = ltrim$(str$(prodTopBott)) + temp$
    next it2
    if carryProd > 0
        temp$ = ltrim$(str$(carryProd)) + temp$
    endif
    ' add intermediate products
    ' initialise add variables
    temp1$ = temp$: temp2$ = temp4$
    L1 = len(temp1$): L2 = len(temp2$)
    ' pad out shorter string with leading 0's
    if L1 <> L2
        if L1 > L2
            temp2$ = string$(L1 - L2, "0") + temp2$
        else
            temp1$ = string$(L2 - L1, "0") + temp1$
        endif
    endif
    ' set iterator to max string length
    if L2 > L1
        i = L2
    else
        i = L1
    endif
    ' intialise add loop
    temp3$ = ""
    carrySum = 0
    ' main add loop, adds two digits at a time
    do
        topSum = val(mid$(temp1$, i, 1))
        bottSum = val(mid$(temp2$, i, 1))
        sumTopBott = topSum + bottSum + carrySum
        if sumTopBott > 9
            carrySum = 1
            sumTopBott = sumTopBott % 10
        else
            carrySum = 0
        endif
        sum$ = ltrim$(str$(sumTopBott))
        temp3$ = sum$ + temp3$
        i = i - 1
    until i < 1
    if carrySum = 1
        temp3$ = "1" + temp3$
    endif
    temp4$ = temp3$
next it1
return temp4$

STRATEGY

The approach here is simply to imitate the method many children are taught multiplication at school. Here's an example. Let's say we want to multiply 2713 by 654. You lay out the problem as shown inset.

2713
x 654

The rule is to multiply the top by the bottom, one digit at a time, from the left of the bottom row. Before each digit is dealt with, zeroes must be inserted under the line to the right. The number of zeroes have to be equal to one less than the digits of the of the bottom row. So the first task is to pad with two digits (one less than the number of digits in the bottom row, 654).

2713
x 654
00

Now take the six from the bottom row and multiply it by the top row. Put the result to the left of the padding zeroes. Children do this one digit at a time, and that method is adopted in the code below. This produces the additions shown inset.

2713
x 654
1627800

Repeat the process for the next digit in the bottom row, a 5. This time, only pad with one zero, one less than the number of digits remaining. Place the results under the last line, as sh

2713
x 654
1627800
135650

Deal with the final digit, the 4 from the bottom row. Since there's only one digit involved now, no padding is necessary. The result looks like the inset figure.

2713
x 654
1627800
135650
10852

The three numbers below the line are the positional products of the each of the digits 654 from the bottom row, taken in order. All we have to do now is add them, and we have the solution to our original multiplication problem. The final result is shown inset. As you can see, it works out quite correctly at 1774302. Note that the code actually sub-totalises these intermediate multiplications as it goes along.

2713
x 654
1627800
135650
10852
1774302

This method will work for any size numbers, no matter how big. It's almost exactly the process used in the code here. It's complicated slightly by the fact that everything has to be done in strings to get round IBasic's inability to handle very large numbers.

If you want to be able to do it without strings, you could use UBasic or Liberty Basic, but this series has been built around IBasic, so I'll stay with it.

I'm going to begin with a description of what all the variables do in the code.

Variable	Comments

it1	Iterates over the digits of argument mult1$, the "bottom" row in the example given above.
it2	Iterates over the digits of argument mult2$, the "top" row in the example given above.
Lmult1	The length of argument mult1$ - in other words, the number of digits it contains.
Lmult2	The length of argument mult2$ - in other words, the number of digits it contains.
topMult	The current digit from the top row which is to be multiplied by a digit from the bottom row.
bottMult	The current digit from the bottom row which is to be multiply a digit from the top row.
topSum	Used in the "add" phase. The current top row digit.
bottSum	Used in the "add" phase. The current bottom row digit.
prodTopBott	The product of topMult and bottMult plus any carry (see next variable).
carryProd	Any carry from the last product of the top and bottom row digits.
sumTopBott	The sum of the values stored in topSum and bottSum.
carrySum	Any carry from adding topSum and bottSum.
temp$	Initally holds the number of zeroes required for padding, as described in note 2 of the "Overview and Strategy" notes above. It will eventually hold a complete line of multiplication.
temp1$	A copy of temp$ used in the "add" phase.
temp2$	A temporary copy of what will become the final sum after all additions have been carried out.
temp3$	An intermediate sum incorporating any carries.
temp4$	The final sum, to be returned to the calling routine.
sum$	Holds the intermediate sums in the digit-by-digit additions.

To make the explanation simpler, I've numbered the lines, excluding comment-only lines. The declarations have already been dealt with, so they're not included. Here are the numbered code lines of interest.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

Lmult1 = len(mult1$): Lmult2 = len(mult2$)
temp$ = ""
for it1 = 1 to LMult1
    temp$ = string$(Lmult1 - it1, "0")
    bottMult = val(mid$(mult1$,it1,1))
    carryProd = 0
    for it2 = Lmult2 to 1 #-1
        topMult = val(mid$(mult2$,it2,1))
        prodTopBott = carryProd + topMult * bottMult
        if prodTopBott > 9
            carryProd = int(prodTopBott/10)
            prodTopBott = prodTopBott % 10
        else
            carryProd = 0
        endif
        temp$ = ltrim$(str$(prodTopBott)) + temp$
    next it2
    if carryProd > 0
        temp$ = ltrim$(str$(carryProd)) + temp$
    endif
    temp1$ = temp$: temp2$ = temp4$
    L1 = len(temp1$): L2 = len(temp2$)
    if L1 <> L2
        if L1 > L2
            temp2$ = string$(L1 - L2, "0") + temp2$
        else
            temp1$ = string$(L2 - L1, "0") + temp1$
        endif
    endif
    if L2 > L1
        i = L2
    else
        i = L1
    endif
    temp3$ = ""
    carrySum = 0
    do
        topSum = val(mid$(temp1$, i, 1))
        bottSum = val(mid$(temp2$, i, 1))
        sumTopBott = topSum + bottSum + carrySum
        if sumTopBott > 9
            carrySum = 1
            sumTopBott = sumTopBott % 10
        else
            carrySum = 0
        endif
        sum$ = ltrim$(str$(sumTopBott))
        temp3$ = sum$ + temp3$
        i = i - 1
    until i < 1
    if carrySum = 1
        temp3$ = "1" + temp3$
    endif
    temp4$ = temp3$
next it1
return temp4$

Now for a line-by-line exegesis of the code. In the description below, keep in mind the simple explanation laid out in "Overview and Strategy" above - it will make things easier to understand.

Lmult1 = len(mult1$): Lmult2 = len(mult2$). Finds and stores the lengths, and thus the number of digits, in each of the function's arguments and stores them in variables Lmult1 and Lmult2 respectively. These values are crucial in knowing how many digits to multiply together.

temp$ = "". Variable temp$ holds the correct number of zeroes to pad intermediate multiplications out with, as explained in point two of "Overview and Strategy" above. So we begin by initialising it to an empty string.

for it1 = 1 to LMult1. The main FOR-NEXT loop is opened. The iterator is variable it1 and its range is 1 to the number of characters in the bottom row, already saved in LMult1.

temp$ = string$(Lmult1 - it1, "0"). Line 4 works out how zeroes are needed for padding, generates them, and saves them into variable temp$. Let's illustrate this from the example already given, 2713 x 654. As explained in point 2 of "Overview and Strategy" above, this needs to be two zeroes. Take a look at how this line does it.

mult1$ is "654" and so Lmult1 is 3. The expression brackets can therefore be simplifed to (3 - it1, "0"). As this is the first pass of the main FOR-NEXT loop, iterator it1 is at value 1, giving a further simplication of the bracketed expression: (3 - 1, "0"), yielding finally (2, "0").

This expression is passed to the inbuilt function string$() which will return a string of the specified characters, in this case "0", numbering, as instructed, 2. So the net result of line 4 is that temp$ contains "00". On subsequent iterations of it1 it will contain "0" and "".

bottMult = val(mid$(mult1$,it1,1)). Were ready to begin some multiplication. First, we need to isolate the multiplying digit. As shown in the example, this should be the "6" in the bottom row during the first pass of the FOR-NEXT loop.

Using the inbuilt function mid$, and substituting values for mult1$ and it1, we have mid$("654", 1,1). This evaluates to "6", which in turn is passed to the inbuilt function val, making it val("6"). The output, saved in variable bottMultI, is simply 6. Note that the function val() just removes the quote marks and returns an integer.

carryProd = 0. In the next few lines of code some multiplication will take place, and we need to look out for overflows, commonly known as "carries." If these occur, they will be stored in variable carryPod. In preparation for this, variable carryPod is initialised to zero.

for it2 = Lmult2 to 1 #-1. An inner FOR-NEXT loop is opened to handle the digit-by-digit multiplication process. This one is dedicated to the multiplication phase only. The iterator is variable it2. The range is the length of mult2$, which is stored in variable Lmult2, that is, the number of characters in the top row. This is worked backwards, from the value in Lmult2 to 1. The reason is that this is the way I was taught to do multiplication, but I know that a lot of kids also learn it the other way around. Both give the same result in the end! Line 7 will set up multiplication of the digits in the top row by the value set up in line 5 from the bottom row.

topMult = val(mid$(mult2$,it2,1)). Having identified a multiplying digit in line 5 it's time to extract a single digit from the top row to multiply by, just as a child would do when tackling this problem with pencil and paper. Using the same kind of format as line 5, and already expounded, we can show that line 8 will extract the 3 from the 2713 example given. This is, of course, on the first pass of the it2 FOR-NEXT loop. It will pull out the 1 on the next pass, then the 7, and so on. This value is stored at every iteration in variable topMult.

prodTopBott = carryProd + topMult * bottMult. We have now acquired a value for both bottMult and topMult. Line 9 multiplies them together and saves the product in variable prodTopBott. There won't be a carry to add in on the first pass, but there may be on subsequent passes, and this will be taken care of by adding carryProd, which just means "add in any carry from the previous product."

if prodTopBott > 9. We were thinking about what happens when a carry is generated in line 9. Line 10 sets about detecting and dealing with any carries. It looks at the product obtained in line 9 and checks to see whether it exceeded 9. Remember, this is the product of two single digits, so it doesn't necessarily generate a carry. We can look at this line as a question: "Is the value now stored in variable prodTopBott greater than 9?"

carryProd = int(prodTopBott/10). Line 11 is only executed if the answer to the question in line 10 was "yes." It means a carry was generated, and must be saved.

Let's take an example. Assume topMult was 9 and was bottMult was7, with no existing value in carryProd. Then their product will be saved in prodTopBott as 9 x 7 = 63. This should generate a carry of 6; let's see if it does.

The inner part of the brackets is (prodTopBott/10), which we can write as (63/10) in this case, simplifying to (6·3). Now to look outside the brackets, where we have int(6·3). The inbuilt function int simply removes the decimal part, yielding 6, the correct carry value, and this is stored in carryProd ready to be used on the next pass.

prodTopBott = prodTopBott % 10. We still have one more operation to do before passing on. prodTopBott now hold 63, although the carry 6 has been saved. We have to reduce the contents of prodTopBott 3 now to make it correct. Once again, integer arithmetic is used. You will remember that the % sign means "make a division, retain any remainder, and discard the rest." So 63 % 10 = 3, and that is what is finally saved in prodTopBott.

else. This line indicates that, if the answer to the question in line 10 was "no," lines 11 and 12 can be skipped and an alternative action applied instead.

carryProd = 0. This is the alternative action. No carry was generated, so the value stored in carryProd must be set to zero.

endif. Housekeeping - closes the IF-ENDIF clause opened in line 10.

temp$ = ltrim$(str$(prodTopBott)) + temp$. We're building up the product of the top row and the 6 of the bottom row a digit at a time. This has to be saved before the next iteration of it2, which will deal with the next digit of the top row. Variable temp$ has been set up for this purpose. It's empty on the first pass, but will have content on subsequent passes.

Working from the inside bracket outwards, we are dealing with (prodTopBott), the latest product. Inbuilt function str$ turns this into a string format. Like all Basic's IBasic inserts a leading space when it does this for formatting purposes. In our application, the space will cause errors, and has to be removed. Another inbuilt function, ltrim$, does this for us.

We now have the product entirely in string format. After concatenating with (tacking on to) anything already saved in temp$, the result is saved back into temp$, over-writing anything that was already in there.

next it2. Housekeeping - completes FOR-NEXT clause opened in line 7.

if carryProd > 0. The multiplication of all the top row digits by one from the bottom row is now complete. However, a carry may have been generated from the last single-digit multiplication, and must be dealt with. Line 18 is asking the question "Was there a carry from the last multiplication?"

temp$ = ltrim$(str$(carryProd)) + temp$. Line 19 is only executed if the answer to the question in line 18 is "yes." It's exactly the same format as line 16, and works in the same way. After its execution, The carry is concatenated onto the front of temp$ as required.

endif. Housekeeping - closes IF-ENDIF clause opened in line 18.

We have now completed the first line of multiplication. Subsequent multiplications will produce further results. All these results have to be added together to produce the final result. A pen-and-paper method would do all the additions together at the end. We don't have that luxury, because we don't know how many there will be so don't know how much memory to allocate for them. The simple solution is to add them together as we go along, rather than all at once at the end. The rest of the code is devoted to this activity.

It's more complicated than the pen-and-paper method because we have to do it all with strings, but the general algorithm is exactly the same as a child would use - deal with one pair of digits at a time.

temp1$ = temp$: temp2$ = temp4$. temp$ holds the latest line to be added; it's copied into temp1$ to be operated on.
temp4$ holds the running total of whole-line additions so far; when the program is finished, its final contents will be returned to the calling routine. To work on it now, it's copied into temp2$.

Lines 22 to 34 are used to format the contents of temp1$ and temp2$ for numerical addition. A real problem could occur when these two strings are of different lengths. Consider the case of trying to perform a numerical addition on the strings "2327" and "81312." All would be ok for the for first four digits, but eventually the code would try to add that 8 to something. There's nothing there, and even a space wouldn't do the trick. So it's important to pad out a shorter string with leading zeroes until it's the same length as the longer string.

L1 = len(temp1$): L2 = len(temp2$). Obtains and saves the lengths (and thus, the number of characters) in both temp1$ and temp2$ and saves them in L1 and L2 respectively.

if L1 <> L2. If the two lengths are different, we need to pad one of the strings with leading zeroes to make them the same length as explained above. This line is checking for that by effectively asking the question "Isthe value stored in L1 different to that stored in L2?"

if L1 > L2. This line is only executed if the answer to the question in line 23 was "yes." In these circumstances, the code needs to know which is the longer, so it goes on to ask a further question: "Is the value stored in L1 greater than that stored in L2?"

temp2$ = string$(L1 - L2, "0") + temp2$. This line is only executed if the answer to the question in line 24 is "yes." It means that temp2$ is shorter than temp1$, and needs to be padded with the correct number of leading zeroes to bring it up to temp1$'s length. Let's see how it does it.

In the example given above, temp1$ = "81312" and temp2$ = "2327". So L1 = 5 and L2 =4. The inbuilt function now looks like this: string$(1, "0"). It will return the simple string "0". The code concatenates this onto the front of temp2$ to make it "02327" and then saves it back into temp2$, over-writing what was already in there.

else. If the answer to the question in line 24, was "no," an alternative action is required, signified by this line.

temp1$ = string$(L2 - L1, "0") + temp1$. Line 27 is the alternative action to line 25, necessary if L2 turned out to be longer than L1. It's identical in action to line 25 except that L2 and L1 are reversed, and the padding is put onto temp1$.

endif. Housekeeping - close IF-ENDIF clause opened in line 24.

endif. Housekeeping - close IF-ENDIF clause opened in line 23.

We now have to initialise iterator i, which will be used in a DO loop to work over the individual digit additions of temp1$ to temp2$. Lines 30 to 34 are used to find out what value to initialise i to. It must be the same length as the longest of the two strings. A problem is that the code still doesn't know the answer to that - L1 and L2 values are unchanged, and may or may not be equal. Lines 30 to 34 sort this problem out.

if L2 > L1. Line 30 asks the question "Is L2 greater than L1?" Note that it doesn't care if they're the same.

i = L2. Line 31 gets executed if the answer to the question in line 30 is "yes." In such a case, iterator i has to be set equal to L2.

else. Indicates that, if the answer to the question in line 30 was "no" an alternative action is necessary.

i = L1. We now know that L1 is equal to or greater than L2. In these circumstances, iterator i has to be set equal to L1.

endif. Housekeeping - closes IF-ENDIF clause opened in line 30.

temp3$ = "". The addition will be built up in temp3$ until it's complete. Line 35 initialises temp3$ to be empty.

carrySum = 0. Any carries generated will be saved into variable carrySum. LIne 36 initialises carrySum to zero.

We are now ready to perform the digit-by-digit addition process. This is very similar to the digit-by-digit multiplication covered in lines 9 to 17. If you understood that, you'll find this even easier, because carries can never be more than 1, whereas in multiplication they can have any value up to 8.

do. The digit-by-digit addition will be done inside a DO loop. Line 37 opens the loop.

topSum = val(mid$(temp1$, i, 1)). Isolates the i'th digit of the top row to be added using the same technique as already described for line 8. After execution of line 38, variable topSum will hold the single digit required.

bottSum = val(mid$(temp2$, i, 1)). The i'th digit of the bottom row is extracted in exactly the same way as line 38 and then saved in variable bottSum.

sumTopBott = topSum + bottSum + carrySum. The values in topSum and bottSum are added together along with anything in carrySum (from previous additions) and saved in variable sumTopBott.

if sumTopBott > 9. We have to check whether the addition just carried out in line 40 generated a carry, which will occur if the sum was greater than 9. So line 41 is asking the question "Was a carry generated?"

carrySum = 1. If the answer to the question in line 42 is "yes," the fact is recorded by setting the value in carrySum to 1.

sumTopBott = sumTopBott % 10. Line 43 mimics the action taken in line 12 during multiplication, saving only the LSD of the last addition (the MSD was already saved in carrySum by line 42). Refer there if you don't understand how this line works.

else. Indicates that there is an alternative action if the answer to the question in line 41 is "no."

carrySum = 0. If the answer was "no," there is no carry, and carrySum is set to zero accordingly.

endif. Housekeeping - closes IF-ENDIF clause opened in line 41.

sum$ = ltrim$(str$(sumTopBott)). We now have a single-digit addition saved in sumTopBott. This must be converted to string format ready to be used in building up the output string. Line 47 mimics line 16 in how it does that, saving the result in variable sum$. If you don't understand how it works, refer back to line 16's commentary.

temp3$ = sum$ + temp3$. sum$ is concatenated onto the front of whatever is already in temp3$ and the result saved back into temp3$, over-writing what was already in there. Remember, temp3$ is building up the complete row addition.

i = i - 1. It's time to move onto the next pair of digits to be added. We are working from left to right, just as you would if doing the addition by hand, so i, the pointer, is decremented by 1.

until i < 1. The code has now reached the end of the DO loop opened in line 37 and has to decide whether to execute the DO loop again or move on. This is easy, because it's controlled by the value of iterator i. It was just decremented by line 47. If that took it to less than 1, all the digits have been dealt with and the loop can quit. If not, go around again.

if carrySum = 1. Having quit the loop, there is still the possibility that the last digit's addition caused a carry. Line 51 is checking that, effectively asking the question "Is there still a carry in variable carrySum?"

temp3$ = "1" + temp3$. If the answer to the question in line 51 is "yes," the carry is concatenated onto the front of temp3$.

endif. Housekeeping - closes the IF-ENDIF clause opened in line 51.

temp4$ = temp3$. temp3$ now holds the accumulated additions of the row multiplications processed so far. This is copied into temp4$ ready to return to the calling routine. Note that this works in the overall picture because temp4$ is copied at each iteration of the main FOR-NEXT loop into temp2$ by line 21, and temp2$ accumulates the output in the DO loop of line 37.

next it1. Housekeeping - closes FOR-NEXT clause opened in line 3.

return temp4$. The multiplication is complete. All that's required now is to return the result to the calling routine, and line 54 takes care of that.

I'm sorry this is such a long and involved function - and writing these notes was surely a labour of love - but I hope you found it useful not only in understanding how the function works, but in appreciating how Basic languages can be manipulated to do almost anything.