BC - An Arbitrary Precision Desk-Calculator Language

ABSTRACT

BC is a language and a compiler for doing arbitrary precision arithmetic on the PDP-11 under the UNIXtime-sharing system. The output of the compiler is interpreted and executed by a collection of routines which can input, output, and do arithmetic on indefinitely large integers and on scaled fixed-point numbers.

      These routines are themselves based on a dynamic storage allocator. Overflow does not occur until all available core storage is exhausted.

      The language has a complete control structure as well as immediate-mode operation. Functions can be defined and saved for later execution.

      Two five hundred-digit numbers can be multiplied to give a thousand digit result in about ten seconds.

      A small collection of library functions is also available, including sin, cos, arctan, log, exponential, and Bessel functions of integer order.

      Some of the uses of this compiler are

• to do computation with large integers,
• to do computation accurate to many decimal places,
• conversion of numbers from one base to another base.

Introduction

      BC is a language and a compiler for doing arbitrary precision arithmetic on the UNIXtime-sharing system [1]. The compiler was written to make conveniently available a collection of routines (called DC [5]) which are capable of doing arithmetic on integers of arbitrary size. The compiler is by no means intended to provide a complete programming language. It is a minimal language facility.

      There is a scaling provision that permits the use of decimal point notation. Provision is made for input and output in bases other than decimal. Numbers can be converted from decimal to octal by simply setting the output base to equal 8.

      The actual limit on the number of digits that can be handled depends on the amount of storage available on the machine. Manipulation of numbers with many hundreds of digits is possible even on the smallest versions of UNIX

      The syntax of BC has been deliberately selected to agree substantially with the C language [2]. Those who are familiar with C will find few surprises in this language.

Simple Computations with Integers

      The simplest kind of statement is an arithmetic expression on a line by itself. For instance, if you type in the line:

142857 + 285714

428571

      Any term in an expression may be prefixed by a minus sign to indicate that it is to be negated (the `unary' minus sign). The expression

7+-3

      More complex expressions with several operators and with parentheses are interpreted just as in Fortran, with ^ having the greatest binding power, then * and % and /, and finally + and -. Contents of parentheses are evaluated before material outside the parentheses. Exponentiations are performed from right to left and the other operators from left to right. The two expressions

a^b^c and a^(b^c)

a*b*c and (a*b)*c

a/b*c is equivalent to (a/b)*c

      Internal storage registers to hold numbers have single lower-case letter names. The value of an expression can be assigned to a register in the usual way. The statement

x = x + 3

      There is a built-in square root function whose result is truncated to an integer (but see scaling below). The lines

x = sqrt(191)
x

13

Bases

      There are special internal quantities, called `ibase' and `obase'. The contents of `ibase', initially set to 10, determines the base used for interpreting numbers read in. For example, the lines

ibase = 8
11

9

ibase = 10

ibase = A

      The contents of `obase', initially set to 10, are used as the base for output numbers. The lines

obase = 16
1000

3E8

      Very large numbers are split across lines with 70 characters per line. Lines which are continued end with \. Decimal output conversion is practically instantaneous, but output of very large numbers (i.e., more than 100 digits) with other bases is rather slow. Non-decimal output conversion of a one hundred digit number takes about three seconds.

      It is best to remember that `ibase' and `obase' have no effect whatever on the course of internal computation or on the evaluation of expressions, but only affect input and output conversion, respectively.

Scaling

      A third special internal quantity called `scale' is used to determine the scale of calculated quantities. Numbers may have up to 99 decimal digits after the decimal point. This fractional part is retained in further computations. We refer to the number of digits after the decimal point of a number as its scale.

      When two scaled numbers are combined by means of one of the arithmetic operations, the result has a scale determined by the following rules. For addition and subtraction, the scale of the result is the larger of the scales of the two operands. In this case, there is never any truncation of the result. For multiplications, the scale of the result is never less than the maximum of the two scales of the operands, never more than the sum of the scales of the operands and, subject to those two restrictions, the scale of the result is set equal to the contents of the internal quantity `scale'. The scale of a quotient is the contents of the internal quantity `scale'. The scale of a remainder is the sum of the scales of the quotient and the divisor. The result of an exponentiation is scaled as if the implied multiplications were performed. An exponent must be an integer. The scale of a square root is set to the maximum of the scale of the argument and the contents of `scale'.

      All of the internal operations are actually carried out in terms of integers, with digits being discarded when necessary. In every case where digits are discarded, truncation and not rounding is performed.

      The contents of `scale' must be no greater than 99 and no less than 0. It is initially set to 0. In case you need more than 99 fraction digits, you may arrange your own scaling.

      The internal quantities `scale', `ibase', and `obase' can be used in expressions just like other variables. The line

scale = scale + 1

scale

      The value of `scale' retains its meaning as a number of decimal digits to be retained in internal computation even when `ibase' or `obase' are not equal to 10. The internal computations (which are still conducted in decimal, regardless of the bases) are performed to the specified number of decimal digits, never hexadecimal or octal or any other kind of digits.

Functions

      The name of a function is a single lower-case letter. Function names are permitted to collide with simple variable names. Twenty-six different defined functions are permitted in addition to the twenty-six variable names. The line

define a(x){

return
return(x)

      Variables used in the function can be declared as automatic by a statement of the form

auto x,y,z

define a(x,y){
auto z
z = x*y
return(z)
}

      A function is called by the appearance of its name followed by a string of arguments enclosed in parentheses and separated by commas. The result is unpredictable if the wrong number of arguments is used.

      Functions with no arguments are defined and called using parentheses with nothing between them: b().

      If the function a above has been defined, then the line

a(7,3.14)

x = a(a(3,4),5)

Subscripted Variables

      A single lower-case letter variable name followed by an expression in brackets is called a subscripted variable (an array element). The variable name is called the array name and the expression in brackets is called the subscript. Only one-dimensional arrays are permitted. The names of arrays are permitted to collide with the names of simple variables and function names. Any fractional part of a subscript is discarded before use. Subscripts must be greater than or equal to zero and less than or equal to 2047.

      Subscripted variables may be freely used in expressions, in function calls, and in return statements.

      An array name may be used as an argument to a function, or may be declared as automatic in a function definition by the use of empty brackets:

f(a[])
define f(a[])
auto a[]

Control Statements

      The `if', the `while', and the `for' statements may be used to alter the flow within programs or to cause iteration. The range of each of them is a statement or a compound statement consisting of a collection of statements enclosed in braces. They are written in the following way

if(relation) statement
while(relation) statement
for(expression1; relation; expression2) statement

if(relation) {statements}
while(relation) {statements}
for(expression1; relation; expression2) {statements}

      A relation in one of the control statements is an expression of the form

x>y

      BEWARE of using = instead of == in a relational. Unfortunately, both of them are legal, so you will not get a diagnostic message, but = really will not do a comparison.

      The `if' statement causes execution of its range if and only if the relation is true. Then control passes to the next statement in sequence.

      The `while' statement causes execution of its range repeatedly as long as the relation is true. The relation is tested before each execution of its range and if the relation is false, control passes to the next statement beyond the range of the while.

      The `for' statement begins by executing `expression1'. Then the relation is tested and, if true, the statements in the range of the `for' are executed. Then `expression2' is executed. The relation is tested, and so on. The typical use of the `for' statement is for a controlled iteration, as in the statement

for(i=1; i<=10; i=i+1) i

define f(n){
auto i, x
x=1
for(i=1; i<=n; i=i+1) x=x*i
return(x)
}

f(a)

define b(n,m){
auto x, j
x=1
for(j=1; j<=m; j=j+1) x=x*(n-j+1)/j
return(x)
}

scale = 20
define e(x){
auto a, b, c, d, n
a = 1
b = 1
c = 1
d = 0
n = 1
while(1==1){
a = a*x
b = b*n
c = c + a/b
n = n + 1
if(c==d) return(c)
d = c
}
}

Some Details

      There are some language features that every user should know about even if he will not use them.

      Normally statements are typed one to a line. It is also permissible to type several statements on a line separated by semicolons.

      If an assignment statement is parenthesized, it then has a value and it can be used anywhere that an expression can. For example, the line

(x=y+17)

      Here is an example of a use of the value of an assignment statement even when it is not parenthesized.

x = a[i=i+1]

      The following constructs work in BC in exactly the same manner as they do in the C language. Consult the appendix or the C manuals [2] for their exact workings.

x=y=z is the same as x=(y=z)
x =+ y x = x+y
x =- y x = x-y
x =* y x = x*y
x =/ y x = x/y
x =% y x = x%y
x =^ y x = x^y
x++ (x=x+1)-1
x-- (x=x-1)+1
++x x = x+1
--x x = x-1

      WARNING! In some of these constructions, spaces are significant. There is a real difference between x=-y and x= -y. The first replaces x by x-y and the second by -y.

Three Important Things

      1. To exit a BC program, type `quit'.

      2. There is a comment convention identical to that of C and of PL/I. Comments begin with `/*' and end with `*/'.

      3. There is a library of math functions which may be obtained by typing at command level

bc -l

      If you type

bc file ...

Acknowledgement

      The compiler is written in YACC [4]; its original version was written by S. C. Johnson.

References

[1]

K. Thompson and D. M. Ritchie, UNIX Programmer's Manual, Bell Laboratories, 1978.

[2]

B. W. Kernighan and D. M. Ritchie, The C Programming Language, Prentice-Hall, 1978.

[3]

R. Morris, A Library of Reference Standard Mathematical Subroutines, Bell Laboratories internal memorandum, 1975.

[4]

S. C. Johnson, YACC -- Yet Another Compiler-Compiler. Bell Laboratories Computing Science Technical Report #32, 1978.

[5]

R. Morris and L. L. Cherry, DC - An Interactive Desk Calculator.

Table of Contents

• 1. Notation
• 2. Tokens
  • 2.1. Comments
  • 2.2. Identifiers
  • 2.3. Keywords
  • 2.4. Constants
• 3. Expressions
  • 3.1. Primitive expressions
    • 3.1.1. Named expressions
      • 3.1.1.1. identifiers
      • 3.1.1.2. array-name[expression]
      • 3.1.1.3. scale, ibase and obase
    • 3.1.2. Function calls
      • 3.1.2.1. function-name([expression[,expression...]])
      • 3.1.2.2. sqrt(expression)
      • 3.1.2.3. length(expression)
      • 3.1.2.4. scale(expression)
    • 3.1.3. Constants
    • 3.1.4. Parentheses
  • 3.2. Unary operators
    • 3.2.1. -expression
    • 3.2.2. ++named-expression
    • 3.2.3. --named-expression
    • 3.2.4. named-expression++
    • 3.2.5. named-expression--
  • 3.3. Exponentiation operator
    • 3.3.1. expression ^ expression
  • 3.4. Multiplicative operators
    • 3.4.1. expression * expression
    • 3.4.2. expression / expression
    • 3.4.3. expression % expression
  • 3.5. Additive operators
    • 3.5.1. expression + expression
    • 3.5.2. expression - expression
  • 3.6. assignment operators
    • 3.6.1. named-expression = expression
    • 3.6.2. named-expression =+ expression
    • 3.6.3. named-expression =- expression
    • 3.6.4. named-expression =* expression
    • 3.6.5. named-expression =/ expression
    • 3.6.6. named-expression =% expression
    • 3.6.7. named-expression =^ expression
• 4. Relations
  • 4.1. expression < expression
  • 4.2. expression > expression
  • 4.3. expression <= expression
  • 4.4. expression >= expression
  • 4.5. expression == expression
  • 4.6. expression != expression
• 5. Storage classes
• 6. Statements
  • 6.1. Expression statements
  • 6.2. Compound statements
  • 6.3. Quoted string statements
  • 6.4. If statements
    if(relation)statement
  • 6.5. While statements
    while(relation)statement
  • 6.6. For statements
    for(expression; relation; expression)statement
  • 6.7. Break statements
    break
  • 6.8. Auto statements
    auto identifier[,identifier]
  • 6.9. Define statements
    define([parameter[,parameter...]]){
    statements}
    
  • 6.10. Return statements
    return
    return(expression)
  • 6.11. Quit