DC - An Interactive Desk Calculator
Robert Morris
Lorinda Cherry
ABSTRACT
DC is an interactive desk calculator program
implemented on the UNIX- time-sharing system to do
arbitrary-precision integer arithmetic. It has
provision for manipulating scaled fixed-point
numbers and for input and output in bases other
than decimal.
The size of numbers that can be manipulated
is limited only by available core storage. On typ-
ical implementations of UNIX, the size of numbers
that can be handled varies from several hundred
digits on the smallest systems to several thousand
on the largest.
Editor's note: the description of the implementation
details of DC in this paper is only valid for the original
version of DC. The current version of DC uses a different
approach.
DC is an arbitrary precision arithmetic package imple-
mented on the UNIX time-sharing system in the form of an
interactive desk calculator. It works like a stacking calcu-
lator using reverse Polish notation. Ordinarily DC operates
on decimal integers, but one may specify an input base, out-
put base, and a number of fractional digits to be main-
tained.
A language called BC [1] has been developed which
accepts programs written in the familiar style of higher-
level programming languages and compiles output which is
interpreted by DC. Some of the commands described below were
designed for the compiler interface and are not easy for a
_________________________
- UNIX is a registered trademark of AT&T Bell Labora-
tories in the USA and other countries.
December 24, 2022
USD:5-2 DC - An Interactive Desk Calculator
human user to manipulate.
Numbers that are typed into DC are put on a push-down
stack. DC commands work by taking the top number or two off
the stack, performing the desired operation, and pushing the
result on the stack. If an argument is given, input is taken
from that file until its end, then from the standard input.
SYNOPTIC DESCRIPTION
Here we describe the DC commands that are intended for
use by people. The additional commands that are intended to
be invoked by compiled output are described in the detailed
description.
Any number of commands are permitted on a line. Blanks
and new-line characters are ignored except within numbers
and in places where a register name is expected.
The following constructions are recognized:
number
The value of the number is pushed onto the main stack.
A number is an unbroken string of the digits 0-9 and
the capital letters A-F which are treated as digits
with values 10-15 respectively. The number may be pre-
ceded by an underscore _ to input a negative number.
Numbers may contain decimal points.
+ - * % ^
The top two values on the stack are added (+), sub-
tracted (-), multiplied (*), divided (/), remaindered
(%), 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 of numbers with decimal points.
An exponent must not have any digits after the decimal
point.
sx
The top of the main stack is popped and stored into a
register named x, where x may be any character. If the
s is capitalized, x is treated as a stack and the value
is pushed onto it. Any character, even blank or new-
line, is a valid register name.
lx
The value in register x is pushed onto the stack. The
register x is not altered. If the l is capitalized,
December 24, 2022
DC - An Interactive Desk Calculator USD:5-3
register x is treated as a stack and its top value is
popped onto the main stack.
All registers start with empty value which is treated as a
zero by the command l and is treated as an error by the com-
mand L.
d
The top value on the stack is duplicated.
p
The top value on the stack is printed. The top value
remains unchanged.
f
All values on the stack and in registers are printed.
x
treats the top element of the stack as a character
string, removes it from the stack, and executes it as a
string of DC commands.
[ ... ]
puts the bracketed character string onto the top of the
stack.
q
exits the program. If executing a string, the recursion
level is popped by two. If q is capitalized, the top
value on the stack is popped and the string execution
level is popped by that value.
<x >x =x !<x !>x !=x
The top two elements of the stack are popped and com-
pared. Register x is executed if they obey the stated
relation. Exclamation point is negation.
v
replaces 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, see the detailed description below.
!
interprets the rest of the line as a UNIX command.
December 24, 2022
USD:5-4 DC - An Interactive Desk Calculator
Control returns to DC when the UNIX command terminates.
c
All values on the stack are popped; the stack becomes
empty.
i
The top value on the stack is popped and used as the
number radix for further input. If i is capitalized,
the value of the input base is pushed onto the stack.
No mechanism has been provided for the input of arbi-
trary numbers in bases less than 1 or greater than 16.
o
The top value on the stack is popped and used as the
number radix for further output. If o is capitalized,
the value of the output base is pushed onto the stack.
k
The top of the stack is popped, and that value is used
as a scale factor that influences the number of decimal
places that are maintained during multiplication, divi-
sion, and exponentiation. The scale factor must be
greater than or equal to zero and less than 100. If k
is capitalized, the value of the scale factor is pushed
onto the stack.
z
The value of the stack level is pushed onto the stack.
?
A line of input is taken from the input source (usually
the console) and executed.
DETAILED DESCRIPTION
Internal Representation of Numbers
Numbers are stored internally using a dynamic storage
allocator. Numbers are kept in the form of a string of
digits to the base 100 stored one digit per byte (centennial
digits). The string is stored with the low-order digit at
the beginning of the string. For example, the representation
of 157 is 57,1. After any arithmetic operation on a number,
care is taken that all digits are in the range 0-99 and that
the number has no leading zeros. The number zero is
represented by the empty string.
December 24, 2022
DC - An Interactive Desk Calculator USD:5-5
Negative numbers are represented in the 100's comple-
ment notation, which is analogous to two's complement nota-
tion for binary numbers. The high order digit of a negative
number is always -1 and 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 negative numbers is ease of addi-
tion. When addition is performed digit by digit, the result
is formally correct. The result need only be modified, if
necessary, to put it into canonical form.
Because the largest valid digit is 99 and the byte can
hold numbers twice that large, addition can be carried out
and the handling of carries done later when that is con-
venient, as it sometimes is.
An additional byte is stored with each number beyond
the high order digit to indicate the number of assumed
decimal digits after the decimal point. The representation
of .001 is 1,3 where the scale has been italicized to
emphasize the fact that it is not the high order digit. The
value of this extra byte is called the scale factor of the
number.
The Allocator
DC uses a dynamic string storage allocator for all of
its internal storage. All reading and writing of numbers
internally is done through the allocator. Associated with
each string in the allocator is a four-word header contain-
ing pointers to 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 DC is done via
pointers to these headers.
The allocator initially has one large string on a list
of free strings. All headers except the one pointing to
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 higher power of 2. When a request for a
string is made, the allocator first checks the free list to
see if there is a string of the desired size. If none is
found, the allocator finds the next larger free string and
splits it repeatedly until it 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 into larger ones. Since all strings are
the result of splitting large strings, each string has a
neighbor that is next to it in core and, if free, can be
combined with it to make a string twice as long. This is an
implementation of the 'buddy system' of allocation described
in [2].
December 24, 2022
USD:5-6 DC - An Interactive Desk Calculator
Failing 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 limitation on
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 of headers, it also asks the system for more space.
There are routines in the allocator for reading, writ-
ing, copying, rewinding, forward-spacing, and backspacing
strings. All string manipulation is done using these rou-
tines.
The reading and writing routines increment the read
pointer or write pointer so that the characters of a string
are read or written in succession by a series of read or
write calls. The write pointer is interpreted as the end of
the information-containing portion of a string and a call to
read beyond that point returns an end-of-string indication.
An attempt to write beyond the end of a string causes the
allocator to allocate a larger space and then copy the old
string into the larger block.
Internal Arithmetic
All arithmetic operations are done on integers. The
operands (or operand) needed for the operation are popped
from the main stack and their scale factors stripped off.
Zeros are added or digits removed as necessary to get a
properly scaled result from the internal arithmetic routine.
For example, if the scale of the operands is different and
decimal alignment is required, as it is for addition, zeros
are appended to the operand with the smaller scale. After
performing the required arithmetic operation, the proper
scale factor is appended to the end of the number before it
is pushed on the stack.
A register called scale plays a part in the results of
most arithmetic operations. scale is the bound on the number
of decimal places retained in arithmetic computations. scale
may be set to the number on the top of the stack truncated
to an integer with the k command. K may be used to push the
value of scale on the stack. scale must be greater than or
equal to 0 and less than 100. The descriptions of the indi-
vidual arithmetic operations will include the exact effect
of scale on the computations.
Addition and Subtraction
The scales of the two numbers are compared and trailing
zeros are supplied to the number with the lower scale to
give both numbers the same scale. The number with the
smaller scale is multiplied by 10 if the difference of the
scales is odd. The scale of the result is then set to the
larger of the scales of the two operands.
December 24, 2022
DC - An Interactive Desk Calculator USD:5-7
Subtraction is performed by negating the number to be
subtracted and proceeding as in addition.
Finally, the addition is performed digit by digit from
the low order end of the number. The carries are propagated
in the usual way. The resulting number is brought into
canonical form, which may require stripping of leading
zeros, or for negative numbers replacing the high-order con-
figuration 99,-1 by the digit -1. In any case, digits which
are not in the range 0-99 must be brought into that range,
propagating any carries or borrows that result.
Multiplication
The scales are removed from the two operands and saved.
The operands are both made positive. Then multiplication is
performed in a digit by digit manner that exactly mimics the
hand method of multiplying. The first number is multiplied
by each digit of the second number, beginning with its low
order digit. The intermediate products are accumulated into
a partial sum which becomes the final product. The product
is put into the canonical form and its sign is computed from
the signs of the original operands.
The scale of the result is set equal to the sum of the
scales of the two operands. If that scale is larger than the
internal register scale and also larger than both of the
scales of the two operands, then the scale of the result is
set equal to the largest of these three last quantities.
Division
The scales are removed from the two operands. Zeros are
appended or digits removed from the dividend to make the
scale of the result of the integer division equal to the
internal quantity scale. The signs are removed and saved.
Division is performed much as it would be done by hand.
The difference of the lengths of the two numbers is com-
puted. If the divisor is longer than the dividend, zero is
returned. Otherwise the top digit of the divisor is divided
into the top two digits of the dividend. The result is used
as the first (high-order) digit of the quotient. It may turn
out be one unit too low, but if it is, the next trial quo-
tient will be larger than 99 and this will be adjusted at
the end of the process. The trial digit is multiplied by the
divisor and the result subtracted from the dividend and the
process is repeated to get additional quotient digits until
the remaining dividend is smaller than the divisor. At the
end, the digits of the quotient are put into the canonical
form, with propagation of carry as needed. The sign is set
from the sign of the operands.
December 24, 2022
USD:5-8 DC - An Interactive Desk Calculator
Remainder
The division routine is called and division is per-
formed exactly as described. The quantity returned is the
remains of the dividend at the end of the divide process.
Since division truncates toward zero, remainders have the
same sign as the dividend. The scale of the remainder is set
to the maximum of the scale of the dividend and the scale of
the quotient plus the scale of the divisor.
Square Root
The scale is stripped from the operand. Zeros are added
if necessary to make the integer result have a scale that is
the larger of the internal quantity scale and the scale of
the operand.
The method used to compute sqrt(y) is Newton's method
with successive approximations by the rule
__)
The initial guess is found=by/takingnthe integer square root
of the top two digits.
Exponentiation
Only exponents with zero scale factor are handled. If
the exponent is zero, then the result is 1. If the exponent
is negative, then it is made positive and the base is
divided into one. The scale of the base is removed.
The integer exponent is viewed as a binary number. The
base is repeatedly squared and the result is obtained as a
product of those powers of the base that correspond to the
positions of the one-bits in the binary representation of
the exponent. Enough digits of the result are removed to
make the scale of the result the same as if the indicated
multiplication had been performed.
Input Conversion and Base
Numbers are converted to the internal representation as
they are read in. The scale stored with a number is simply
the number of fractional digits input. Negative numbers are
indicated by preceding the number with a _ (an underscore).
The hexadecimal digits A-F correspond to the numbers 10-15
regardless of input base. The i 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 to
8 or 16 to do octal or hexadecimal to decimal conversions.
The command I will push the value of the input base on the
stack.
December 24, 2022
DC - An Interactive Desk Calculator USD:5-9
Output Commands
The command p 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 output by typing the
command f. The o command can be used to change the output
base. This command uses the top of the stack, truncated to
an integer as the base for all further output. The output
base in initialized to 10. It will work correctly for any
base. The command O pushes the value of the output base on
the stack.
Output Format and Base
The input and output bases only affect the interpreta-
tion of numbers on input and output; they have no effect 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 are useful. A particularly useful output base is
100000, which has the effect of grouping digits in fives.
Bases of 8 and 16 can be used for decimal-octal or decimal-
hexadecimal conversions.
Internal Registers
Numbers or strings may be stored in internal registers
or loaded on the stack from registers with the commands s
and l. The command sx pops the top of the stack and stores
the result in register x. x can be any character. lx puts
the contents of register x on the top of the stack. The l
command has no effect on the contents of register x. The s
command, however, is destructive.
Stack Commands
The command c clears the stack. The command d pushes a
duplicate of the number on the top of the stack on the
stack. The command z pushes the stack size on the stack. The
command X replaces the number on the top of the stack with
its scale factor. The command Z replaces the top of the
stack with its length.
Subroutine Definitions and Calls
Enclosing a string in [ ] pushes the ascii string on
the stack. The q command quits or in executing a string,
pops the recursion levels by two.
Internal Registers - Programming DC
The load and store commands together with [ ] to store
strings, x to execute and the testing commands '<', '>',
'=', '!<', '!>', '!=' can be used to program DC. The x
December 24, 2022
USD:5-10 DC - An Interactive Desk Calculator
command assumes the top of the stack is an string of DC com-
mands and executes it. The testing commands compare the top
two elements on the stack and if the relation holds, execute
the register that follows the relation. For example, to
print the numbers 0-9,
[lip1+ si li10>a]sa
0si lax
Push-Down Registers and Arrays
These commands were designed for used by a compiler,
not by people. They involve push-down registers and arrays.
In addition to the stack that commands work on, DC can be
thought of as having individual stacks for each register.
These registers are operated on by the commands S and L. Sx
pushes the top value of the main stack onto the stack for
the register x. Lx pops the stack for register x and puts
the result on the main stack. The commands s and l also work
on registers but not as push-down stacks. l doesn't effect
the top of the register stack, and s destroys what was there
before.
The commands to work on arrays are : and ;. :x pops the
stack and uses this value as an index into the array x. The
next element on the stack is stored at this index in x. An
index must be greater than or equal to 0 and less than 2048.
;x is the command to load the main stack from the array x.
The value on the top of the stack is the index into the
array x of the value to be loaded.
Miscellaneous Commands
The command ! interprets the rest of the line as a UNIX
command and passes it to UNIX to execute. One other compiler
command is Q. This command uses the top of the stack as the
number of levels of recursion to skip.
DESIGN CHOICES
The real reason for the use of a dynamic storage allo-
cator was that a general purpose program could be (and in
fact has been) used for a variety of other tasks. The allo-
cator has some value for input and for compiling (i.e. the
bracket [...] commands) where it cannot be known in advance
how long a string will be. The result was that at a modest
cost in execution time, all considerations of string alloca-
tion and sizes of strings were removed from the remainder of
the program and debugging was made easier. The allocation
method used wastes approximately 25% of available space.
The choice of 100 as a base for internal arithmetic
seemingly has no compelling advantage. Yet the base cannot
December 24, 2022
DC - An Interactive Desk Calculator USD:5-11
exceed 127 because of hardware limitations and at the cost
of 5% in space, debugging was made a great deal easier and
decimal output was made much faster.
The reason for a stack-type arithmetic design was to
permit all DC commands from addition to subroutine execution
to be implemented in essentially the same way. The result
was a considerable degree of logical separation of the final
program into modules with very little communication between
modules.
The rationale for the lack of interaction between the
scale and the bases was to provide an understandable means
of proceeding after a change of base or scale when numbers
had already been entered. An earlier implementation which
had global notions of scale and base did not work out well.
If the value of scale were to be interpreted in the current
input or output base, then a change of base or scale in the
midst of a computation would cause great confusion in the
interpretation of the results. The current scheme has the
advantage that the value of the input and output bases are
only used for input and output, respectively, and they are
ignored in all other operations. The value of scale is not
used for any essential purpose by any part of the program
and it is used only to prevent the number of decimal places
resulting from the arithmetic operations from growing beyond
all bounds.
The design rationale for the choices for the scales of
the results of arithmetic were that in no case should any
significant digits be thrown away if, on appearances, the
user actually wanted them. Thus, if the user wants to add
the numbers 1.5 and 3.517, it seemed reasonable to give him
the result 5.017 without requiring him to unnecessarily
specify his rather obvious requirements for precision.
On the other hand, multiplication and exponentiation
produce results with many more digits than their operands
and it seemed reasonable to give as a minimum the number of
decimal places in the operands but not to give more than
that number of digits unless the user asked for them by
specifying a value for scale. Square root can be handled in
just the same way as multiplication. The operation of divi-
sion gives arbitrarily many decimal places and there is sim-
ply no way to guess how many places the user wants. In this
case only, the user must specify a scale to get any decimal
places at all.
The scale of remainder was chosen to make it possible
to recreate the dividend from the quotient and remainder.
This is easy to implement; no digits are thrown away.
December 24, 2022
USD:5-12 DC - An Interactive Desk Calculator
References
[1] L. L. Cherry, R. Morris, BC - An Arbitrary Precision
Desk-Calculator Language.
[2] K. C. Knowlton, A Fast Storage Allocator, Comm. ACM 8,
pp. 623-625 (Oct. 1965).
December 24, 2022