!pr2
18-digit Arithmetic, Part 3................Bob Sander-Cederlof

Plowing ahead, this installment will offer the division and input conversion subroutines.

You will remember that we covered addition and subtraction in the May 1984 issue, and multiplication in June.  Now it's time for division, which completes the fundamental arithmetic operations.  All four of these routines are designed to operate on two arguments stored in DAC and ARG, leaving the result in DAC.  Addition and subtraction leave "garbage" in ARG.  Multiplication leaves ARG unchanged.  Division leaves in ARG what was in DAC.

Division is simple enough in concept, but no one would call it simple in implementation.  "How many groups of X are in Y?"  "If I deal an entire deck of 52 cards to 4 people, how many will each person get?"  "If I scramble a dozen eggs, and serve them in equal-size portions to 7 people, how many eggs will each eat?"  (Really, I am good cook!)

Suppose I have a pile of pennies, and want to find out how many dollars they represent.  I will count out piles of 100 pennies, moving them into separate piles.  Then I will count the little piles.  Now, suppose I have two 18-digit numbers in my computer and want to divide the one in ARG by the one in DAC....  I will subtract the value in DAC from the one in ARG over and over, until I finally cross zero.  Then if I was wise enough to count how many times I did the subtraction, I have the answer.

Let's look at the problem in more detail now.  What I want to do is divide the value in ARG by the value in DAC:

       numerator (in ARG)
      --------------------  =  quotient (in DAC)
      denominator (in DAC)

Numbers in DP18 can be positive or negative, so we have to remember the rules of signed division.  If the signs of the numerator and denominator are the same, the quotient will be positive; if they are different, the quotient will be negative.

Numbers in DP18 are coded as 18-digit fractions with a power- of-ten exponent.  Remembering algebra:

       .f * 10^m      f
       ---------  =  --- * 10^(m-n)
       .g * 10^n      g

The 18-digit fractions are normalized so that there are no leading zeroes.  That is, the value will either be all zero, or it will be between .1 and .999999999999999999 (inclusive).

I think it is time now to start looking at the program.  In the listing which follows there are references to subroutines and variables which we defined in the previous two installments of this series.

Line 4250 swaps the contents of ARG and DAC.  I did it this way because it leaves something possibly useful in ARG after the division is finished.  If you wanted to form the reciprocal quotient, DAC=DAC/ARG, you can enter at DDIVR, which skips the swapping step.

Lines 4260-4270 check for the illegal case of division by zero.  If I divide something into zero-size parts, I get an infinite number of these parts.  That's fine, but the DP18 has no representation for infinity; therefore we say it is illegal to divide by zero, just like Applesoft does.  Some computers and some software arithmetic packages do represent infinity, but DP18 does not.  Zero values are represented by having an exponent byte of zero, so we only have to check one byte here.

Lines 4280-4310 form the sign of the quotient.  This is the same as lines 1280-1310 of the DMULT listing given last month, and so we could make them into a subroutine.  The subroutine would take 10 bytes, and the two JSR's make another 6.  That's 16 bytes, against the 18 bytes for the two versions of in-line code.  Saves a total of 2 bytes, at a cost of adding 12 cpu cycles to both multiply and divide.  (Small digression into the kind of trade-offs I am continually making....)

Lines 4330-4390 compute the exponent of the quotient, and check for overflow and underflow cases.  The special case of the numerator being zero is also caught here, line 4350.  Line 4380 restores the bias of $40.  Bias?  Remember, the exponent is kept in memory with $40 added to it, so that the range -63 through +63 is represented by $01 through $7F.

If the new exponent is still in the range $00 through $7F, we will go ahead and do the division.  If not, the quotient is either too small (underflow) or too large (overflow).  For example, 10^-40 / 10^40 results in 10^-80, which is too small for DP18.  Lines 4410-4470 catch these cases, and change the quotient to zero.  If the new exponent is between $80 and $BF, it represents 10^64 or larger, and so we call on the Applesoft OVERFLOW error.

Lines 4500-4550 set up the loop which does the actual division of the fractions.  The 6502's decimal mode will be used during this loop.  Ten bytes in MAC (defined in DMULT last month) will be used to hold the quotient until we are through with DAC.  The X-register will be used to count out the 20 digits.   The other end of the loop is in lines 4920-4930, where X is decremented and tested.

The body of the loop is really a lot simpler than it looks.  Basically, ARG is subtracted from DAC until DAC goes negative.  The number of subtractions is counted in MAC+9.  Then ARG is added back to DAC to make it positive again, and MAC+9 decremented.  The result is a quotient digit in MAC+9, and a remainder in DAC.  One extra digit is needed, extending DAC on the left end.  This digit is carried in the stack.  See it pushed at line 4710, pulled at line 4790.
!np
After each digit of the quotient is determined, both MAC and DAC are shifted left one digit place.  This might shift a significant digit out of DAC (the remainder), so it is lifted out first and saved on the stack (lines 4570-4630).  If the first two digits of the remainder (happen to be "00", then we know without subtracting that the quotient digit in this position will also be "0".  (Remember that the leading digit of the denominator in ARG is NEVER zero.)  This fact can speed up divisions, so it is tested for at line 4580, with lines 4670-4680.

After all 20 digits are formed, the loop terminates.  Line 4950 then returns us to binary mode.  Line 4960 adds one to the quotient exponent, adjusting for the normalization step.  (.9/.1 = 9, but we want to represent it as .9*10^1.)  If the exponent now is negative ($80), it may be still in range if the leading digit of the quotient is zero (.1/.9 = 0.1111...).  This test takes place at lines 4970-5000.

Lines 5020-5060 copy the quotient from MAC to DAC.  These are the same as lines 1330-1370 in DMULT, so they could be made into a subroutine.  Two other candidates for subroutines are lines 4720-4780, which are identical to lines 1680-1740 of DADD (May 1984); and lines 4830-4890, which are the same as 1530-1590 of DADD.

Finally, DDIV exits by jumping to NORMALIZE.DAC.

Doesn't all this take a lot of time?  You bet it does!  I timed it in the full DP18 package with a program that looked like this:

       &DP:INPUT X(0) : INPUT X(2)
       FOR I = 1 TO 100
       &DP:X(4) = X(0)/X(2)
       NEXT

I determined the loop overhead by entering a value zero for X(0).  Since this case skips around nearly everything in DDIV, I called its time the loop overhead time.  After subtracting out the loop overhead, the times look like this:

       0/anything      0
       x/x             12 msec
       1/9=.1111...    23 msec
       8/9=.8888...    49 msec
       1/7=.142857...  35 msec

It looks like the maximum time, which would be for a quotient with all 20 digits = 9, would be about 53 msec.  The average time, about 35 msec.  This compares with an average Applesoft 9-digit division time of about 7 msec.


<<<listing here.>>>
!np





















DP18 Input Conversion

The input conversion subroutine processes characters from memory to produce a value in DAC.  This is analogous to what the equivalent subroutine in Applesoft ROMs does.

It is so analogous, in fact, that I even depend upon CHRGET and CHRGOT to fetch successive characters from memory.  It is a lot faster than Applesoft conversion, however, because it is BCD coded rather than binary.  This means that, stripping away the frills such as sign, exponent part, and decimal point, it even easier than an ASCII to hex conversion.

Of course, we need all those frills.  Look ahead to the program listing which follows:  Lines 1200-1220, just those three little lines, handle the conversion of digits.  All the rest of the page is for frills!  Well, to be honest about it, two of the three lines call subroutines, but still, the frills predominate.

The acceptable format of numbers is basically the same as that which normal Applesoft accepts.  A leading sign is optional.  The numeric portion can be more than 20 digits long, but only the first 20 will be accumulated (not counting leading zeroes).  A decimal point is optional anywhere in the numeric portion.  An exponent part can be appended to the numeric portion, and consists of the letter "E", and optional sign, and one or two digits.  The exponent can be up to 81, just so the final number evaluates between .1*10^-63 and .9999...9*10^63.  Numbers smaller than .1*10^-63 will be changed to zero, and numbers larger than .9999...9*10^63 will cause an OVERFLOW ERROR.

Looking at the program, lines 1040-1080 clear a working area which comprises DAC and four other variables:  SGNEXP, EXP, DGTCNT, and DECFLG.  SGNEXP will be used to hold the sign of the exponent part; EXP will hold the value of the exponent part; DGTCNT will count the digits in the numeric portion; and DECFLG will flag the occurrence of a decimal point.  DAC includes DAC.SIGN.  Note that the X-register will be left with $FF, which fact is important at line 1170 below.

Lines 1090-1100 preset the DAC.EXPONENT to $40, which indicates 10^0.  This will be incremented along with DGTCNT until a decimal point is encountered.

Lines 1110-1180 handle the optional leading sign.  DAC.SIGN has already been cleared above, indicating the positive case.  If a minus sign is in front of the number, line 1170 sets DAC.SIGN negative.  Note that calling CHRGOT and CHRGET to retrieve characters automatically eliminates (ignores) blanks.  CHRGOT/CHRGET also checks whether the character retrieved is a digit or not, and indicates digits by carry clear.  If the first non-blank character is a digit, we immediately jump to the numeric loop at line 1200.  If not, the subroutine FIN.SIGN checks for a + or - character.  The + or - may or may not be tokenized, depending on whether the string is from an INPUT statement or is a constant embedded in a program, so we have to check for both the character and the token form of both signs.  FIN.SIGN handles this checking.

If that first character is neither a digit nor a sign, it may be a letter "E" or a decimal point; so, we go down to lines 1240-1270 to check for those two cases.  If neither of these either, we must be at the end of the number.  If it is a decimal point, lines 1630-1650 record the fact that a decimal point was found and also check whether this is the first one found or not.  If the first, back we go to continue looking for digits.  If not the first, it must be the end of the number, so we fall into the final processing section at line 1670.

Exponents are more difficult, because the value actually must be converted from ASCII to binary.  Lines 1290-1610 do the work, including handling of the optional sign, and range checking.

Lines 1670-1730 compute the final exponent value.  This is the number of digits before the decimal point (not counting any leading zeroes you may have typed to confuse me) plus the exponent computed in the optional "E" field.  If the result is negative, between $C0 and $FF, it indicates underflow; in this case, the value is changed to zero.  If there were no non-zero digits in the numeric portion, the value is set to zero regardless of any "E" field.  If the resulting exponent is between $80 and $BF, it indicates OVERFLOW.

Lines 1840-2130 accumulate individual digits.  DGTCNT is used to index into the nybbles of DAC, and the digit is stored directly into place.  Leading zeroes on the numeric field are handled here (lines 2090-2120).  Leading zeroes before a decimal point are entirely ignored, while leading zeroes after a decimal point cause the DAC.EXPONENT to be decremented.  The incrementation of DAC.EXPONENT for each significant digit on the left of the decimal point is also taken care of here (lines 2020-2070).

This complete the third installment of DP18.  We are well on the way to a working subset of the entire package.  We still need output conversion and some sort of linkage to Applesoft before we can begin to see it all run.  The entire DP18 package really exists, and works, now.  It includes PRINT USING, very fancy input screen handling, full expression parsing, and all the math functions.  Several of you have been very anxious to get the whole package for use in projects of your own, so we have offered a source code license to DP18 on an "as is" basis for only $200.
