The phrase "unbounded precision" means that the program providing the calculation itself places no limitation on the number of digits in a value. There are limitations to the storage capacity of any computing system; but they are generally very large relative to values that are likely to be used, and the program simply ignores that bound.

The basic response of the program is designed to deal with entry sequences such as: 24 + 9 =, which results in a display of 33 and the retention of that value in an accumulator (represented by the variable *AC*). A string of digits that designates a number is terminated by an operator, and so it is (value,operator)-pairs that are accepted by the program. Although an operator terminates the entry of a number, it is the *previous* operator that usually determines the action. (Operators such as ''C" and ''Q'' are exceptions.) In more detail, if the entering value is *X* and the result of arithmetic is held in *AC*, the action of this sequence can be traced as shown in Table D.1.

EntriesX NewOp Op AC

--------------------------

C 0

24+ 24 + C 24

9= 9 = + 33

- 24 + 9 =

- 24 + 9 +

24 + +

24 + + =

24 + + + =

The command-shell program that results is:

programUnBound

Preface

DoneFALSE

Op'C'

repeat

ValueIn(X,NoX,NextOp)

ifNextOp= 'Q'

thenDoneTRUE

else ifNextOp= 'C'

thenClear(AC)

Clear(X)

Op'C'

endif

ifNoXthenXACendif

case ofOp

'=', 'C':Swap{ACwithX

'+':Add(AC,X)

{'-', '*', '/'are similar to'+'}

endcase

endif

OpNextOp

Display

untilDone

end{UnBound

The next level of detail is dependent on the implementation of values, and that implementation must allow assignments *X ** AC* and *AC ** X* for unbounded strings of digits. Values need to carry a sign, have leading zeroes suppressed for the sake of efficiency and display, be compared in magnitude (left-to-right for corresponding digits), and be used right-to-left in arithmetic operations. The chosen implementation for *AC* and *X* is a pointer to a header of a doubly linked list. Such a list plays the role of a *register*--a storage location directly associated with computation. For reasons that only become apparent when operations are examined in detail, it is convenient to carry one leading zero and link it to itself. When AC 743, the resulting register structure is shown in Figure D.1.

A header such as *AC* or *X* can then be initialized by:

procedureNewRegister(R)

NEW(d)

d.Leftd

d.Value0

d.RightNIL

NEW(R)

R.Firstd

R.Lastd

R.SignTRUE

R.Count0

end{NewRegister

Setting an initialized register back to zero can be even simpler:

procedureClear(R)

R.LastR.First

R.Count0

R.SignTRUE

end{Clear

procedureClear(R)

pR.Last

qp.Left

whilepR.Firstdo

DISPOSE(p)

pq

qp.Left

endwhile

p.RightNIL

R.Lastp

R.Count0

R.SignTRUE

end{Clear

procedureCompact(R)

pR.First

qp.Right

whileqNILdo

ifq.Value0

thenexit

elsetq.Right

DISPOSE(q)

R.CountR.Count - 1

P.Rightt

qt

iftNIL

thent.Leftpendif

endif

endwhile

ifR.Count = 0thenR.LastR.Firstendif

end{Compact

(qNIL) AND (q.Value0)

is risky. A more direct translation results from the use of GOTO to implement **exit**.

On the principle of "never trust the user," compaction is included as the last action in *ValueIn*.

The input-token generator *ValueIn* is:

procedureValueIn(X,NoX,NextOp)

NoXTRUE

Clear(X)

Read(ch)

whileNOT (chINOperatorSet)do

ifch IN[0..9]

thenNoXFALSE

NEW(d)

d.RightNIL

d.ValueORD(ch) - ORD('0')

d.LeftX.Last

X.Last.Rightd

X.Lastd

X.CountX.Count+1

endif

Read(ch)

endwhile

NextOpch

Compact(X)

end{ValueIn

**1.** Compare *AC* and *X* and switch them if necessary to insure that *AC* *X*.

procedureAdd(X)

RLargerOf(AC,X)

ifR=X

thenXAC

ACR

endif

ifX.Count=0then return endif

ifAC.Sign=X.Sign

thenCarry(AC,X)

elseBorrow(AC,X)

endif

end{Add

functionLargerOf(AC,X) {O(n)Assumes compacted operands

ifAC.Count>X.Countthen returnACendif

ifX.Count>AC.Countthen returnXendif

kAC.Count

pACAC.First.Right

pXX.First.Right

whilek>0do

ifpAC.Value>pX.Valuethen returnACendif

ifpAC.Value<pX.Valuethen returnXendif

pACpAC.Right

pXpX.Right

kk-1

endwhile

returnAC{X = AC

end{LargerOf

procedureCarry(X)

pACAC.Last

pXX.Last

Over0

fork=1toAC.Countdo

SumpAC.Value+pX.Value+Over

ifSum>9

thenOver1

pAC.ValueSum-10

elseOver0

pAC.ValueSum

endif

pACpAC.Left

pXpX.Left

nextk

ifOver> 0

thenNEW(d)

d.RightpAC.Right

d.LeftpAC

pAC.Right.Leftd

pAC.Rightd

d.ValueOver

AC.CountAC.Count+1

endif

end{Carry

procedureBorrow

pACAC.Last

pXX.Last

Loan0

fork=1toAC.Countdo

DifferencepAC.Value-pX.Value-Loan

ifDifference<0

thenLoan1

pAC.ValueDifference+10

elseLoan 0

pAC.ValueDifference

endif

pACpAC.Left

pXpX.Left

nextk

Compact(AC)

end{Borrow

With *Add* complete, subtraction becomes very simple:

procedureSubtract(X)

X.SignNOTX.Sign

Add(X)

end{Subtract

procedureSetUp

YAC

NewRegister(AC)

New Register(M)

RLargerOf(Y,X)

ifR = X

thenXY

YR

endif

NewSign(Y.Sign = X.Sign)

X.SignTRUE

Y.SignTRUE

Clear(AC)

end{SetUp

A routine is needed to shift successive products one digit to the left. One approach is to shift *Y:*

procedureShiftLeft(Y)

NEW(d)

d.ValueO

d.RightNIL

d.LeftY.Last

Y.CountY.Count + 1

Y.Last.Rightd

Y.Lastd

end{ShiftLeft

Multiplication then can be done with:

procedureMultiply(X)

SetUp

ifX.Count=0then return endif

pXX.Last

forj=1toX.Countdo

Over0

MakeCopy(M,Y)

pMM.Last

pXX.Last

vpX.Value

fork=1toM.Countdo

ProductpM.Value*v+Over

pM.ValueProductMOD10

OverProductDIV10

pMpM.Left

nextk

ifOver>0

thenNEW(d)

d.RightpM.Right

d.LeftpM

pM.Right.Leftd

pM.Rightd

M.CountM.Count+1

d.ValueOver

endif

Add(AC,M)

ShiftLeft(Y)

pXpX.Left

nextj

AC.SignNewSign

Clear(Y)

Clear(M)

end{Multiply

procedureProlog

NewSign(AC.Sign=X.Sign)

AC.SignTRUE

X.SignTRUE

DAC

NewRegister(AC)

NewRegister(R)

NewRegister(S)

end{Prolog

The resulting divide logic is:

procedureDivide(X)

ifX.Count=0

thenClear(AC)

return

endif

Prolog

MakeCopy(S,X)

MakeCopy(AC,One)

RLargerOf(D,S)

whileR = Ddo

Carry(AC,One)

Carry(S,X)

RLargerOf(D,S)

endwhile

Borrow(AC,One)

AC.SignNewSign

Clear(D)

Clear(S)

end{Divide

A listing of a Pascal program that results from this design follows:

PROGRAM UnBound (InPut,OutPut);

TYPE Digit = DigitNode;

Register = RegisterNode;

DigitNode = RECORD

Value : 0 . . 9;

Left : Digit;

Right : Digit

END;

RegisterNode = RECORD

Sign : BOOLEAN;

Count : INTEGER;

First : Digit;

Last : Digit

END;

VAR Op ,NextOP : CHAR;

NoX,Done : BOOLEAN;

One,X,AC : Register;

OperatorSet : SET OF CHAR;

Numeric : SET OF CHAR;

{ }

PROCEDURE Display (AC : Register);

VAR pAC : Digit;

k : INTEGER;

BEGIN

Write1n;

pAC := AC .First;

IF NOT (AC . Sign) THEN Write('-');

FOR k := 1 TO (AC . Count + 1) DO BEGIN

Write(pAC .Value);

pAC := pAC . Right

END;

Write1n

END {Display};

{ }

PROCEDURE NewRegister(VAR R : Register);

VAR d : Digit;

BEGIN

NEW(d);

d .Left := d;

d .Value := 0;

d .Right := NIL;

NEW(R);

R .First := d;

R .Last := d;

R .Sign := TRUE;

R .Count := 0

END {NewRegister};

{ }

PROCEDURE Clear (VAR R : Register);

VAR p , q : Digit;

BEGIN

p := R .Last;

q := P .Left;

WHILE (p <> R .First) DO BEGIN

DISPOSE(p);

p := q;

q := p .Left

END;

R .Last := p;

R .Count := 0;

P .Right := NIL;

R .Sign := TRUE

END {Clear};

{ }

PROCEDURE MakeOne(VAR One : Register);

VAR d : Digit;

BEGIN

NewRegister(One);

NEW(d);

d .Value := 1;

d .Left := One .First;

d .Right := NIL;

One .First .Right := d;

One .Last := d;

One .Count := 1

END {MakeOne};

{ }

PROCEDURE Preface;

BEGIN

Write1n('This program simulates a calculator that');

Write1n('allows unbounded integers. Enter values');

Write1n('followed by operators. The accepted operators');

Write1n('are: +,-,*,/,=,C (for clear),Q (for quit).');

NewRegister(AC);

NewRegister(X);

MakeOne(One);

Numeric := ['0'..'9'];

OperatorSet := ['+','-','*','/','=','C','Q']

END {Preface};

{ }

PROCEDURE Compact(VAR R : Register);

VAR p, q, t : Digit;

BEGIN

p := R .First;

q := p .Right;

IF (q <> NIL) THEN IF (q .Value <> 0) THEN q:= NIL;

WHILE (q <> NIL) DO BEGIN

t := q .Right;

DISPOSE(q);

R .Count := R .Count - 1;

P .Right := t;

q := t;

IF (t <> NIL)

THEN BEGIN

t .Left := p;

IF (t .Value <> 0) THEN q := NIL

END

END;

IF (R .Count = 0) THEN R .Last := R .First

END {Compact};

{ }

PROCEDURE ValueIn(VAR X : Register; VAR NoX : BOOLEAN;

VAR NextOP : CHAR);

VAR ch : CHAR;

d : Digit;

BEGIN

NoX := TRUE;

Clear(X);

Read(ch);

WHILE NOT (ch IN OperatorSet)

DO BEGIN

IF (ch IN Numeric)

THEN BEGIN

NoX := FALSE;

NEW(d);

d .Right := NIL;

d .Value := ORD(ch) - ORD('0');

d .Left := X .Last;

X .Last .Right := d;

X .Last := d;

X .Count := X .Count + 1

END;

Read(ch)

END;

NextOp := ch;

Compact(X)

END {ValueIn};

{ }

FUNCTION LargerOf(AC,X : Register) : Register;

VAR K : INTEGER;

pAC,pX : Digit;

BEGIN

LargerOf := AC;

IF (AC .Count <= X .Count) THEN

IF (AC .Count < X .Count)

THEN LargerOf := X

ELSE BEGIN

k := AC .Count;

pAC := AC .First .Right;

pX := X .First .Right;

WHILE (k > 0) DO

IF (pAC .Value < = pX .Value)

THEN IF (pAC .Value < pX .Value)

THEN BEGIN

LargerOf := X;

K := O

END

ELSE BEGIN

pAC := pAC .Right;

pX := pX .Right;

k := k - 1

END

ELSE k := O

END;

END {LargerOf};

{ }

PROCEDURE MakeCopy(VAR M : Register; Y : Register);

VAR d,pY : Digit;

k : INTEGER;

BEGIN

Clear(M);

IF (Y .Count > 0) THEN BEGIN

pY := Y .First .Right;

FOR k := 1 TO Y .Count DO BEGIN

NEW(d);

d .Right := NIL;

d .Value := PY .Value;

pY := pY .Right;

d .Left := M .Last;

M .Last .Right := d;

M .Last := d

END;

M .Count := Y .Count;

END

END {MakeCopy};

{ }

PROCEDURE Carry(VAR AC : Register; X : Register);

VAR pAC, pX, d : Digit;

k,Sum, Over : INTEGER;

BEGIN

pAC := AC .Last;

pX := X .Last;

Over := 0;

FOR K := 1 TO AC .Count DO BEGIN

Sum := pAC .Value + pX .Value + Over;

IF (Sum > 9)

THEN BEGIN

Over := 1;

pAC .Value := Sum - 10

END

ELSE BEGIN

Over := 0;

pAC .Value := Sum

END;

pAC := pAC .Left;

pX := pX .Left

END;

IF (Over > 0)

THEN BEGIN

NEW(d);

d .Right := pAC .Right;

d .Left := pAC;

pAC .Right .Left := d;

pAC .Right := d;

d .Value := Over;

AC .Count := AC .Count + 1

END

END {Carry};

{ }

PROCEDURE Borrow(VAR AC: Register; X: Register);

VAR pAC,pX: Digit;

k,Loan,Difference: INTEGER;

BEGIN

pAC := AC .Last;

pX := X .Last;

Loan := 0;

FOR k := 1 TO AC .Count DO BEGIN

Difference := pAC .Value - pX .Value - Loan;

IF (Difference < 0)

THEN BEGIN

Loan := 1;

pAC .Value := Difference + 10

END

ELSE BEGIN

Loan := 0;

pAC .Value := Difference

END;

pAC := pAC .Left;

pX := pX .Left

END;

Compact(AC)

END {Borrow};

{ }

PROCEDURE Add(VAR AC: Register; VAR X : Register);

VAR R: Register;

BEGIN {X is VAR as AC may swap with it.}

R := LargerOf(AC,X);

IF (R = X)

THEN BEGIN

X := AC;

AC := R

END;

IF (X .Count <>0)

THEN IF (AC .Sign = X .Sign)

THEN Carry(AC,X)

ELSE Borrow(AC,X)

END {Add};

{ }

PROCEDURE Subtract(VAR AC: Register; VAR X: Register);

BEGIN

X .Sign := NOT X .Sign;

Add(AC,X)

END {Subtract};

{ }

PROCEDURE Multiply (VAR AC: Register; VAR X: Register);

VAR pM,pX,d: Digit;

M,Y : Register;

v,k,j,Over,Product: INTEGER;

NewSign: BOOLEAN;

{ }

PROCEDURE SetUp;

VAR R: Register;

BEGIN

Y := AC;

NewRegister(AC);

NewRegister(M);

R := LargerOf( Y,X);

IF (R = X)

THEN BEGIN

X := Y;

Y := R

END;

NewSign := (Y .Sign = X .Sign);

X .Sign := TRUE;

Y .Sign := TRUE;

Clear(AC)

END {SetUp};

{ }

PROCEDURE ShiftLeft(VAR Y: Register);

VAR d: Digit;

BEGIN

NEW (d);

d .Value := 0;

d .Right := NIL;

d .Left := Y .Last;

Y .Count := Y .Count + 1;

Y .Last .Right := d;

Y .Last := d

END {ShiftLeft};

{ }

BEGIN {Multiply}

SetUp;

IF (X .Count <> 0)

THEN BEGIN

pX := X .Last;

FOR j := 1 TO X .Count DO BEGIN

Over := 0;

MakeCopy(M,Y);

pM := M .Last;

v := pX .Value;

FOR k := 1 TO M .Count DO BEGIN

Product:=pM .Value* v + Over;

pM .Value := Product MOD 10;

Over := Product DIV 10;

pM := pM .Left

END;

IF (Over > 0)

THEN BEGIN

NEW (d);

d .Right := pM .Right;

d .Left := pM;

pM .Right .Left := d;

pM .Right := d;

M .Count := M .Count + 1;

d .Value := Over

END;

Add(AC,M);

ShiftLeft(Y);

pX := pX .Left

END;

AC .Sign := NewSign;

Clear(Y);

Clear(M)

END

END {Multiply};

{ }

PROCEDURE Divide(VAR AC: Register; VAR X: Register);

VAR NewSign: BOOLEAN;

D,R,S : Register;

{ }

PROCEDURE Prolog;

BEGIN

NewSign := (AC .Sign = X .Sign);

AC .Sign := TRUE;

X .Sign := TRUE;

D := AC;

NewRegister(AC);

NewRegister(R);

NewRegister(S)

END {Prolog};

{ }

BEGIN {Divide}

IF (X .Count = 0)

THEN Clear(AC)

ELSE BEGIN

Prolog;

MakeCopy(S,X);

MakeCopy(AC,One);

R := LargerOf(D,S);

WHILE (R = D) DO BEGIN

Carry(AC,One);

Carry(S,X);

R := LargerOf(D,S)

END;

Borrow(AC,One);

AC .Sign := NewSign;

Clear(D); Clear(S)

END

END {Divide};

{ }

PROCEDURE Swap;

VAR R: Register;

BEGIN

R := AC;

AC := X;

X := R

END {Swap};

{**

**}

BEGIN {UnBound}

Preface;

Done := FALSE;

Op := 'C';

REPEAT

ValueIn(X,NoX,NextOp);

IF (NextOp = 'Q')

THEN Done = TRUE

ELSE BEGIN

IF (NextOp = 'C')

THEN BEGIN

Clear(X); Clear(AC);

Op :='C'

END;

IF NoX THEN MakeCopy(X,AC);

CASE Op OF

'C' : Swap; {AC with X}

'=' : Swap;

'+' : Add(AC,X);

'-' : Subtract(AC,X);

'*' : Multiply(AC,X);

'/' : Divide(AC,X)

END

END;

Op := NextOp;

Display(AC)

UNTIL Done

END {UnBound}.