Calculators and Reverse Polish Notation

At the end of September, Doc Mike Finnley posted an interesting article about early pocket calculators that caught my eye (I avoided reading any comments). I enjoyed his construction notes, given many of these older machines use NiCad batteries and so generally do require maintenance and repair. His explanation of the often misunderstood percentage key was useful and timely given our esteemed leaders in the HOC are determined to eat into all our percentages while increasing the size of the hole we’re stuck in. Tory’s eh? What are they good for?

The machines in the Doc’s article employ an entry method known as algebraic infix notation – where the word infix refers to the operator (ie: add subtract, multiply or divide) being between the operands (ie: the number values). An infix expression such as (10 + 2) x 3, has two operators (add and multiply) and three operands 10, 2 and 3. Just to make this example mildly more interesting, I’ve added parenthesis to rearrange the order in which operators should be used… in this arrangement we add first and then multiply. If the parenthesis were removed, we’d use the rules of precedence (anyone remember BODMAS?) and divide/multiply followed by add/subtract (in which case the correct answer for 10 + 2 x 3 would be 16).

Entering our original example (10 + 2) x 3 on a standard algebraic infix calculator involves the following eight steps.

(
10
+
2
)
x
3
=

Ending up with the answer 36.

In fact, on the little Sharp used by the good Doctor, I couldn’t see bracket keys so although this problem can still be tackled, it requires an understanding of precedence, which turns out to be the crux of why students would be wise to care about the notation employed by their calculator.

While most will be familiar with using a standard calculator in this way, many may not have noticed the subtle inconsistencies with the way it is working. Consider the add operator, which requires two values to add, but in this case will only have one when the add operation is invoked. That means that the calculator has to put a partial add operation on hold until more values have been entered and either an equals or bracket is pressed. The calculator is now making decisions based on what you are doing, but without knowing any of the detail of the wider problem it is tasked to solve.

This same problem seriously affects compilers (ie: software that can take a program written in an English like language and convert it to executable code, suited to a processor) because a compiler can’t execute any two operand instruction (ie: add, subtract, divide, multiply along with a million others) without first having all the operands it needs. In other words, machines need values first, followed by operators, which algebraic infix notation doesn’t provide.

Historic interlude

Poles and Hungarians are famed the world over for being good at Mathematics. It was the Poles who laid much of the groundwork to break the early three rotor Nazi Enigma cipher, just before a bunch of ugly jack booted Germans waltzed into their country. The Poles were good friends with us Brits as well as being tenacious fighters and courageous allies. Thankfully they also made sure we reaped the benefits of all their many Enigma breakthroughs, involving a long and fairly twisted road of logic, careful deduction and rather brilliant mathematics. Some of the logic of notation had been worked on by a Polish logician and philosopher in the 20’s called Jan Łukasiewicz who began to formalise the best way to arrange operands (values) and operators (actions… such as multiply) from the starting point of expressions in infix notation. His ideas turned out to be important for early computing pioneers because they addressed the issue of how systems need data before starting to process.

Consider our infix statement above:-

(10 + 2) x 3

Łukasiewicz concluded there were two ways to organise the operands and operators. Prefix notation (known as polish notation) would place the operators first, followed by the values. In this case there were two slightly different ways to achieve a polish notation for this expression in infix notation.

x 3 + 10 2 or x + 10 2 3

He went on to say that you could also reverse this, resulting in a postfix notation (more commonly known as Reverse Polish Notation or RPN for short) by placing the values first, followed by the operators. Again, for this particular infix expression, there are two slightly different ways to achieve RPN.

10 2 + 3 x or 3 10 2 + x

His work was far ahead of its time but when everyone else caught up, they quickly cottoned on to how well RPN suited computing. For unlike infix, a postfix notation such as 3, 10, 2, +, x naturally scans left to right. So when the computer reaches the add operator, it already has the operands 10 and 2 at its disposal. Likewise when the multiply operation is reached it would have the previous addition result (12) as well as the operand 3 at its disposal.

Consider a slightly more practical example where we build a theoretical “machine” with a small but rather special type of number store, organised so that the last item we place into the store will be the first item we retrieve. This common type of memory is technically known as a LIFO (Last In, First Out), but software engineers generally refer to this organisation as a Stack. It is a very common memory arrangement.

Imagine we push the number 30 onto our stack. Our next retrieval would pop 30 out, at which point the stack would be empty. If we pushed the values 30, 49 followed by 55 onto our stack it would then contain three values. Our first retrieval would pop out the value 55, at which point the stack would then hold 2 remaining values. Our second retrieval would pop 49 out, leaving one value remaining in the stack and our last retrieval would pop 30 out, at which point the stack would be empty.

So, the Last value In, will be the First value Out.

Assume for the sake of this mind experiment that our theoretical machine has a stack capable of holding three numbers.

Now that we’ve got our theoretical machine complete with its shiny new stack memory, let’s consider our first RPN representation above: 10 2 + 3 x working left to right:-

Now consider the second slightly different RPN representation above: 3 10 2 + x

Both methods work and both methods obtain the right result.

Neither method requires brackets, nor an equal’s key, as both these contrivances are redundant in a postfix arrangement. Both methods are also equally valid and the choice of which to use is purely down to personal preference: in my case it would be based on my experience of knowing the fastest (and safest) way for me to reach a result.

Hewlett Packard (HP) spotted this elegant relationship of a user capable of working with postfix notation and a machine equipped with a stack memory and began the development of larger desktop calculators in the early to middle 60’s which turned out to be highly successful products and came with the bonus of training a generation of women and men to use postfix notation with accuracy and precision. Engineers, insurance brokers, actuaries and financier’s all used RPN calculation technology and the vast majority still do to this day.

HP found that a four level stack would generally suffice for even very complicated problems and in later years christened these the X, Y, Z and T stack and where the X register was always on display. The developmental time period here is quite important, because at the tail end of the 60’s millions of engineers were still using slide rules, given algebraic infix pocket calculators of the day were unable to cope with anything beyond simple two value operator problems. Those machines didn’t permit brackets and had no concept of precedence, which greatly limited their use.

By the late 60’s HP set itself a goal of developing an RPN pocket calculator to fit inside a shirt pocket and released the astonishing HP-35 in 1972. The impact of this pocket calculator was enormous. HP sold 300,000 HP-35s during its short three year production run (short, only because processor improvements quickly made the original chip design obsolete). As a result of students flocking to this machine, colleges dumped slide rule classes and the sales of slide rules died more or less overnight.

From the user point of view, the only price paid (over and above the calculator itself), was the need to learn RPN.

*My work anniversary/commemorative HP35s model – where the heck is that equals key?*

As HP were developing their extensive line of RPN pocket calculators and having a field day with sales, the development of infix calculators continued in parallel but from a starting point of only a partial implementation of algebraic infix notation. As things advanced, more band aids were thrown at infix inconsistencies to make it work better (brackets being the first and then nested brackets as a second improvement) but in essence the underlying logical difficulty of using algebraic infix notation never quite went away. Even in the 70’s, when TI had reached a peak with their fabulous TI-57, 58 and 59 calculators, they set limits on the maximum number of levels of parenthesis and pending values the machines could handle… a limit that I ran into multiple times. Additionally these machines threw out infix notation altogether, whenever they used functions like Sin, Cos, Tan, Root or Square – because the calculator suddenly expected you to about-face and enter the operand value before the function:-

So: 85.2 SIN instead of SIN 85.2 =

Inconsistent and illogical at the same time, especially when you start throwing programming into the mix. Many of these calculators made (and continue to make) the erroneous claim that with algebraic infix notation you can enter an equation just as you would write it down as the user guide for my old Commodore SR7919 illustrates, albeit with a very carefully selected example.

To illustrate this, my old TI 58 and even the little calculator app on my iPhone both give me the wrong answer (9.9) to the following problem, when entered, as it is written.

6+9
10+3

The app treats this as 6+9 ÷ 10 + 3 and so when you press the equals key, it incorrectly starts by dividing 9 by 10 (following BODMAS rules of precedence) and then adds the 6 and 3. Even if you try and help, by first summing the numerator, the app will still give the wrong answer (4.5) after first dividing 15 by 10 and then adding 3. The problem here is that the divisor line sits under the full numerator which algebraic infix doesn’t make clear. The correct answer is 15÷13 or 1.1538462.

Most algebraic infix calculators will get this simple equation wrong, unless you step in and deliberately add two sets of brackets, one containing the full numerator and the other, the full denominator. So any sales blurb that says you’ll be able to enter equations as you write them is generally nonsense and increasingly so as equations become more involved. We’ll see a better aero example further down.

This simple example illustrates the central issue, namely: how do you precisely state the problem you want the calculator to solve?

But this is a question already asked and answered by our friend Jan Łukasiewicz.

My Introduction to RPN

I left school with a humble Commodore SR7919 calculator complete with its power hungry red LED display and PP3 battery but with all the most important trig and table type functions built in namely sin, cos, tan, log, ln, all the inverses along with squares, roots, reciprocal and even a Pi constant key. It even had one memory. Not bad for the late 70’s and good enough for CSE maths. I still own it, it still works and on that calculator I learned that 58008.618 is a magic number whenever the calculator is turned upside down. If you’re wondering what the 8<>5 key does (yep, I had to remind myself) it displays the full mantissa part of the number when the calculator is showing an exponent. For example, divide 1 by 7000 and the machine will display 1.4825-04 but pressing 8<>5 reveals all 8 mantissa digits of the number: 1.4825714 and if you turn that upside down it says hils 2 bhi. Nah, me neither.

It was the only calculator I had when I started studying for a HTEC in telecommunications and it did its job, at the start, but as it didn’t permit brackets and had no grasp of precedence in chain calculations, time and time again I was forced to resort to pen and paper. Three phase calculations, cable loading and span weights, matrix settling, eigenvalues… broadly everything became difficult and error prone.

In my first year at tech-college, I’m rather proud to say I was one of a rather sharp bunch of students… more like a sponges really. We devoured learning, feeding off each other to be the best that we could. Most of us (including me) hadn’t done well at school but more than made up for it at college. It was a period in my life I look back on with great fondness and especially as we were lucky enough to have some of the most gifted tutors I’ve ever encountered, all with their own personal industrial background and through all five years of study. One day in 1978 our mathematics professor brought in his brand spanking new Hewlett Packard HP32E RPN scientific calculator, which was sleek enough to gather a great deal of attention. I’d never seen anything remotely as well built. He spent most of that class chatting about it with the students, along with side discussions concerning the early Sinclair calculators… another story, but again with Polish involvement.

*The HP-32E*
Alex P. Kok, CC BY-SA 4.0, via Wikimedia Commons

So, where is the equal’s key I asked?

I think even now I’m slightly surprised by how quickly I grasped the nuances of his introduction to Reverse Polish Notation as I could see at a stroke it eliminated the need for parenthesis and in fact during long chain calculations, the display provided visual feedback of intermediate results, so checking became instinctive and easy. I could still use normal estimation techniques to roughly guess where values should lie but then check those against the results on the display, as I proceeded with a calculation. That cut down my risk of miscalculating results.

I was sold (I wasn’t the only one) and popped down later that week to a specialist store on Wimbledon Broadway to buy my own HP32E (which I still have to this day). Everything about the calculator was crafted with care and attention. The keyboard, display, packaging and especially the documentation were master classes in excellent design. Within a day I could use it properly.

Since then I’ve always used RPN and won’t use an algebraic infix calculator for anything other than very simple calculations. I own ten or so different HP calculators including my original 1978 HP32E. These include a really old HP29C, newer anniversary models of both the HP15C and the 35s (which I use daily at work) plus a beautiful HP41CV and my much loved HP42s. On the graphing side of HP calculator products I started with the excellent HP48GX (which saw me through an honours degree in mathematics and computer science) along with a HP49, 50 and finally (most recently) a HP Prime, which is a very capable graphing RPN calculator. I also own a number of non HP products, including the excellent WP34s RPN calculator, which came into being after a large group of smart people took an off the shelf HP financial calculator (the 30b) and repurposed it with the objective of making something better than the incomparably good HP42s. A high bar perhaps, but I think they succeeded admirably building an excellent machine (which has a free phone app emulator).

In the algebraic world, while at college I got through three different Commodores, a couple of Sharps and finally stretched to the dizzy heights of a Texas Instruments TI 58. I loved that machine because I cut my teeth on the basics of programming with its help. But it was an object lesson in the limits of algebraic infix entry that never left me. You couldn’t program a HP32E, but in all other regards it could run rings around a TI 58.

The big advantage with RPN is that it forces you to structure equations in an efficient way. Because smaller intermediate parts are calculated as they are entered, errors become far more obvious with RPN whereas with an algebraic infix calculator, leaving off an opening bracket may not cause a calculation error until very much later, when an entire intermediate result is evaluated.

The rest is down to what works for you. But for me, I neither trust algebraic infix machines nor like them.

As one final parting example, consider an over optimistic effort to break the speed of sound, where a high-flying ace pilot pushes open the throttle of her surplus Corsair aircraft to see if she can make a sonic boom. From her instruments, she reads a pressure altitude of 25,500 feet and a calibrated airspeed of 350 knots. What is her air speed?

Has she beaten Mach 1?

Well, the equation below calculates her Mach number, given pressure altitude and calibrated air speed and the full equation, with all these values neatly plugged in, is as follows:-

An experienced user with a RPN calculator will probably need 20 seconds to compute this. It took me 35 seconds but I do tend to traverse complex calculations like this cautiously, due to the nesting. If you have to use an algebraic calculator, my wager is it’ll take much longer, assuming the calculator can solve the problem at all.

I used the following steps on my HP35s calculator to solve this (the answer is 0.835725 – MACH 0.84, so no, our budding lady ace didn’t beat the speed of sound). My starting point is near the centre (350/661.5) and the RPN key strokes and the intermediate x register results after each step are shown below. That said and in precisely the same way that (10+2)*3 had two RPN solutions, there are a number of alternate RPN solutions that would work equally in this case. Quite likely, one will be better than mine.

Personally, I always start near the middle and work out. I observed brackets, but solely to ensure mathematical correctness. During the keystrokes, RPN allows me to see my intermediate results and deal gracefully with any errors that I make during the keying process, but I neither have to think of, nor use parenthesis. I don’t care how many key strokes it takes. The only thing I care about is the accuracy of the result, or more precisely, the likelihood of the result being accurate. It just so happens that RPN is extremely helpful in that regard.

Note that: CHS means change sign. EE sets exponent entry mode which is useful when entering numbers like 6.875 x 10^-6

Key stroke	X stack register	Comment
350 ENTER	350	Start more or less at the centre with 350/661.5
661.5 ÷	0.529101
2 y^x	0.279947	Square the result
0.2 x	0.055989	Multiply by 0.2
1+	1.055989	Add 1
3.5 y^x	1.210065	And then raise to the power of 3.5.
1 –	0.210065	Finally subtract 1 which leaves the x register holding the left hand side of the squiggly brackets {}. We’ll leave that as an intermediate result and use it later.
1 Enter	1	Now moving to the right side of the squiggle bracketed section {} – start with the left hand 1. Note we push this onto the stack (using ENTER) so that our intermediate result 0.210065 above is not lost
6.875 EE CHS 6 ENTER	0.000007	Now place 6.875 x 10^-6 onto the stack
25500 *	0.175313	Type in 25500 and then multiply to form the sum
–	0.824688	Subtract, to take the difference of the above value from the very first 1
5.2656 CHS y^x	2.759221	Raise the right hand bracket to the power of -5.2656
*	0.579615	Finally multiply the right and left hand blocks – which now clears all the parts inside the squiggly {} braces. The x register now contains the full value of the entire squiggly brace section.
1 +	1.579615	Now clear the outer operators – so, add 1
0.286 y^x	1.139687	Raise that result to the power of 0.286
1 –	0.139687	Subtract 1
5 *	0.698435	…then finally clear the far left multiplication by 5. That completes everything under the root.
√	0.835725	Finally take the square root (you can raise to a half if you can’t find a square root key). Voila our answer is 0.84 So, not quite Mach 1, but pretty close.