All arithmetic operations are done on integers.The operands (or operand) needed for the operation are poppedfrom the main stack and their scale factors stripped off.Zeros are added or digits removed as necessary to geta properly scaled result from the internal arithmetic routine.For example, if the scale of the operands is different and decimalalignment is required, as it is foraddition, zeros are appended to the operand with the smallerscale.After performing the required arithmetic operation,the proper scale factor is appended to the end of the number beforeit is pushed on the stack..PPA register called \fBscale\fP plays a partin the results of most arithmetic operations.\fBscale\fP is the bound on the number of decimal places retained inarithmetic computations.\fBscale\fP may be set to the number on the top of the stacktruncated to an integer with the \fBk\fP command.\fBK\fP may be used to push the value of \fBscale\fP on the stack.\fBscale\fP must be greater than or equal to 0 and less than 100.The descriptions of the individual arithmetic operations willinclude the exact effect of \fBscale\fP on the computations..SHAddition and Subtraction.PPThe scales of the two numbers are compared and trailingzeros are supplied to the number with the lower scale to give bothnumbers the same scale.  The number with the smaller scale ismultiplied by 10 if the difference of the scales is odd.The scale of the result is then set to the larger of the scalesof the two operands..PPSubtraction is performed by negating the numberto be subtracted and proceeding as in addition..PPFinally, the addition is performed digit by digit from thelow order end of the number.  The carries are propagatedin the usual way.The resulting number is brought into canonical form, which mayrequire stripping of leading zeros, or for negative numbersreplacing the high-order configuration 99,\-1 by the digit \-1.In any case, digits which are not in the range 0\-99 mustbe brought into that range, propagating any carries or borrowsthat result..SHMultiplication.PPThe scales are removed from the two operands and saved.The operands are both made positive.Then multiplication is performed ina digit by digit manner that exactly mimics the hand methodof multiplying.The first number is multiplied by each digit of the secondnumber, beginning with its low order digit.  The intermediateproducts are accumulated into a partial sum which becomes thefinal product.The product is put into the canonical form and its sign iscomputed from the signs of the original operands..PPThe scale of the result is set equal to the sumof the scales of the two operands.If that scale is larger than the internal register.ft Bscale.ftand also larger than both of the scales of the two operands,then the scale of the result is set equal to the largestof these three last quantities..SHDivision.PPThe scales are removed from the two operands.Zeros are appended or digits removed from the dividend to makethe scale of the result of the integer division equal tothe internal quantity\fBscale\fP.The signs are removed and saved..PPDivision is performed much as it would be done by hand.The difference of the lengths of the two numbersis computed.If the divisor is longer than the dividend,zero is returned.Otherwise the top digit of the divisor is divided into the toptwo digits of the dividend.The result is used as the first (high-order) digit of thequotient.It may turn out be one unit too low, but if it is, the nexttrial quotient will be larger than 99 and this will beadjusted at the end of the process.The trial digit is multiplied by the divisor and the result subtractedfrom the dividend and the process is repeated to getadditional quotient digits until the remainingdividend is smaller than the divisor.At the end, the digits of the quotient are put intothe canonical form, with propagation of carry as needed.The sign is set from the sign of the operands..SHRemainder.PPThe division routine is called and division is performedexactly as described.  The quantity returned is the remains of thedividend at the end of the divide process.Since division truncates toward zero, remainders have the samesign as the dividend.The scale of the remainder is set to the maximum of the scale of the dividend andthe scale of the quotient plus the scale of the divisor..SHSquare Root.PPThe scale is stripped from the operand.Zeros are added if necessary to make theinteger result have a scale that is the larger ofthe internal quantity\fBscale\fPand the scale of the operand..PPThe method used to compute sqrt(y) is Newton's methodwith successive approximations by the rule.EQx sub {n+1} ~=~ half ( x sub n + y over x sub n ).ENThe initial guess is found by taking the integer square rootof the top two digits..SHExponentiation.PPOnly exponents with zero scale factor are handled.  If the exponent iszero, then the result is 1.  If the exponent is negative, thenit is made positive and the base is divided into one.  The scaleof the base is removed..PPThe integer exponent is viewed as a binary number.The base is repeatedly squared and the result isobtained as a product of those powers of the base thatcorrespond to the positions of the one-bits in the binaryrepresentation of the exponent.Enough digits of the resultare removed to make the scale of the result the same as if theindicated multiplication had been performed..SHInput Conversion and Base.PPNumbers are converted to the internal representation as they are readin.The scale stored with a number is simply the number of fractional digits input.Negative numbers are indicated by preceding the number with a \fB\_\fP.The hexadecimal digits A\-F correspond to the numbers 10\-15 regardless of input base.The \fBi\fP command can be used to change the base of the input numbers.This command pops the stack, truncates the resulting number to an integer,and uses it as the input base for all further input.The input base is initialized to 10 but may, for example be changed to8 or 16 to do octal or hexadecimal to decimal conversions.The command \fBI\fP will push the value of the input base on the stack..SHOutput Commands.PPThe command \fBp\fP causes the top of the stack to be printed.It does not remove the top of the stack.All of the stack and internal registers can be outputby typing the command \fBf\fP.The \fBo\fP command can be used to change the output base.This command uses the top of the stack, truncated to an integer asthe base for all further output.The output base in initialized to 10.It will work correctly for any base.The command \fBO\fP pushes the value of the output base on the stack..SHOutput Format and Base.PPThe input and output bases only affectthe interpretation of numbers on input and output; they have noeffect on arithmetic computations.Large numbers are output with 70 characters per line;a \\ indicates a continued line.All choices of input and output bases work correctly, although not all areuseful.A particularly useful output base is 100000, which has the effect ofgrouping digits in fives.Bases of 8 and 16 can be used for decimal-octal or decimal-hexadecimalconversions..SHInternal Registers.PPNumbers or strings may be stored in internal registers or loaded on the stackfrom registers with the commands \fBs\fP and \fBl\fP.The command \fBs\fIx\fR pops the top of the stack andstores the result in register \fBx\fP.\fIx\fP can be any character.\fBl\fIx\fR puts the contents of register \fBx\fP on the top of the stack.The \fBl\fP command has no effect on the contents of register \fIx\fP.The \fBs\fP command, however, is destructive..SHStack Commands.PPThe command \fBc\fP clears the stack.The command \fBd\fP pushes a duplicate of the number on the top of the stackon the stack.The command \fBz\fP pushes the stack size on the stack.The command \fBX\fP replaces the number on the top of the stackwith its scale factor.The command \fBZ\fP replaces the top of the stackwith its length..SHSubroutine Definitions and Calls.PPEnclosing a string in \fB[]\fP pushes the ascii string on the stack.The \fBq\fP command quits or in executing a string, pops the recursion levels by two..SHInternal Registers \- Programming DC.PPThe load and storecommands together with \fB[]\fP to store strings, \fBx\fP to executeand the testing commands `<', `>', `=', `!<', `!>', `!=' can be used to programDC.The \fBx\fP command assumes the top of the stack is an string of DC commandsand executes it.The testing commands compare the top two elements on the stack and if the relation holds, execute the registerthat follows the relation.For example, to print the numbers 0-9,.DS[lip1+  si  li10>a]sa0si  lax.DE.SHPush-Down Registers and Arrays.PPThese commands were designed for used by a compiler, not bypeople.They involve push-down registers and arrays.In addition to the stack that commands work on, DC can be thoughtof as having individual stacks for each register.These registers are operated on by the commands \fBS\fP and \fBL\fP.\fBS\fIx\fR pushes the top value of the main stack onto the stack forthe register \fIx\fP.\fBL\fIx\fR pops the stack for register \fIx\fP and puts the result on the mainstack.The commands \fBs\fP and \fBl\fP also work on registers but not as push-downstacks.\fBl\fP doesn't effect the top of theregister stack, and \fBs\fP destroys what was there before..PPThe commands to work on arrays are \fB:\fP and \fB;\fP.\fB:\fIx\fR pops the stack and uses this value as an index intothe array \fIx\fP.The next element on the stack is stored at this index in \fIx\fP.An index must be greater than or equal to 0 andless than 2048.\fB;\fIx\fR is the command to load the main stack from the array \fIx\fP.The value on the top of the stack is the indexinto the array \fIx\fP of the value to be loaded..SHMiscellaneous Commands.PPThe command \fB!\fP interprets the rest of the line as a .UX command and passesit to .UXto execute.One other compiler command is \fBQ\fP.This command uses the top of the stack as the number of levels of recursion to skip..SHDESIGN CHOICES.PPThe real reason for the use of a dynamic storage allocator wasthat a general purpose program could be (and in fact has been)used for a variety of other tasks.The allocator has some value for input and for compiling (i.e.the bracket [...] commands) where it cannot be known in advancehow long a string will be.The result was that at a modestcost in execution time, all considerations of string allocationand sizes of strings were removed from the remainder of the programand debugging was made easier.  The allocation methodused wastes approximately 25% of available space..PPThe choice of 100 as a base for internal arithmeticseemingly has no compelling advantage.  Yet the base cannotexceed 127 because of hardware limitations and at the costof 5% in space, debugging was made a great deal easier anddecimal output was made much faster..PPThe reason for a stack-type arithmetic design wasto permit all DC commands from addition to subroutine executionto be implemented in essentially the same way.  The resultwas a considerable degree of logical separation of the finalprogram into modules with very little communication betweenmodules..PPThe rationale for the lack of interaction between the scale and the baseswas to provide an understandable means of proceeding aftera change of base or scale when numbers had already been entered.An earlier implementation which had global notions ofscale and base did not work out well.If the value of.ft Bscale.ftwere to be interpreted in the currentinput or output base,then a change of base or scale in the midst of acomputation would cause great confusion in the interpretationof the results.The current scheme has the advantage that the value ofthe input and output basesare only used for input and output, respectively, and theyare ignored in all other operations.The value ofscaleis not used for any essential purpose by any part of the programand it is used only to prevent the number ofdecimal places resulting from the arithmetic operations fromgrowing beyond all bounds..PPThe design rationale for the choices for the scales ofthe results of arithmetic were that in no case shouldany significant digits be thrown away if, on appearances, theuser actually wanted them.  Thus, if the user wantsto add the numbers 1.5 and 3.517, it seemed reasonable to givehim the result 5.017 without requiring him to unnecessarilyspecify his rather obvious requirements for precision..PPOn the other hand, multiplication and exponentiation produceresults with many more digits than their operands and itseemed reasonable to give as a minimum the number of decimalplaces in the operands but not to give more than thatnumber of digitsunless the user asked for them by specifying a value for \fBscale\fP.Square root can be handled in just the same way as multiplication.The operation of division gives arbitrarily many decimal placesand there is simply no way to guess how many places the userwants.In this case only, the user mustspecify a \fBscale\fP to get any decimal places at all..PPThe scale of remainder was chosen to make it possibleto recreate the dividend from the quotient and remainder.This is easy to implement; no digits are thrown away..SHReferences.IP [1]L. L. Cherry, R. Morris,.ft IBC \- An Arbitrary Precision Desk-Calculator Language..ft.IP [2]K. C. Knowlton,.ft IA Fast Storage Allocator,.ftComm. ACM \fB8\fP, pp. 623-625 (Oct. 1965).