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