CALCULATOR

The following program acts as a calculator, with the ability to add, multiply, and divide. The unusual feature provided by the program is that it will calculate to an unlimited accuracy, restricted only by the amount of memory available to the program.

The program uses reverse Polish notation, also known as Polish suffix notation, in which the operator follows the operand or operands. This notation is used on some scientific calculators because it allows any expression to be entered without the need for brackets.
An expression in reverse Polish notation is:

1 2 + 4 5 + *

To understand how this is evaluated, imagine the expression read from left to right. When an operator, such as '+' and '*’, is encountered it removes the two numbers to its left, performs the operation, and replaces them with the result. Successive stages in the evaluation of this equation are:

1 2 + 4 5 + *
    3 4 5 + *
    3     9 *
           27

The equivalent expression in algebraic notation is (1+2)*(4+5). The great advantage of this notation is that the order of evaluation is unambiguous, and no brackets are needed to indicate how the expression is to be evaluated. Some other equations in algebraic form are shown below together with their equivalents in reverse Polish:

Algebraic:      Reverse Polish:
2 + 3 + 4       2 3 + 4 +
             or 2 3 4 + + 
3 * (4 + 5)     3 4 5 + *
(3 * 4) + 5     3 4 * 5 +

The above example would be entered into the calculator program as shown below. The '?' is the prompt, and after each number or operator is entered RETURN should be typed. The program prints out the result after each operation:

?1 
?2
?+
= 3
?4 
?5
?+
= 9
= 27

Sample run

In the following example using larger numbers the calculator works out 10000000001/99009901:

?10000000001 ?99009901
= 101

A number can be squared, by duplicating it on the stack with " and then multiplying:

?111111111111
?"
= 111111111111
?*
= 12345679012320987654321

Finally, we divide the result by the square of 111111:

?111111
p"
= 111111
p*
= 12345654321
?/
= 1000002000001

These results are all exact, and could not of course be obtained with a conventional calculator.

Program Operation

In these programs the long numbers are represented as strings of ASCII characters. The arithmetic routines to multiply, divide, and add, take two strings and generate a result in the form of a third string. This representation was chosen so that the standard BASIC string operations could be used to manipulate long numbers and print them out; other representations would probably require special routines for these functions, but might give faster calculation.

BBC Computer Version

5 REM ... Calculator
10 DIM M%240,SS%(10),F%1023
20 S%=0:SS%(S%)=F%:Z%=ASC("0")
30 REPEAT INPUT LINESM%

Look for digit, or one of the following commands:
" - duplicate item on stack
* - multiply
+ - add
/ - divide

40 IF?N%>=ASC("0") AND ?M%<=ASC("9") $F%=$M%: PROCUP:PROCF: UNTIL0
45 IFS%>0 AND ?M%=ASC""""A%=SS%(S%): D%=SS%(S%-1):PROCUP:PROCRESULT:UNTIL0

Make sure there are at least 2 items on the stack, and then set up:
D - top of stack (for result).
B - first operand on stack
A - second operand on stack

46 IF S%<2 PRINT"STACK EMPTY%: UNTIL 0 
48 D%=SS%(S%): BS=SS%(S%-1): AS=SS%(S%-2)
50 IF?M%=ASC"*"PROCMUL: PROCDONE: UNTIL 0
55 IF?M%=ASC"+"PROCADD: PROCDONE: UNTIL 0 
58 IF?M%=ASC"/" PROCDIV: PROCDONE: UNTIL 0 
60 PRINT%ERROR": UNTIL 0

PROCDONE - Decrement stack, then drop through to put result on stack.

90 DEF PROCDONE S%=S%-1

PROCRESULT - Result is in D. Remove leading zeros; then copy result down stack, and print result.

92 DEF PROCRESULT
93 D%=D%-1:REPEAT D%=D%+1: UNTIL ?D%<>Z% OR D%?1=13
95 $A%=$D%: FR=A%: PROCF
100 PRINT " = "$SS%(S%-1)
110 ENDPROC

PROCF - Make room for result on top of stack.

500 DEF PROCF F%=F%+LEN($F%)+1: SS%(S%)=F%: ENDPROC

PROCMUL - Multiply: $D% = $A% * $B%
First set L% to length of result, and zero $D%. Then do long multiplication.

1000 DEF PROCMUL
1005 L%=LEN($A%)+LEN($B%): FOR N%=0 TO L%-1:
D%?N%=Z%: NEXT: D%?L%=13
1010 FOR J%=LEN($B%)-1 TO 0 STEP -1: C%=0: G%=B%?J%-Z%
1020 V%=D%+J%+1
1030 FOR L%=LEN($A%)-1 TO 0 STEP -1: H%=A%?L%-Z%
1040 Q%=G%*H%+C%+(V%?L%-Z%)
1050 V%?L%=Q% MOD 10+Z%: C%=Q%/10:NEXT
1060 V%?L%=C%+Z%
1070 NEXT:ENDPROC

PROCADD - Addition: $D% = $A% + $B%
Set result to longest operand, and add in other operand.

2000 DEF PROCADD
2005 W%=A%:V%=B%: J%=LEN($A%)-LEN($B%): IFJ%<0 W%=B%:V%=A%:J%=-J%
2010 $(D%+1)=$W%:?D%=Z%:C%=0:W%=D%+J%+1
2020 FOR L%=LEN($V%)-1 TO 0 STEP -1
2030 Q%=W%?L%+V%?L%-2*Z%
2040 W%?L%=Q% MOD 10+Z%: C%=Q%/10
2050 NEXT:W%?L%=W%?L%+C%:ENDPROC

PROCDIV - Division: $D% = $A% / $B%
Keep subtracting divisor, counting in V%, using C% as a borrow this time, until overflows (C%=0); then add divisor back in once.

4000 DEF PROCDIV
4005 FOR J%=0 TO LEN($A%)-LEN($B%):W%=A%+J%:V%=-1
4010 REPEAT V%=V%+1:C%=1
4020 FOR L%=LEN($B%)-1 TO -J% STEP -1
4025 Q%=Z%: IF L%>=0 Q%=B%?L%
4030 Q%=W%?L%-Q%+C%+9
4032 W%?L%=Q% MOD 10 +Z%:C%=Q%/10
4035 NEXT
4040 UNTIL C%=0
4050 FOR L%=LEN($B%)-1 TO -J% STEP -1
4055 Q%=Z%:if L%>=0 Q%=b$?l%
4060 Q%=W%?L%+Q%-2*Z%+C%
4065 W%?L%=Q% MOD 10+2%:C%=Q%/10:NEXT
4070 D%?J%=V%+Z%:NEXT:D%?J%=13
4080 ENDPROC

PROCUP - Increment stack

6000 DEF PROCUP IF S%>10 PRINT "STACK FULL":ENDPROC
6010 S%=S%+1:ENDPROC

Variables:

$A%,$B% - Strings containing the two operands used by the arithmetic routines
C% - Carry/borrow
$D% - String into which result is put
H% - Temporary variable
J%,L% - Loop counters
M% - Input line
Q% - Intermediate result in calculations
S% - Next free stack pointer
SS%(0)..SS%(10) - Pointers to number strings on stack
V%,W% - Pointers used by arithmetic routines
Z% - Equal to ASC("0")

Atom Version

5 REM ... CALCULATOR ...
10 DIM M(64),SS(10),F(-1)
20 S=0;SSS=F; Z=CH"0"
30 DO INPUT$M

Look for digit, or one of the following commands:
" - duplicate item on stack
* - multiply
+ - add
/ - divide

40 IF?M>=CH"0"AND?M<=CH"9" $F=$M; GOSUB u;GOSUB f;GOTO x
45 IFS>0AND?M=CH""""A=SSS; D=SS(S-1);GOSUB u;GOTO w

Make sure there are at least 2 items on the stack, and then set up:
D - top of stack (for result).
B - first operand on stack
A - second operand on stack

46 IFS<2 PRINT"STACK EMPTY"';GOTO x
48 D=SSS;B=SS(S-1);A=SS(S-2)
50 IF?M=CH"*" GOSUB m;GOTO z
55 IF?M=CH"+" GOSUB a;GOTO z
58 IF?M=CH"/" GOSUB d;GOTO z
60 PRINT"ERROR"';GOTO x
90zS=S-1

w - Result is in D. Remove leading zeros; then copy result down stack, and print result.

92wD=D-1;DO D=D+1; UNTIL?D<>Z OR D?1=13
95 $A=$D; F=A;GOSUB f
100 PRINT " = "$SS(S-1)'
110xUNTIL 0

f - Make room for result on top of stack.

500 f F=F+LENF+1; SSS=F; RETURN

m - Multiply: $D = $A * $B
First set L to length of result, and zero $D. Then do long multiplication.

1000mL=LENA+LENB;FOR N=0 TO L-1; D?N=Z;NEXT;D?L¿13
1010 FOR J=LENB-1 TO 0 STEP -1;C=O;G=B? J-Z
1020 V=D+J+1
1030 FOR L=LENA-1 TO 0 STEP -1;H=A?L-Z
1040 Q=G*H+C+(V?L-Z)
1050 V?L=Q%10+Z;C=Q/10;NEXT
1060 V?L=C+Z
1070 NEXT; RETURN

a - Addition: $D = $A + $B
Set result to longest operand, and add in other operand.

2000aW=A;V=B; J=LENA-LENB;IFJ<0 W=B;V=A; J=-J
2010 $(D+1)=$W;?D=Z;C=0;W=D+J+1
2020 FOR L=LEN V-1 TO 0 STEP -1
2030 Q=W?L+V?L-2*Z
2040 W?L=Q%10+Z;C=Q/10
2050 NEXT; W?L=W?L+C; RETURN

d - Division: D = $A / $B
Keep subtracting divisor, counting in V, using C as a borrow this time, until overflows (C=0); then add divisor back in once.

4000dFOR J=0 TO LEN A-LEN B; W=A+J; V=-1
4010 DO V=V+1;C=1
4020 FOR L=LEN B-1 TO -J STEP -1
4025 Q=Z; IF L>=0 Q=B?L
4030 Q=W?L-Q+C+9
4032 W?L=Q%10+Z; C=Q/10
4035 NEXT
4040 UNTIL C=0
4050 FOR L=LEN B-1 TO -J STEP -1
4055 Q=Z; IF L>=0 Q=B?L
4060 Q=W?L+Q-2*Z+C
4065 W?L=Q%10+Z;C=Q/10;NEXT
4070 D?J=V+Z;NEXT;D?J=13 
4080 RETURN

u - Increment stack

6000uIF S>10 PRINT"STACK FULL"';RETURN 
6010 S=S+1;RETURN

Variables:

$A,$B - Strings containing the two operands used by the arithmetic routines
C - Carry/borrow
$D - String into which result is put
H - Temporary variable
J,L - Loop counters
M - Input line
Q - Intermediate result in calculations
S - Next free stack pointer
SS(0)..SS(10) - Pointers to number strings on stack
V,W - Pointers used by arithmetic routines
Z - Equal to CH"0"

Further Suggestions

The calculator could be extended to handle negative numbers, represented by a string starting with a sign, and subtraction could then be implemented. As a more ambitious undertakinq, the calculator could be extended to give arbitrary-precision versions of all the integer functions of a standard pocket calculator, including X^Y, factorials, and probability functions.

A more ambitious extension would make these routines the basis of an interpreter, which would allow proqrams to be written manipulating numbers to unlimited accuracy.