Algebraic Operation System (AOS)

[Thomas Klemm]

Description

This program allows you to use the Algebraic Operation System (AOS) similar to how old Texas Instruments calculators work.
The shunting yard algorithm is used with a data and an operator stack.
Their stack size is configurable and is only limited by the amount of memory available.

Functions

The functions just operate on the X register in postfix notation.
This is how the TI-57 and other older calculators from Texas Instruments work.

For example, to calculate \( \sqrt{3^2 + 4^2} \) use:

3 x^2 + 4 x^2 = √x

Alternatively we can use:

( 3 x^2 + 4 x^2 ) √x

However, this requires one more keystroke.

Apparently we use a mixture of infix notation for arithmetic operations and postfix notation for functions.

Change Sign

It behaves similarly to an ordinary function.

E.g. an expression like \( - 3^4 \) has to be keyed in like:

3 y^x 4 = +/-

Or alternatively:

( 3 y^x 4 ) +/-


Intermediate Results

The intermediate results of a calculation are viewed and may also be printed.

Example

\( \frac{1 \times 2 + 3 \times 4 + 5 \times 6 + 7 \times 8}{4} \)


( 1 * 2 + 3 * 4 + 5 * 6 + 7 * 8 ) / 4 =

Code:

ST X=                  2
ST X=                 12
ST X=                 14
ST X=                 30
ST X=                 44
ST X=                 56
ST X=                100
ST X=                 25

Implicit Data Entry

The current value in the X register is used as data entry.

This allows to reuse the first entry:

3 + =

This results in \( 3 + 3 = 6 \).

3 * * =

This results in \( 3^4 = 81 \).


The Monster Formula

The formula is from A case against the x<>y key:

\( 1 - 2 \times 3^4 \div 5 + \sin\left(6 - \sqrt[3]{7^2} \right) \times 8! + \ln \left[ \left(-9^{2^3} \times 45 ^ \frac{6}{7} \right)^2 \right] \)

Here's how it is entered with this program.

1 - 2 * 3 ^ 4 / 5 + ( 6 - 7 X^2 ^ 3 1/X ) SIN * 8 FACT + ( 9 ^ 2 ^ 3 * 45 ^ ( 6 / 7 ) ) CHS X^2 LN =

1657.008948


Intermediate Results

Code:

ST X=                 81
ST X=                162
ST X=               32.4
ST X=              -31.4
ST X=      3.65930571002
ST X=      2.34069428998
ST X=      1646.72764773
ST X=      1615.32764773
ST X=                  8
ST X=           43046721
ST X=   8.57142857143ᴇ-1
ST X=      26.1239772883
ST X=      1124551561.74
ST X=      1657.00894809

Registers

This is a list of the registers after the calculation:

Code:

00:                 5
01:                10
02:              -4.1
03:                 0
04:                 0
05:                 0
06:     1615.32764773
07:          43046721
08:                45
09:                 6
10:                 0
11:              -1.2
12:                 0
13:              -3.1
14:               5.1
15:                 0
16:              -4.1
17:                 0
18:                 0
19:                 0

Mark Hardman’s solution

(05-10-2015 03:12 PM)Mark Hardman Wrote:  

Code:

              x          y          z          t
1 [Enter]     1          -          -          -
3 [Enter]     3          1          -          -
4             4          3          1          -
y^x          81          1          -          -
2             2         81          1          -
x           162          1          -          -
5             5        162          1          -
/            32.4        1          -          -
-           -31.4        -          -          -
6 [Enter]     6        -31.4        -          -
7             7          6        -31.4        -
x^2          49          6        -31.4        -
3             3         49          6        -31.4
1/x           0.3333    49          6        -31.4
y^x           3.6593     6        -31.4      -31.4
-             2.3407   -31.4      -31.4      -31.4
sin           0.0408   -31.4      -31.4      -31.4
8             8          0.0408   -31.4      -31.4
x!        40320          0.0408   -31.4      -31.4
x          1646.7276   -31.4      -31.4      -31.4
+          1615.3276   -31.4      -31.4      -31.4
45 [Enter]   45       1615.3276   -31.4      -31.4
6  [Enter]    6         45       1615.3276   -31.4
7             7          6         45       1615.3276
/             0.8571    45       1615.3276  1615.3276
y^x          26.1240  1615.3276  1615.3276  1615.3276
2 [Enter]     2         26.1240  1615.3276  1615.3276
3             3          2         26.1240  1615.3276
y^x           8         26.1240  1615.3276  1615.3276
9 [Chs]      -9          8         26.1240  1615.3276
x<>y          8         -9         26.1240  1615.3276
y^x        4.3047e07    26.1240  1615.3276  1615.3276
x          1.1246e09  1615.3276  1615.3276  1615.3276
x^2        1.2646e18  1615.3276  1615.3276  1615.3276
ln        41.6813     1615.3276  1615.3276  1615.3276
+       1657.0089     1615.3276  1615.3276  1615.3276

TI-57

These are the key strokes for the TI-57:

1 - 2 × 3 y^x 4 ÷ 5 + ( 6 - 7 x^2 INV y^x 3 ) 2nd sin * 40320 + ( 9 y^x ( 2 y^x 3 ) × 45 ^ ( 6 ÷ 7 ) ) +/- x^2 lnx =

We get the same result:

1657.0089

For this I used the TI-57 Programmable Calculator.
However I had to cheat a little: since the factorial function is missing I just replaced \( 8! \) with \( 40320 \).
Also since the \( y^x \) operation apparently is not right associative I used another pair of parenthesis to calculate:

\( 9 ^ {2 ^ 3} = 9 ^ {(2 ^ 3)} \)

Program

This is the program for the HP-41C:

Code:

01▸LBL "AOS"
02 CLRG
03 3
04 STO 00
05 10
06 STO 01
07 CLST
08 RTN
09▸LBL "+"
10 -1.2
11 GTO 00
12▸LBL "-"
13 -2.2
14 GTO 00
15▸LBL "*"
16 -3.1
17 GTO 00
18▸LBL "/"
19 -4.1
20 GTO 00
21▸LBL "^"
22 5.1
23▸LBL 00
24 STO 02
25 FRC
26 X>0?
27 GTO 11
28▸LBL 09
29 RCL IND 01
30 X=0?
31 GTO 10
32 FRC
33 X<Y?
34 GTO 10
35 X<> Z
36 LASTX
37 XEQ 06
38 R^
39 GTO 09
40▸LBL 10
41 RDN
42▸LBL 11
43 RDN
44 RCL 02
45 XEQ 07
46 ISG 00
47 RTN
48 STO IND 00
49 RTN
50▸LBL "<"
51 0
52▸LBL 07
53 ISG 01
54 RTN
55 STO IND 01
56 RDN
57 RTN
58▸LBL ">"
59 XEQ 08
60 DSE 01
61 RTN
62▸LBL "="
63▸LBL 08
64 RCL IND 01
65 X=0?
66 GTO 13
67 XEQ 06
68 GTO 08
69▸LBL 13
70 RDN
71 RTN
72▸LBL 06
73 DSE 01
74 X<>Y
75 RCL IND 00
76 DSE 00
77 X<>Y
78 XEQ IND Z
79 VIEW X
80 RTN
81▸LBL 01
82 +
83 RTN
84▸LBL 02
85 -
86 RTN
87▸LBL 03
88 *
89 RTN
90▸LBL 04
91 /
92 RTN
93▸LBL 05
94 Y^X
95 END

Key Assignments

Of course you are free to choose differently buy I recommend the following key assignments:

Code:

| Label | Key    | Code
|-------|--------|-----
| +     | +      |  61
| -     | -      |  51
| *     | *      |  71
| /     | /      |  81
| ↑     | Y↑X    | -12
| =     | ENTER↑ |  41
| <     | X<>Y   |  21
| >     | R↓     |  22
| AOS   | CLx/A  | -44

Registers

The program needs 3 register to control the data and the operator stack:

Code:

| Register | Comment
|----------|----------------------
| 00       | top of data stack
| 01       | top of operator stack
| 02       | current operator

Synthetic Programming

We could use the alpha registers M, N and O instead of register 00-02.
With this the data stack could be started at register 00.
For now I'm leaving that as an exercise for the dear reader.

Operators

The decimal part of the code is used as precedence.
A negative code means left associativity.

The code for the left parenthesis ( is 0.
Thus we already have an implicit open parenthesis.
This makes handling the right parenthesis ) and = similar.

Code:

| Operator | Label | Code  | Precedence | Associativity
|----------|-------|-------|------------|--------------
| (        |       |   0   |            |
| +        | 01    |  -1.2 | -0.2       | left
| -        | 02    |  -2.2 | -0.2       | left
| *        | 03    |  -3.1 | -0.1       | left
| /        | 04    |  -4.1 | -0.1       | left
| ^        | 05    |   5.1 |  0.1       | right

Code Walkthrough

Initialisation

The registers and the stack is cleared with:

XEQ AOS

Here you can configure the start of the data and the operator stack.
Be warned that there are no checks in the program.
Thus the data stack could grow into the operator stack and vice versa.
It's up to you to select reasonable values.

Code:

LBL "AOS"
CLRG
3                ; top of data stack
STO 00
10               ; top of operator stack
STO 01
CLST
RTN

Enter Operator

Each operator pushes a specific code onto the stack in which label, precedence and associativity is encoded.

Code:

LBL "+"
-1.2
GTO 00           ; new operator

LBL "-"
-2.2
GTO 00           ; new operator

LBL "*"
-3.1
GTO 00           ; new operator

LBL "/"
-4.1
GTO 00           ; new operator

LBL "^"
5.1

LBL 00           ; new operator

New operator

Each time we reach a new operator, we pop operators from the stack until we reach one that has lower precedence.
In the case of a right associative operator, we also stop if we reach an operator of the same precedence.

Code:

| X    | Y    | Decision
|------|------|-----------
| -0.2 | -0.2 | pop
| -0.1 | -0.2 | pop
|  0.1 | -0.2 | pop
| -0.2 | -0.1 | no more
| -0.1 | -0.1 | pop
|  0.1 | -0.1 | pop
| -0.2 |  0.1 | no more
| -0.1 |  0.1 | no more
|  0.1 |  0.1 | no more

There's no lower precedence than -0.2, thus + and - always pop.
On the other hand, ^ never pops previous operators.
This leaves us with * and / which pop unless an operator on the stack has lower precedence like + or -.

Stack diagram: ( x op -- x' )

Code:

LBL 00           ; add new operator
STO 02           ; save new operator
FRC              ; precedence of new operator
X>0?             ; it is ^
GTO 11           ; no more pop
LBL 09           ; while higher precedence
RCL IND 01       ; top of stack operator
X=0?             ; is left parenthesis ?
GTO 10           ; no more pop
FRC              ; precedence of top of stack operator
X<Y?             ; has lower precedence ?
GTO 10           ; no more pop
X<> Z            ; x
LASTX            ; top of stack operator
XEQ 06           ; pop operator
R^               ; precedence of new operator
GTO 09           ; while higher precedence
LBL 10           ; no more pop
RDN              ; drop precedence of top of stack operator
LBL 11           ; no more pop
RDN              ; drop precedence of new operator
RCL 02           ; current operator
XEQ 07           ; push operator
ISG 00           ; push data
RTN              ; no op
STO IND 00       ; store data
RTN

Push Operator

The left parenthesis ( is just pushed onto the operator stack.
The RTN command after ISG is used as a no-operation which is always skipped.

Code:

LBL "("
0

LBL 07           ; push operator
ISG 01           ; increment top operator
RTN              ; no op
STO IND 01       ; store operator
RDN              ; drop operator
RTN

Right Parentheses and Equals

Code:

while the operator at the top of the operator stack is not a left parenthesis:
    pop the operator from the operator stack into the output queue
pop the left parenthesis from the operator stack and discard it

Code:

LBL ")"
XEQ 08
DSE 01          ; pop left parenthesis
RTN

LBL "="
LBL 08          ; while not (
RCL IND 01      ; top of operator stack
X=0?            ; is left parenthesis ?
GTO 13          ; pop (
XEQ 06          ; pop operator
GTO 08          ; while not (
LBL 13          ; pop (
RDN             ; drop operator
RTN

The = operator does not pop the implicit left parenthesis.
But otherwise it behaves like the right parenthesis and removes any leftover operators from the operator stack.

Pop Operator

Stack diagram: ( a x op -- a a op x' )

Code:

LBL 06           ; pop operator
DSE 01           ; decrement top of operator stack
X<>Y             ; ( a op x )
RCL IND 00       ; y: top of data stack
DSE 00           ; pop data
X<>Y             ; ( a op y x )
XEQ IND Z        ; execute operator
VIEW ST X        ; view result
RTN

Implementation

This is just the implementation of the operators:

Code:

LBL 01           ; +
+
RTN

LBL 02           ; -
-
RTN

LBL 03           ; *
*
RTN

LBL 04           ; /
/
RTN

LBL 05           ; ^
Y^X
END

HP-42S

The program also works with the HP-42S.
However, we can assign the programs only to a custom menu.

I'm using the following layout:

Code:

 X^2  | SQRT | 10^X | LOG  | E^X  |  LN
------+------+------+------+------+------
   +  |   -  |   *  |   /  |   ↑  |   =
------+------+------+------+------+------
   (  |   )  |  1/X |  N!  |      |  AOS

But compared to the HP-41C, the user experience is modest.

Code:

00 { 186-Byte Prgm }
01▸LBL "AOS"
02 CLRG
03 3
04 STO 00
05 10
06 STO 01
07 CLST
08 RTN
09▸LBL "+"
10 -1.2
11 GTO 00
12▸LBL "-"
13 -2.2
14 GTO 00
15▸LBL "*"
16 -3.1
17 GTO 00
18▸LBL "/"
19 -4.1
20 GTO 00
21▸LBL "↑"
22 5.1
23▸LBL 00
24 STO 02
25 FP
26 X>0?
27 GTO 11
28▸LBL 09
29 RCL IND 01
30 X=0?
31 GTO 10
32 FP
33 X<Y?
34 GTO 10
35 X<> ST Z
36 LASTX
37 XEQ 06
38 R↑
39 GTO 09
40▸LBL 10
41 R↓
42▸LBL 11
43 R↓
44 RCL 02
45 XEQ 07
46 ISG 00
47 RTN
48 STO IND 00
49 RTN
50▸LBL "("
51 0
52▸LBL 07
53 ISG 01
54 RTN
55 STO IND 01
56 R↓
57 RTN
58▸LBL ")"
59 XEQ 08
60 DSE 01
61 RTN
62▸LBL "="
63▸LBL 08
64 RCL IND 01
65 X=0?
66 GTO 13
67 XEQ 06
68 GTO 08
69▸LBL 13
70 R↓
71 RTN
72▸LBL 06
73 DSE 01
74 X<>Y
75 RCL IND 00
76 DSE 00
77 X<>Y
78 XEQ IND ST Z
79 VIEW ST X
80 RTN
81▸LBL 01
82 +
83 RTN
84▸LBL 02
85 -
86 RTN
87▸LBL 03
88 ×
89 RTN
90▸LBL 04
91 ÷
92 RTN
93▸LBL 05
94 Y↑X
95 END

References

• Shunting-yard algorithm
• Dijkstra's original description of the Shunting yard algorithm