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^{254} - 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$ |
1. |
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 |
2. |
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 |
3. |
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 |
4. |
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 |
5. |
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 |
6. |
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. |
1 |
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. |
2 |
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. |
3 |
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. |
4 |
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 "". |
5 |
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. |
6 |
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. |
7 |
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. |
8 |
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. |
9 |
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." |
10 |
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?" |
11 |
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. |
12 |
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. |
13 |
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. |
14 |
carryProd = 0. This is the alternative action. No carry was generated, so the value stored in carryProd must be set to zero. |
15 |
endif. Housekeeping - closes the IF-ENDIF clause opened in line 10. |
16 |
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. |
17 |
next it2. Housekeeping - completes FOR-NEXT clause opened in line 7. |
18 |
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?" |
19 |
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. |
20 |
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. |
21 |
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. |
22 |
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. |
23 |
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?" |
24 |
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?" |
25 |
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. |
26 |
else. If the answer to the question in line 24, was "no," an alternative action is required, signified by this line. |
27 |
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$. |
28 |
endif. Housekeeping - close IF-ENDIF clause opened in line 24. |
29 |
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. |
30 |
if L2 > L1. Line 30 asks the question "Is L2 greater than L1?" Note that it doesn't care if they're the same. |
31 |
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. |
32 |
else. Indicates that, if the answer to the question in line 30 was "no" an alternative action is necessary. |
33 |
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. |
34 |
endif. Housekeeping - closes IF-ENDIF clause opened in line 30. |
35 |
temp3$ = "". The addition will be built up in temp3$ until it's complete. Line 35 initialises temp3$ to be empty. |
36 |
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. |
37 |
do. The digit-by-digit addition will be done inside a DO loop. Line 37 opens the loop. |
38 |
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. |
39 |
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. |
40 |
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. |
41 |
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?" |
42 |
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. |
43 |
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. |
44 |
else. Indicates that there is an alternative action if the answer to the question in line 41 is "no." |
45 |
carrySum = 0. If the answer was "no," there is no carry, and carrySum is set to zero accordingly. |
46 |
endif. Housekeeping - closes IF-ENDIF clause opened in line 41. |
47 |
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. |
48 |
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. |
49 |
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. |
50 |
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. |
51 |
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?" |
52 |
temp3$ = "1" + temp3$. If the answer to the question in line 51 is "yes," the carry is concatenated onto the front of temp3$. |
53 |
endif. Housekeeping - closes the IF-ENDIF clause opened in line 51. |
54 |
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. |
55 |
next
it1.
Housekeeping - closes FOR-NEXT clause opened in line 3. |
56 |
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. |
MAIN MENU
HOW DOES IT WORK?
Site design/maintenance: Dave Ellis E-mail me!
Last Updated: February 5th, 2010.