![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dc CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / share / doc / usd / 05.dc|
Return to dc CVS log | Up to [CSRG BSD Unix] / 43BSDReno / share / doc / usd / 05.dc |
1.1 root 1: .\" @(#)dc 6.1 (Berkeley) 5/22/86
2: .\"
3: .EH 'USD:5-%''DC \- An Interactive Desk Calculator'
4: .OH 'DC \- An Interactive Desk Calculator''USD:5-%'
5: .\".RP
6: ....TM 75-1271-8 39199 39199-11
7: .ND
8: .TL
9: DC \- An Interactive Desk Calculator
10: .AU "MH 2C-524" 3878
11: Robert Morris
12: .AU
13: Lorinda Cherry
14: .AI
15: .MH
16: .AB
17: DC is an interactive desk calculator program implemented
18: on the
19: .UX
20: time-sharing system to do arbitrary-precision
21: integer arithmetic.
22: It has provision for manipulating scaled fixed-point numbers and
23: for input and output in bases other than decimal.
24: .PP
25: The size of numbers that can be manipulated is limited
26: only by available core storage.
27: On typical implementations of
28: .UX ,
29: the size of numbers that
30: can be handled varies from several hundred digits on the smallest
31: systems to several thousand on the largest.
32: .AE
33: .PP
34: .SH
35: .PP
36: DC is an arbitrary precision arithmetic package implemented
37: on the
38: .UX
39: time-sharing system
40: in the form of an interactive desk calculator.
41: It works like a stacking calculator using reverse Polish notation.
42: Ordinarily DC operates on decimal integers, but one may
43: specify an input base, output base, and a number of fractional
44: digits to be maintained.
45: .PP
46: A language called BC [1] has been developed which accepts
47: programs written in the familiar style of higher-level
48: programming languages and compiles output which is
49: interpreted by DC.
50: Some of the commands described below were designed
51: for the compiler interface and are not easy for a human user
52: to manipulate.
53: .PP
54: Numbers that are typed into DC are put on a push-down
55: stack.
56: DC commands work by taking the top number or two
57: off the stack, performing the desired operation, and pushing the result
58: on the stack.
59: If an argument is given,
60: input is taken from that file until its end,
61: then from the standard input.
62: .SH
63: SYNOPTIC DESCRIPTION
64: .PP
65: Here we describe the DC commands that are intended
66: for use by people. The additional commands that are
67: intended to be invoked by compiled output are
68: described in the detailed description.
69: .PP
70: Any number of commands are permitted on a line.
71: Blanks and new-line characters are ignored except within numbers
72: and in places where a register name is expected.
73: .PP
74: The following constructions are recognized:
75: .SH
76: number
77: .IP
78: The value of the number is pushed onto the main stack.
79: A number is an unbroken string of the digits 0-9
80: and the capital letters A\-F which are treated as digits
81: with values 10\-15 respectively.
82: The number may be preceded by an underscore \*_ to input a
83: negative number.
84: Numbers may contain decimal points.
85: .SH
86: + \- * % ^
87: .IP
88: The
89: top two values on the stack are added
90: (\fB+\fP),
91: subtracted
92: (\fB\-\fP),
93: multiplied (\fB*\fP),
94: divided (\fB/\fP),
95: remaindered (\fB%\fP),
96: or exponentiated (^).
97: The two entries are popped off the stack;
98: the result is pushed on the stack in their place.
99: The result of a division is an integer truncated toward zero.
100: See the detailed description below for the treatment of
101: numbers with decimal points.
102: An exponent must not have any digits after the decimal point.
103: .SH
104: s\fIx\fP
105: .IP
106: The
107: top of the main stack is popped and stored into
108: a register named \fIx\fP, where \fIx\fP may be any character.
109: If
110: the
111: .ft B
112: s
113: .ft
114: is capitalized,
115: .ft I
116: x
117: .ft
118: is treated as a stack and the value is pushed onto it.
119: Any character, even blank or new-line, is a valid register name.
120: .SH
121: l\fIx\fP
122: .IP
123: The
124: value in register
125: .ft I
126: x
127: .ft
128: is pushed onto the stack.
129: The register
130: .ft I
131: x
132: .ft
133: is not altered.
134: If the
135: .ft B
136: l
137: .ft
138: is capitalized,
139: register
140: .ft I
141: x
142: .ft
143: is treated as a stack and its top value is popped onto the main stack.
144: .LP
145: All registers start with empty value which is treated as a zero
146: by the command \fBl\fP and is treated as an error by the command \fBL\fP.
147: .SH
148: .SH
149: d
150: .IP
151: The
152: top value on the stack is duplicated.
153: .SH
154: p
155: .IP
156: The top value on the stack is printed.
157: The top value remains unchanged.
158: .SH
159: f
160: .IP
161: All values on the stack and in registers are printed.
162: .SH
163: x
164: .IP
165: treats the top element of the stack as a character string,
166: removes it from the stack, and
167: executes it as a string of DC commands.
168: .SH
169: [ ... ]
170: .IP
171: puts the bracketed character string onto the top of the stack.
172: .SH
173: q
174: .IP
175: exits the program.
176: If executing a string, the recursion level is
177: popped by two.
178: If
179: .ft B
180: q
181: .ft
182: is capitalized,
183: the top value on the stack is popped and the string execution level is popped
184: by that value.
185: .SH
186: <\fIx\fP >\fIx\fP =\fIx\fP !<\fIx\fP !>\fIx\fP !=\fIx\fP
187: .IP
188: The
189: top two elements of the stack are popped and compared.
190: Register
191: .ft I
192: x
193: .ft
194: is executed if they obey the stated
195: relation.
196: Exclamation point is negation.
197: .SH
198: v
199: .IP
200: replaces the top element on the stack by its square root.
201: The square root of an integer is truncated to an integer.
202: For the treatment of numbers with decimal points, see
203: the detailed description below.
204: .SH
205: !
206: .IP
207: interprets the rest of the line as a
208: .UX
209: command.
210: Control returns to DC when the
211: .UX
212: command terminates.
213: .SH
214: c
215: .IP
216: All values on the stack are popped; the stack becomes empty.
217: .SH
218: i
219: .IP
220: The top value on the stack is popped and used as the
221: number radix for further input.
222: If \fBi\fP is capitalized, the value of
223: the input base is pushed onto the stack.
224: No mechanism has been provided for the input of arbitrary
225: numbers in bases less than 1 or greater than 16.
226: .SH
227: o
228: .IP
229: The top value on the stack is popped and used as the
230: number radix for further output.
231: If \fBo\fP is capitalized, the value of the output
232: base is pushed onto the stack.
233: .SH
234: k
235: .IP
236: The top of the stack is popped, and that value is used as
237: a scale factor
238: that influences the number of decimal places
239: that are maintained during multiplication, division, and exponentiation.
240: The scale factor must be greater than or equal to zero and
241: less than 100.
242: If \fBk\fP is capitalized, the value of the scale factor
243: is pushed onto the stack.
244: .SH
245: z
246: .IP
247: The value of the stack level is pushed onto the stack.
248: .SH
249: ?
250: .IP
251: A line of input is taken from the input source (usually the console)
252: and executed.
253: .SH
254: DETAILED DESCRIPTION
255: .SH
256: Internal Representation of Numbers
257: .PP
258: Numbers are stored internally using a dynamic storage allocator.
259: Numbers are kept in the form of a string
260: of digits to the base 100 stored one digit per byte
261: (centennial digits).
262: The string is stored with the low-order digit at the
263: beginning of the string.
264: For example, the representation of 157
265: is 57,1.
266: After any arithmetic operation on a number, care is taken
267: that all digits are in the range 0\-99 and that
268: the number has no leading zeros.
269: The number zero is represented by the empty string.
270: .PP
271: Negative numbers are represented in the 100's complement
272: notation, which is analogous to two's complement notation for binary
273: numbers.
274: The high order digit of a negative number is always \-1
275: and all other digits are in the range 0\-99.
276: The digit preceding the high order \-1 digit is never a 99.
277: The representation of \-157 is 43,98,\-1.
278: We shall call this the canonical form of a number.
279: The advantage of this kind of representation of negative
280: numbers is ease of addition. When addition is performed digit
281: by digit, the result is formally correct. The result need only
282: be modified, if necessary, to put it into canonical form.
283: .PP
284: Because the largest valid digit is 99 and the byte can
285: hold numbers twice that large, addition can be carried out
286: and the handling of carries done later when
287: that is convenient, as it sometimes is.
288: .PP
289: An additional byte is stored with each number beyond
290: the high order digit to indicate the number of
291: assumed decimal digits after the decimal point. The representation
292: of .001 is 1,\fI3\fP
293: where the scale has been italicized to emphasize the fact that it
294: is not the high order digit.
295: The value of this extra byte is called the
296: .ft B
297: scale factor
298: .ft
299: of the number.
300: .SH
301: The Allocator
302: .PP
303: DC uses a dynamic string storage allocator
304: for all of its internal storage.
305: All reading and writing of numbers internally is done through
306: the allocator.
307: Associated with each string in the allocator is a four-word header containing pointers
308: to the beginning of the string, the end of the string,
309: the next place to write, and the next place to read.
310: Communication between the allocator and DC
311: is done via pointers to these headers.
312: .PP
313: The allocator initially has one large string on a list
314: of free strings. All headers except the one pointing
315: to this string are on a list of free headers.
316: Requests for strings are made by size.
317: The size of the string actually supplied is the next higher
318: power of 2.
319: When a request for a string is made, the allocator
320: first checks the free list to see if there is
321: a string of the desired size.
322: If none is found, the allocator finds the next larger free string and splits it repeatedly until
323: it has a string of the right size.
324: Left-over strings are put on the free list.
325: If there are no larger strings,
326: the allocator tries to coalesce smaller free strings into
327: larger ones.
328: Since all strings are the result
329: of splitting large strings,
330: each string has a neighbor that is next to it in core
331: and, if free, can be combined with it to make a string twice as long.
332: This is an implementation of the `buddy system' of allocation
333: described in [2].
334: .PP
335: Failing to find a string of the proper length after coalescing,
336: the allocator asks the system for more space.
337: The amount of space on the system is the only limitation
338: on the size and number of strings in DC.
339: If at any time in the process of trying to allocate a string, the allocator runs out of
340: headers, it also asks the system for more space.
341: .PP
342: There are routines in the allocator for reading, writing, copying, rewinding,
343: forward-spacing, and backspacing strings.
344: All string manipulation is done using these routines.
345: .PP
346: The reading and writing routines
347: increment the read pointer or write pointer so that
348: the characters of a string are read or written in
349: succession by a series of read or write calls.
350: The write pointer is interpreted as the end of the
351: information-containing portion of a string and a call
352: to read beyond that point returns an end-of-string indication.
353: An attempt to write beyond the end of a string
354: causes the allocator to
355: allocate a larger space and then copy
356: the old string into the larger block.
357: .SH
358: Internal Arithmetic
359: .PP
360: All arithmetic operations are done on integers.
361: The operands (or operand) needed for the operation are popped
362: from the main stack and their scale factors stripped off.
363: Zeros are added or digits removed as necessary to get
364: a properly scaled result from the internal arithmetic routine.
365: For example, if the scale of the operands is different and decimal
366: alignment is required, as it is for
367: addition, zeros are appended to the operand with the smaller
368: scale.
369: After performing the required arithmetic operation,
370: the proper scale factor is appended to the end of the number before
371: it is pushed on the stack.
372: .PP
373: A register called \fBscale\fP plays a part
374: in the results of most arithmetic operations.
375: \fBscale\fP is the bound on the number of decimal places retained in
376: arithmetic computations.
377: \fBscale\fP may be set to the number on the top of the stack
378: truncated to an integer with the \fBk\fP command.
379: \fBK\fP may be used to push the value of \fBscale\fP on the stack.
380: \fBscale\fP must be greater than or equal to 0 and less than 100.
381: The descriptions of the individual arithmetic operations will
382: include the exact effect of \fBscale\fP on the computations.
383: .SH
384: Addition and Subtraction
385: .PP
386: The scales of the two numbers are compared and trailing
387: zeros are supplied to the number with the lower scale to give both
388: numbers the same scale. The number with the smaller scale is
389: multiplied by 10 if the difference of the scales is odd.
390: The scale of the result is then set to the larger of the scales
391: of the two operands.
392: .PP
393: Subtraction is performed by negating the number
394: to be subtracted and proceeding as in addition.
395: .PP
396: Finally, the addition is performed digit by digit from the
397: low order end of the number. The carries are propagated
398: in the usual way.
399: The resulting number is brought into canonical form, which may
400: require stripping of leading zeros, or for negative numbers
401: replacing the high-order configuration 99,\-1 by the digit \-1.
402: In any case, digits which are not in the range 0\-99 must
403: be brought into that range, propagating any carries or borrows
404: that result.
405: .SH
406: Multiplication
407: .PP
408: The scales are removed from the two operands and saved.
409: The operands are both made positive.
410: Then multiplication is performed in
411: a digit by digit manner that exactly mimics the hand method
412: of multiplying.
413: The first number is multiplied by each digit of the second
414: number, beginning with its low order digit. The intermediate
415: products are accumulated into a partial sum which becomes the
416: final product.
417: The product is put into the canonical form and its sign is
418: computed from the signs of the original operands.
419: .PP
420: The scale of the result is set equal to the sum
421: of the scales of the two operands.
422: If that scale is larger than the internal register
423: .ft B
424: scale
425: .ft
426: and also larger than both of the scales of the two operands,
427: then the scale of the result is set equal to the largest
428: of these three last quantities.
429: .SH
430: Division
431: .PP
432: The scales are removed from the two operands.
433: Zeros are appended or digits removed from the dividend to make
434: the scale of the result of the integer division equal to
435: the internal quantity
436: \fBscale\fP.
437: The signs are removed and saved.
438: .PP
439: Division is performed much as it would be done by hand.
440: The difference of the lengths of the two numbers
441: is computed.
442: If the divisor is longer than the dividend,
443: zero is returned.
444: Otherwise the top digit of the divisor is divided into the top
445: two digits of the dividend.
446: The result is used as the first (high-order) digit of the
447: quotient.
448: It may turn out be one unit too low, but if it is, the next
449: trial quotient will be larger than 99 and this will be
450: adjusted at the end of the process.
451: The trial digit is multiplied by the divisor and the result subtracted
452: from the dividend and the process is repeated to get
453: additional quotient digits until the remaining
454: dividend is smaller than the divisor.
455: At the end, the digits of the quotient are put into
456: the canonical form, with propagation of carry as needed.
457: The sign is set from the sign of the operands.
458: .SH
459: Remainder
460: .PP
461: The division routine is called and division is performed
462: exactly as described. The quantity returned is the remains of the
463: dividend at the end of the divide process.
464: Since division truncates toward zero, remainders have the same
465: sign as the dividend.
466: The scale of the remainder is set to
467: the maximum of the scale of the dividend and
468: the scale of the quotient plus the scale of the divisor.
469: .SH
470: Square Root
471: .PP
472: The scale is stripped from the operand.
473: Zeros are added if necessary to make the
474: integer result have a scale that is the larger of
475: the internal quantity
476: \fBscale\fP
477: and the scale of the operand.
478: .PP
479: The method used to compute sqrt(y) is Newton's method
480: with successive approximations by the rule
481: .EQ
482: x sub {n+1} ~=~ half ( x sub n + y over x sub n )
483: .EN
484: The initial guess is found by taking the integer square root
485: of the top two digits.
486: .SH
487: Exponentiation
488: .PP
489: Only exponents with zero scale factor are handled. If the exponent is
490: zero, then the result is 1. If the exponent is negative, then
491: it is made positive and the base is divided into one. The scale
492: of the base is removed.
493: .PP
494: The integer exponent is viewed as a binary number.
495: The base is repeatedly squared and the result is
496: obtained as a product of those powers of the base that
497: correspond to the positions of the one-bits in the binary
498: representation of the exponent.
499: Enough digits of the result
500: are removed to make the scale of the result the same as if the
501: indicated multiplication had been performed.
502: .SH
503: Input Conversion and Base
504: .PP
505: Numbers are converted to the internal representation as they are read
506: in.
507: The scale stored with a number is simply the number of fractional digits input.
508: Negative numbers are indicated by preceding the number with a \fB\_\fP (an
509: underscore).
510: The hexadecimal digits A\-F correspond to the numbers 10\-15 regardless of input base.
511: The \fBi\fP command can be used to change the base of the input numbers.
512: This command pops the stack, truncates the resulting number to an integer,
513: and uses it as the input base for all further input.
514: The input base is initialized to 10 but may, for example be changed to
515: 8 or 16 to do octal or hexadecimal to decimal conversions.
516: The command \fBI\fP will push the value of the input base on the stack.
517: .SH
518: Output Commands
519: .PP
520: The command \fBp\fP causes the top of the stack to be printed.
521: It does not remove the top of the stack.
522: All of the stack and internal registers can be output
523: by typing the command \fBf\fP.
524: The \fBo\fP command can be used to change the output base.
525: This command uses the top of the stack, truncated to an integer as
526: the base for all further output.
527: The output base in initialized to 10.
528: It will work correctly for any base.
529: The command \fBO\fP pushes the value of the output base on the stack.
530: .SH
531: Output Format and Base
532: .PP
533: The input and output bases only affect
534: the interpretation of numbers on input and output; they have no
535: effect on arithmetic computations.
536: Large numbers are output with 70 characters per line;
537: a \\ indicates a continued line.
538: All choices of input and output bases work correctly, although not all are
539: useful.
540: A particularly useful output base is 100000, which has the effect of
541: grouping digits in fives.
542: Bases of 8 and 16 can be used for decimal-octal or decimal-hexadecimal
543: conversions.
544: .SH
545: Internal Registers
546: .PP
547: Numbers or strings may be stored in internal registers or loaded on the stack
548: from registers with the commands \fBs\fP and \fBl\fP.
549: The command \fBs\fIx\fR pops the top of the stack and
550: stores the result in register \fBx\fP.
551: \fIx\fP can be any character.
552: \fBl\fIx\fR puts the contents of register \fBx\fP on the top of the stack.
553: The \fBl\fP command has no effect on the contents of register \fIx\fP.
554: The \fBs\fP command, however, is destructive.
555: .SH
556: Stack Commands
557: .PP
558: The command \fBc\fP clears the stack.
559: The command \fBd\fP pushes a duplicate of the number on the top of the stack
560: on the stack.
561: The command \fBz\fP pushes the stack size on the stack.
562: The command \fBX\fP replaces the number on the top of the stack
563: with its scale factor.
564: The command \fBZ\fP replaces the top of the stack
565: with its length.
566: .SH
567: Subroutine Definitions and Calls
568: .PP
569: Enclosing a string in \fB[ ]\fP pushes the ascii string on the stack.
570: The \fBq\fP command quits or in executing a string, pops the recursion levels by two.
571: .SH
572: Internal Registers \- Programming DC
573: .PP
574: The load and store
575: commands together with \fB[ ]\fP to store strings, \fBx\fP to execute
576: and the testing commands `<', `>', `=', `!<', `!>', `!=' can be used to program
577: DC.
578: The \fBx\fP command assumes the top of the stack is an string of DC commands
579: and executes it.
580: The testing commands compare the top two elements on the stack and if the relation holds, execute the register
581: that follows the relation.
582: For example, to print the numbers 0-9,
583: .DS
584: [lip1+ si li10>a]sa
585: 0si lax
586: .DE
587: .SH
588: Push-Down Registers and Arrays
589: .PP
590: These commands were designed for used by a compiler, not by
591: people.
592: They involve push-down registers and arrays.
593: In addition to the stack that commands work on, DC can be thought
594: of as having individual stacks for each register.
595: These registers are operated on by the commands \fBS\fP and \fBL\fP.
596: \fBS\fIx\fR pushes the top value of the main stack onto the stack for
597: the register \fIx\fP.
598: \fBL\fIx\fR pops the stack for register \fIx\fP and puts the result on the main
599: stack.
600: The commands \fBs\fP and \fBl\fP also work on registers but not as push-down
601: stacks.
602: \fBl\fP doesn't effect the top of the
603: register stack, and \fBs\fP destroys what was there before.
604: .PP
605: The commands to work on arrays are \fB:\fP and \fB;\fP.
606: \fB:\fIx\fR pops the stack and uses this value as an index into
607: the array \fIx\fP.
608: The next element on the stack is stored at this index in \fIx\fP.
609: An index must be greater than or equal to 0 and
610: less than 2048.
611: \fB;\fIx\fR is the command to load the main stack from the array \fIx\fP.
612: The value on the top of the stack is the index
613: into the array \fIx\fP of the value to be loaded.
614: .SH
615: Miscellaneous Commands
616: .PP
617: The command \fB!\fP interprets the rest of the line as a
618: .UX
619: command and passes it to
620: .UX
621: to execute.
622: One other compiler command is \fBQ\fP.
623: This command uses the top of the stack as the number of levels of recursion to skip.
624: .SH
625: DESIGN CHOICES
626: .PP
627: The real reason for the use of a dynamic storage allocator was
628: that a general purpose program could be (and in fact has been)
629: used for a variety of other tasks.
630: The allocator has some value for input and for compiling (i.e.
631: the bracket [...] commands) where it cannot be known in advance
632: how long a string will be.
633: The result was that at a modest
634: cost in execution time, all considerations of string allocation
635: and sizes of strings were removed from the remainder of the program
636: and debugging was made easier. The allocation method
637: used wastes approximately 25% of available space.
638: .PP
639: The choice of 100 as a base for internal arithmetic
640: seemingly has no compelling advantage. Yet the base cannot
641: exceed 127 because of hardware limitations and at the cost
642: of 5% in space, debugging was made a great deal easier and
643: decimal output was made much faster.
644: .PP
645: The reason for a stack-type arithmetic design was
646: to permit all DC commands from addition to subroutine execution
647: to be implemented in essentially the same way. The result
648: was a considerable degree of logical separation of the final
649: program into modules with very little communication between
650: modules.
651: .PP
652: The rationale for the lack of interaction between the scale and the bases
653: was to provide an understandable means of proceeding after
654: a change of base or scale when numbers had already been entered.
655: An earlier implementation which had global notions of
656: scale and base did not work out well.
657: If the value of
658: .ft B
659: scale
660: .ft
661: were to be interpreted in the current
662: input or output base,
663: then a change of base or scale in the midst of a
664: computation would cause great confusion in the interpretation
665: of the results.
666: The current scheme has the advantage that the value of
667: the input and output bases
668: are only used for input and output, respectively, and they
669: are ignored in all other operations.
670: The value of
671: scale
672: is not used for any essential purpose by any part of the program
673: and it is used only to prevent the number of
674: decimal places resulting from the arithmetic operations from
675: growing beyond all bounds.
676: .PP
677: The design rationale for the choices for the scales of
678: the results of arithmetic were that in no case should
679: any significant digits be thrown away if, on appearances, the
680: user actually wanted them. Thus, if the user wants
681: to add the numbers 1.5 and 3.517, it seemed reasonable to give
682: him the result 5.017 without requiring him to unnecessarily
683: specify his rather obvious requirements for precision.
684: .PP
685: On the other hand, multiplication and exponentiation produce
686: results with many more digits than their operands and it
687: seemed reasonable to give as a minimum the number of decimal
688: places in the operands but not to give more than that
689: number of digits
690: unless the user asked for them by specifying a value for \fBscale\fP.
691: Square root can be handled in just the same way as multiplication.
692: The operation of division gives arbitrarily many decimal places
693: and there is simply no way to guess how many places the user
694: wants.
695: In this case only, the user must
696: specify a \fBscale\fP to get any decimal places at all.
697: .PP
698: The scale of remainder was chosen to make it possible
699: to recreate the dividend from the quotient and remainder.
700: This is easy to implement; no digits are thrown away.
701: .SH
702: References
703: .IP [1]
704: L. L. Cherry, R. Morris,
705: .ft I
706: BC \- An Arbitrary Precision Desk-Calculator Language.
707: .ft
708: .IP [2]
709: K. C. Knowlton,
710: .ft I
711: A Fast Storage Allocator,
712: .ft
713: Comm. ACM \fB8\fP, pp. 623-625 (Oct. 1965).
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.