.RP....TM 75-1271-8 39199 39199-11.TLDC \- An Interactive Desk Calculator.AU "MH 2C-524" 3878Robert Morris.AULorinda Cherry.AI.MH.ABDC is an interactive desk calculator program implementedon the.UXtime-sharing system to do arbitrary-precisioninteger arithmetic.It has provision for manipulating scaled fixed-point numbers andfor input and output in bases other than decimal..PPThe size of numbers that can be manipulated is limitedonly by available core storage.On typical implementations of.UX ,the size of numbers thatcan be handled varies from several hundred digits on the smallestsystems to several thousand on the largest..AE.PP.SH.ND.PPDC is an arbitrary precision arithmetic package implementedon the.UXtime-sharing systemin the form of an interactive desk calculator.It works like a stacking calculator using reverse Polish notation.Ordinarily DC operates on decimal integers, but one mayspecify an input base, output base, and a number of fractionaldigits to be maintained..PPA language called BC [1] has been developed which acceptsprograms written in the familiar style of higher-levelprogramming languages and compiles output which isinterpreted by DC.Some of the commands described below were designedfor the compiler interface and are not easy for a human userto manipulate..PPNumbers that are typed into DC are put on a push-downstack.DC commands work by taking the top number or twooff the stack, performing the desired operation, and pushing the resulton the stack.If an argument is given,input is taken from that file until its end,then from the standard input..SHSYNOPTIC DESCRIPTION.PPHere we describe the DC commands that are intendedfor use by people.  The additional commands that areintended to be invoked by compiled output aredescribed in the detailed description..PPAny number of commands are permitted on a line.Blanks and new-line characters are ignored except within numbersand in places where a register name is expected..PPThe following constructions are recognized:.SHnumber.IPThe value of the number is pushed onto the main stack.A number is an unbroken string of the digits 0-9and the capital letters A\-F which are treated as digitswith values 10\-15 respectively.The number may be preceded by an underscore \*_ to input anegative number.Numbers may contain decimal points..SH+  \-  *  %  ^.IPThetop two values on the stack are added(\fB+\fP),subtracted(\fB\-\fP),multiplied (\fB*\fP),divided (\fB/\fP),remaindered (\fB%\fP),or exponentiated (^).The two entries are popped off the stack;the result is pushed on the stack in their place.The result of a division is an integer truncated toward zero.See the detailed description below for the treatment ofnumbers with decimal points.An exponent must not have any digits after the decimal point..SHs\fIx\fP.IPThetop of the main stack is popped and stored intoa register named \fIx\fP, where \fIx\fP may be any character.Ifthe.ft Bs.ftis capitalized,.ft Ix.ftis treated as a stack and the value is pushed onto it.Any character, even blank or new-line, is a valid register name..SHl\fIx\fP.IPThevalue in register.ft Ix.ftis pushed onto the stack.The register.ft Ix.ftis not altered.If the.ft Bl.ftis capitalized,register.ft Ix.ftis treated as a stack and its top value is popped onto the main stack..LPAll registers start with empty value which is treated as a zeroby the command \fBl\fP and is treated as an error by the command \fBL\fP..SH.SHd.IPThetop value on the stack is duplicated..SHp.IPThe top value on the stack is printed.The top value remains unchanged..SHf.IPAll values on the stack and in registers are printed..SHx.IPtreats the top element of the stack as a character string,removes it from the stack, andexecutes it as a string of DC commands..SH[ ... ].IPputs the bracketed character string onto the top of the stack..SHq.IPexits the program.If executing a string, the recursion level ispopped by two.If.ft Bq.ftis capitalized,the top value on the stack is popped and the string execution level is poppedby that value..SH<\fIx\fP  >\fIx\fP  =\fIx\fP  !<\fIx\fP  !>\fIx\fP  !=\fIx\fP.IPThetop two elements of the stack are popped and compared.Register.ft Ix.ftis executed if they obey the statedrelation.Exclamation point is negation..SHv.IPreplaces the top element on the stack by its square root.The square root of an integer is truncated to an integer.For the treatment of numbers with decimal points, seethe detailed description below..SH!.IPinterprets the rest of the line as a.UXcommand.Control returns to DC when the.UXcommand terminates..SHc.IPAll values on the stack are popped; the stack becomes empty..SHi.IPThe top value on the stack is popped and used as thenumber radix for further input.If \fBi\fP is capitalized, the value ofthe input base is pushed onto the stack.No mechanism has been provided for the input of arbitrarynumbers in bases less than 1 or greater than 16..SHo.IPThe top value on the stack is popped and used as thenumber radix for further output.If \fBo\fP is capitalized, the value of the outputbase is pushed onto the stack..SHk.IPThe top of the stack is popped, and that value is used asa scale factorthat influences the number of decimal placesthat are maintained during multiplication, division, and exponentiation.The scale factor must be greater than or equal to zero andless than 100.If \fBk\fP is capitalized, the value of the scale factoris pushed onto the stack..SHz.IPThe value of the stack level is pushed onto the stack..SH?.IPA line of input is taken from the input source (usually the console)and executed..SHDETAILED DESCRIPTION.SHInternal Representation of Numbers.PPNumbers are stored internally using a dynamic storage allocator.Numbers are kept in the form of a stringof digits to the base 100 stored one digit per byte(centennial digits).The string is stored with the low-order digit at thebeginning of the string.For example, the representation of 157is 57,1.After any arithmetic operation on a number, care is takenthat all digits are in the range 0\-99 and thatthe number has no leading zeros.The number zero is represented by the empty string..PPNegative numbers are represented in the 100's complementnotation, which is analogous to two's complement notation for binarynumbers.The high order digit of a negative number is always \-1and all other digits are in the range 0\-99.The digit preceding the high order \-1 digit is never a 99.The representation of \-157 is 43,98,\-1.We shall call this the canonical form of a number.The advantage of this kind of representation of negativenumbers is ease of addition.  When addition is performed digitby digit, the result is formally correct.  The result need onlybe modified, if necessary, to put it into canonical form..PPBecause the largest valid digit is 99 and the byte canhold numbers twice that large, addition can be carried outand the handling of carries done later whenthat is convenient, as it sometimes is..PPAn additional byte is stored with each number beyondthe high order digit to indicate the number ofassumed decimal digits after the decimal point.  The representationof .001 is 1,\fI3\fPwhere the scale has been italicized to emphasize the fact that itis not the high order digit.The value of this extra byte is called the.ft Bscale factor.ftof the number..SHThe Allocator.PPDC uses a dynamic string storage allocatorfor all of its internal storage.All reading and writing of numbers internally is done throughthe allocator.Associated with each string in the allocator is a four-word header containing pointersto the beginning of the string, the end of the string,the next place to write, and the next place to read.Communication between the allocator and DCis done via pointers to these headers..PPThe allocator initially has one large string on a listof free strings.  All headers except the one pointingto this string are on a list of free headers.Requests for strings are made by size.The size of the string actually supplied is the next higherpower of 2.When a request for a string is made, the allocatorfirst checks the free list to see if there isa string of the desired size.If none is found, the allocator finds the next larger free string and splits it repeatedly untilit has a string of the right size.Left-over strings are put on the free list.If there are no larger strings,the allocator tries to coalesce smaller free strings intolarger ones.Since all strings are the resultof splitting large strings,each string has a neighbor that is next to it in coreand, if free, can be combined with it to make a string twice as long.This is an implementation of the `buddy system' of allocationdescribed in [2]..PPFailing to find a string of the proper length after coalescing,the allocator asks the system for more space.The amount of space on the system is the only limitationon the size and number of strings in DC.If at any time in the process of trying to allocate a string, the allocator runs out ofheaders, it also asks the system for more space..PPThere are routines in the allocator for reading, writing, copying, rewinding,forward-spacing, and backspacing strings.All string manipulation is done using these routines..PPThe reading and writing routinesincrement the read pointer or write pointer so thatthe characters of a string are read or written insuccession by a series of read or write calls.The write pointer is interpreted as the end of theinformation-containing portion of a string and a callto read beyond that point returns an end-of-string indication.An attempt to write beyond the end of a stringcauses the allocator toallocate a larger space and then copythe old string into the larger block..SHInternal Arithmetic.PP