Decimal Arithmetic

Decimal Addition

Much of the structure and many of the concepts introduced here will be reused in the other modules. The basic idea is to place tables of digit sum elements in the environment. The structure of the tables is that of three dimensional arrays, using concatenation of indexes for the first two dimensions and indirect reference through argument variable names for the third. For example, if we need the sum of the digits 9 and 2, with carry from a previous sum, we would extract the elements r[CF][9][2] and c[CF][9][2] to get the digit and carry flag. (r is for "result", CF is for "carry flag", and the two digits point to the specific values of result and carry that result from the sum of the digits with carry. The specific table entries containing those indexes and results are


    r19=0 1 2 3 4 5 6 7 8 9
and

    c19=1 1 1 1 1 1 1 1 1 1
The same digits without carry-in have the entries

    r09=9 0 1 2 3 4 5 6 7 8
and

    c09=0 1 1 1 1 1 1 1 1 1

The complete setup code is shown in its place in the wrapper batch file below.

Since, in the addition of two numbers, the carry value can only be zero or one, only four sets of ten entry each environment variables are needed, but they take forty entries, for a total of 920 bytes of environment space. That's a lot, by conventional standards, and is not to be expected to be available in a normal environment. For this reason, the program's wrapper must create it's own, extra large, environment by spawning itself in a secondary command processor. This leads to some complications, but also removes some others:


 @echo off
 if %1 = goto %1 %2
 set x=%1
 set y=%2
 set IP=init
 set result=
 command /e:32768 /c%0 goto init
 if exist getrslt.bat call getrslt
 if exist getrslt.bat del getrslt.bat
 if exist }add{.bat del }add{.bat
 goto end

 :init
 set sum=
 set CF=0

 set r00=0 1 2 3 4 5 6 7 8 9 
 set r01=1 2 3 4 5 6 7 8 9 0 
 set r02=2 3 4 5 6 7 8 9 0 1 
 set r03=3 4 5 6 7 8 9 0 1 2 
 set r04=4 5 6 7 8 9 0 1 2 3 
 set r05=5 6 7 8 9 0 1 2 3 4 
 set r06=6 7 8 9 0 1 2 3 4 5 
 set r07=7 8 9 0 1 2 3 4 5 6 
 set r08=8 9 0 1 2 3 4 5 6 7 
 set r09=9 0 1 2 3 4 5 6 7 8 

 set c00=0 0 0 0 0 0 0 0 0 0
 set c01=0 0 0 0 0 0 0 0 0 1
 set c02=0 0 0 0 0 0 0 0 1 1
 set c03=0 0 0 0 0 0 0 1 1 1
 set c04=0 0 0 0 0 0 1 1 1 1
 set c05=0 0 0 0 0 1 1 1 1 1
 set c06=0 0 0 0 1 1 1 1 1 1
 set c07=0 0 0 1 1 1 1 1 1 1
 set c08=0 0 1 1 1 1 1 1 1 1
 set c09=0 1 1 1 1 1 1 1 1 1

 set r10=1 2 3 4 5 6 7 8 9 0 
 set r11=2 3 4 5 6 7 8 9 0 1 
 set r12=3 4 5 6 7 8 9 0 1 2 
 set r13=4 5 6 7 8 9 0 1 2 3 
 set r14=5 6 7 8 9 0 1 2 3 4 
 set r15=6 7 8 9 0 1 2 3 4 5 
 set r16=7 8 9 0 1 2 3 4 5 6 
 set r17=8 9 0 1 2 3 4 5 6 7 
 set r18=9 0 1 2 3 4 5 6 7 8 
 set r19=0 1 2 3 4 5 6 7 8 9 

 set c10=0 0 0 0 0 0 0 0 0 1
 set c11=0 0 0 0 0 0 0 0 1 1
 set c12=0 0 0 0 0 0 0 1 1 1
 set c13=0 0 0 0 0 0 1 1 1 1
 set c14=0 0 0 0 0 1 1 1 1 1
 set c15=0 0 0 0 1 1 1 1 1 1
 set c16=0 0 0 1 1 1 1 1 1 1
 set c17=0 0 1 1 1 1 1 1 1 1
 set c18=0 1 1 1 1 1 1 1 1 1
 set c19=1 1 1 1 1 1 1 1 1 1

 set IP=start
 ::     // the string processor is GETNSTR.BAT
 call getnstr
 set IP=pass1
 ::     // the decimal adder is DADD.BAT
 dadd
 
 :end

The actual adder is a separate batch file so that the above used-once code can't weigh it down. The string processor is also part of the initialization code and resides in yet another file, also for speed reasons.

The big headache is that when the process terminates, the sum is lost. This is dealt with by having the process write (from within the secondary command processor) a batch file that restores the value later, which is what the CALL getrslt command (above) does.

Given that the sum of the two digits and carry in work at the moment exist as table entries that can be referenced as environment variables, we still face the problem of extracting the desired character from the string that is the table entry. The obvious way is to feed the string back into the program as an argument string and extract the desired argument value. It's not that simple, though that is the approach. Both the environment variable name and the argument name contain variables, and while we can resolve the environment variable name's variable parts within the program, we can't construct a variable argument name within the program. We can, however, have the program write and call another batch file that adds an additional level of '%' parsing, and can therefore resolve the name and write the result into the environment. The desired program looks like this (this example is a leftover from a test; IPA is set to pass}1{ before the subprogram is launched)


 goto %IPA%
 :pass}1{
 set IPA=pass}2{
 }add{ %r09%
 :pass}2{
 shift
 set sum=%2%sum%
 set IPA=pass}3{
 }add{ %c09%
 :pass}3{
 shift
 set CF=%2

This bit of obscurity results in this sequence of commands (// marks added comments)


 goto pass}1{           //  goto %IPA%
 // :pass}1{
 set IPA=pass}2{

 }add{ 9 0 1 2 3 4 5 6 7 8   // }add{ %r09% - this reinvokes the sub,
         // with the environment string as its argument list.
 goto pass}2{

 shift          // this causes %0 to line up with the sum of 9 + 0
        // so that %n is the sum of 9 and n
 set sum=1      // note that %2 is 1, the sum part of the result and
        // that since this is the first pass, SUM is null, so we just
        // concatenate the digit with a null when set sum=%2%sum% is
        // executed.
 set sum=1
 set IPA=pass}3{

 }add{ 0 1 1 1 1 1 1 1 1 1      // same as above, except for the carry

 goto pass}3{

 shift

 set CF=1       // note that the carry is not concatenated with
                // anything - it is generated afresh each pass.

Conceptually, this example does not differ from the way grade school children are taught to add two single digit numbers. The handling of carries, however is dramatically different.

In grade school, we are taught to add lists of multi digit numbers by summing each column and carrying everything but the final digit by writing it above the list as a new entry - machines don't work that way. Machines add lists of numbers by starting with a sum of zero and adding each successive list entry to the running total - digit-to- digit carries can be only zero or one. The child is taught only one addition table, with carries handled as extra list items, but there would be no other use for the ability to add three numbers in the machine case, so here, it makes sense to use two addition tables: one with and one without the carry built into the table. It takes more memory to do it that way, but the program can be considerably less complex (and admittedly, this is already a complex enough task for a batch language program).

The above code is, in fact, the heart of the adder. The rest of the program is concerned with preparing the strings of digits and building the above code anew for each pair of digits (the digits are hard code in the commands - they cannot be variables at the level where they are actually used). The core subprogram is a bit tricky to build, because of the task of keeping track of all the '%' characters needed, and also because of the need to pay attention to such details as where there must not be any spaces. I dealt with the latter concern by omitting them from in front of all of the redirection symbols in


 :build          // build }add{.bat
 echo goto %%IPA%% > }add{.bat
 echo :pass}1{>> }add{.bat
 echo set IPA=pass}2{>> }add{.bat
 ::             // split array[CF][dx] into fields
 echo }add{ %%r%CF%%dx%%%>> }add{.bat

 echo :pass}2{>> }add{.bat
 ::             // shift array[CF][dx] to align %0 with array[dx][0]
 echo shift>> }add{.bat
 ::             // sum is array[CF][dx][ex]; place digit in string
 echo set sum=%%%ex%%%sum%%>> }add{.bat
 echo set IPA=pass}3{>> }add{.bat
 ::             // split carry[CF][dx] into fields
 echo }add{ %%c%CF%%dx%%%>> }add{.bat
 echo :pass}3{>> }add{.bat
 ::             // shift to align %0 with carry[CF][dx][ex]
 echo shift>> }add{.bat
 ::             // carry is carry[CF][dx][ex]
 echo set CF=%%%ex%%>> }add{.bat
 :end
Note: the // comments appear in the real program, as shown here.

Because the way COMMAND.COM processes '%' escape characters is not well understood my many batch programmers, I will devote a bit of space to illustrating the handling of things like %%c%CF%%dx%%% in some detail. The particular code above generates this sequence of commands (from the same test run as above the above), with the file commands added as comments


 echo goto %IPA% > }add{.bat  // echo goto %%IPA%% > }add{.bat

 echo :pass}1{>> }add{.bat    // echo :pass}1{>> }add{.bat

 echo set IPA=pass}2{>> }add{.bat // echo set IPA=pass}2{>> }add{.bat

 echo }add{ %r09%>> }add{.bat // echo }add{ %%r%CF%%dx%%%>> }add{.bat

 echo :pass}2{>> }add{.bat    // echo :pass}2{>> }add{.bat

 echo shift>> }add{.bat       // echo shift>> }add{.bat

 echo set sum=%2%sum%>> }add{.bat 
   //(line above) echo set sum=%%%ex%%%sum%%>> }add{.bat

 echo set IPA=pass}3{>> }add{.bat // echo set IPA=pass}3{>> }add{.bat

 echo }add{ %c09%>> }add{.bat // echo }add{ %%c%CF%%dx%%%>> }add{.bat

 echo :pass}3{>> }add{.bat    // echo :pass}3{>> }add{.bat

 echo shift>> }add{.bat       // echo shift>> }add{.bat

 echo set CF=%2>> }add{.bat   // echo set CF=%%%ex%%>> }add{.bat
Note that the comments are the code that actually generates the commands on the left, after the variable references are resolved. The actual commands make some sense, the code from the program makes rather less. The idea is that for every '%' we want to go into the target file, we have to use "%%" in the program, and for every variable we want to have resolved into a value before it is written to the target file, we have to use just '%'. An environment variable followed by a '%' literal comes out looking like %dx%%%, where two environment variables to be resolved immediately come together we need %CF%%dx%, and when we need a constant preceded by a '%' literal, we use %%r - that all comes together as %%r%CF%%dx%%%.

Now that we have an engine that can add two digits, with or without carry, and prefix the result to a sum string under construction, we can address the main part of the program, which prepares the given number strings for processing and controls the execution of the actual addition engine. There are several major problems, most notably the need to separate the digits of the given strings and to control looping so that all the digits get processed, none get ignored, and leading zeros get prefixed to the shorter of the two strings.

The given strings are converted into space delimited strings in reverse order, so that when working from the front of the string, each digit is encountered in its correct order and unused digit positions come at the end. This is done using a variation on the theme of stripping characters from a string with the undocumented FOR %a in (/string) do syntax. That syntax is another topic, dealt with elsewhere. Here, the code (GETNSTR.BAT) is


 goto %IP%      // set to "start" by calling program
 :char          // handles character part of string
 set c=%1 %c%
 set IP=str
 goto end

 :str           // handles remainder of string
 set s=%1
 set IP=char
 goto end

 :start         // convert number strings into space delimited records
 set IP=char

 set bx=%y%!
 set ax=%x%!
 set s=
 set c=

 :loopa
 for %%a in (/%ax%) do call %0 %%a
 set ax=%s%
 if not %s% == ! goto loopa
 set ax=%c%
 set s=
 set c=

 :loopb
 for %%a in (/%bx%) do call %0 %%a
 set bx=%s%
 if not %s% == ! goto loopb
 set bx=%c%

 set c=
 set s=
 set x=
 set y=

 :end
This code is separated from the other parts of the program because it runs only once, but is heavily recursive and would be rather slow if there were more code in the file.

The number strings are passed in x and y, and are processed into ax and bx, with c used as the temporary variable for building the space delimited string (note the space in the line set c=%1 %c%, and s is used to hold the remainder of the string until it can be placed back into the string being stripped for the next pass. The bang (!) character is used to mark the end of the string - when the string in work is reduced to just that character, the DO WHILE loop terminates.

The remaining major part of the adder program is the process flow control code


 goto %IP%
 :pass1
 set IP=pass2
 ::             // split ax record into strings
 %0 %ax%

 :pass2
 set dx=%1
 set ax=%2 %3 %4 %5 %6 %7 %8 %9
 set IP=pass3
 ::             // split bx record into fields
 %0 %bx%

 :pass3
 set IP=pass4
 %0 %bx%

 :pass4
 set ex=%1
 set bx=%2 %3 %4 %5 %6 %7 %8 %9

 set IP=build
 call %0        // calls build to make }add{.bat
 set IPA=pass}1{
 call }add{

 set IP=pass5
 %0 %ax% !
 :pass5
 set x=%1
 set IP=pass6
 %0 %bx%  !

 :pass6
 set y=%1
 if not "%x%" == "!" if "%y%" == "!" set bx=0
 if "%x%" == "!" if not "%y%" == "!" set ax=0
 set IP=pass1
 if not "%x%%y%" == "!!" %0 %ax%
 if %CF% == 1 set sum=1%sum%
 echo set result=%sum% > getrslt.bat
 goto end
The lines

 set IP=pass2
 %0 %ax%

 :pass2
 set dx=%1
 set ax=%2 %3 %4 %5 %6 %7 %8 %9
in conjunction with the goto %IP% line at the beginning of the adder program restart the program, passing the environment variable (a space delimited string) as a list of arguments, the first of which is separated out for processing, while the remainder replace the string just passed (with the spaces restored by the spaces between the argument names). It should be noted that the spaces always go back, even if there are no associated digit characters. This process is repeated for the second number and the engine building code is called to construct an engine for those digits. Then the engine is called to process them (call }add{). When the engine returns, the residual strings are examined to determine if there are any digits remaining. If one has digits and the other doesn't, the short one gets replaced by a zero. Since the string can be all spaces, and multiple spaces cannot be compared as strings, this is non-trivial - the spaces must be removed. Passing the environment variable back into the program through the argument list does this (at pass5). The variable is passed, along with a bang character, back to the program, where %1 is compared with '!'. If the environment variable is all spaces, the bang will be %1, otherwise, it will be a later argument. The x and y variables are set to %1 and compared with '!' is several ways, to determine if either or both number strings are exhausted. If only one, then the program continues, using 0 as the value for the short string. If both are exhausted (x = y = !), then the program terminates after considering whether to prefix the carry to the sum, or not. The last thing before exit is to write the batch file that will communicate across the separate environment barrier (remember - this program is running under a secondary command processor).

Once the adder terminates, the calling batch file then calls the newly created batch file to set the sum into the RESULT variable and then erases the temporary files (all the tables in the secondary environment vanished when the secondary command processor terminated).

Note that the result is always the same length as the longer of the two original numbers, oe one digit longer. If it is longer, the carry falg (CF) is 1. This can be used to signal overrange when using the code to build file names. When building file names, the length can be forced with leading zeros on the base number.

You can download or view the files TESTADD.BAT, GETNSTR.BAT, and DADD.BAT here. Netscape may trash the line ends of those if you save them, so if you are using that browser, you will have to either remove the extra CR characters yourself or download this ZIP archive of all three files.

  ** Copyright 1995, Ted Davis - all rights reserved ** 

Input and feedback from readers are welcome. NOTE: the subject of the message must contain the word "batch" for the message to get past the spam filter.

Back to the Table of Contents page

Back to my personal links page - back to my home page