RPN or DAL?

by James Redin

History


To add "eighth plus six" in your normal calculator you just press the following sequence of keys:

[8] [+] [6] [=]

Very simple, right? Now, how would you do the same operation in an RPN calculator? The procedure involves to enter the two operands first and then its operator. This yields the following sequence:

[8] [ENTER] [6] [+]

Notice that the sequence still requires four keystrokes, although it may look a little confusing if you never had an HP calculator.

Hewlett-Packard have used the "Reverse Polish Notation, RPN" since they launched the first scientific pocket calculator, the HP-35, back in 1972. Two of the reasons why Hewlett-Packard decided to use the RPN notation as opposed to the Direct Algebraic Logic (ADL) used on standard calculators were probabily the following: first, Reverse Polish Notation is a very efficient way for a chip logic to perform calculations, and second, a technical user, which was the main target for scientific calculators, can perform more complicated calculations with less number of keystrokes, by using this procedure. To illustrate this, lets take two simple examples which do not use scientific functions:


CASE A: Solve the following expression: (8 + 6)(7 - 5)

With a normal calculator, assuming you have memory functions, you have to enter:

[8][+][6][=] [M+] [7][-][5] [x] [MR] [=]

while, with an RPN calculator you just enter:

[8][ENTER][6][+] [7][ENTER][5][-] [x]

RPN required only 9 keystrokes instead of the 11 required by a standard calculator.


CASE B: Solve the following expression: [(8 + 6)(7 - 5)] / (9 - 7)

A user with a standard calculator still can solve this expression (without memorizing or noting subtotals in a piece of paper), but the solution is tricky as shown in the following sequence:

[8][+][6][=][M+] [7][-][5][x][MR][=] [MC][M+] [9][-][7][/][MR][=][MC][M+][1][/][MR][=]

Instead of the 25 keystrokes and a lot of ingenuity, an RPN calculator would require only 14 strokes and the application of the same basic technique: evaluate one operation at a time by entering the two operands first and then the operator that acts upon them:

[8][ENTER][6][+] [7][ENTER][5][-] [x] [9][ENTER][7][-] [/]


Obviously, once you get the feeling of the technique it is not only efficient but also elegant, and this was one of the reasons why HP RPN calculators were so widely accepted among technical users.

In a normal arithmetic expression, operations are grouped within parentheses to control the precedence of the operations. Segments of the expression which are enclosed within parentheses must be solved prior to continuing with the remaining parts of the expression. Parentheses can also be nested, in which case inner parentheses have precedence and must be solved first.

A polish mathematician, Jan Lukasiewicz, demonstrated in 1929 (though even this may be late; it could be as early as 1922 [3]) that parentheses are not required to specify the sequence of operations within an expression. He showed that the reason why parentheses are used is because the operator is inserted in between the operands and operands cannot be used as delimiters in the expression, however, if the operator is specified before (Polish Notation) or after (Reverse Polish Notation) the operands, then the operator acts also as a delimiter or separator of the different expression components, and the order may then be controlled by setting a left-to-right precedence of the expression components.

This left-to-right precedence is very compatible with the sequential nature of operations in a computing device. LIFO (Last-In-First-Out) algorithms and sequential stacks are common place in compilers and computer languages. So it was natural for early scientific calculators to use the RPN notation. The usage of standard algebraic approach introduced additional complexity and overhead which was not desirable at the point where the technology was in 1972 when the first scientific calculator was introduced in the market by Hewlett-Packard. The RPN method, however, proved to be successful not only from the point of view of chip design efficiency but also from the point of view of human operation. Once the user gets the basic understanding on the technique, its elegance converts users into RPN fans, which is one of the factors responsible by the popularity of HP among technical users.

Of course, the advantage tends to disappear when the operations are simple, like the ones normally handled in standard four function calculators, and this is the reason why standard non-scientific calculators do not use RPN notation. More over, non-HP scientific calculators, such as the ones manufactured by Texas Instruments, relied on the algebraic model for their data-entry by providing parentheses as part of the keyboard, at the beginning that imposed limitations on the number of nested levels that could be handled, but these limitations started to disappear as new models arrived.

Another limitation of the algebraic model was the fact that even with the usage of parenthesis, the operators had to be entered by the user explicitly, even though the usual expression involved the implicit multiplication operator. For example, to solve the expression 5(8-2), the user had the enter the sequence:

[5] [x] [(][8][-][2][)] [=]

This can become very inconvenient in certain expressions. To overcome this problem, Sharp developed a technology called "Advanced Direct Algebraic Logic (Advanced DAL)," which allows for the user to enter an expression in the same way as it appears in a text on a written document. For example, the expression:

2 sin(45+2^3)

would be entered as:

[2] [sin] [(] [4][5] [+] [2] [^] [3] [)] [=]

This simplifies significantly the number-entry procedure and constitutes an interesting progress in the usage of algebraic notation within scientific calculators.

Under RPN, the previous expression may be entered as:

[2][ENTER][3][^] [4][5] [+] [sin] [2] [x]

One less stroke was required by the RPN procedure. In addition, RPN fans will state that the RPN procedure gives a better understanding on what the expression is actually doing. And most probabily they will be right. On the other hand, ADL advocates will say that entering the expression actually implies that there is already a previous understanding on what the expression is doing, so they would rather leave the chip circuits to determine the sequence on which the elemental operations need to be performed. And most probably, they will also be right…

Sources:

[1] Thomas M. Whitney, France Rode, and Chung C. Tung , "The 'Powerful Pocketful': an Electronic Calculator Challenges the Slide Rule." Hewlett-Packard Journal, June 1972, Article 1 - Sidebar: "Reverse Polish Notation"

[2] David Hemmendinger - Notes from the 4th. Edition of the "Encyclopedia of Computer Science" to be published in 1998.


The X-Number World of Calculators
Copyright James Redin - October 5, 1997
Revised: February 12, 2005.