Wednesday, May 6, 2009

Wednesday Math, Vol. 70: Reverse Polish Notation

What do I mean by three times five plus two?

If I write 3 * 5 + 2 into a calculator, the machine will understand the order of operations rules, do the multiplication first to get 15 + 2, which of course is 17.

If I really wanted the addition to be done before the multiplication, I would put parentheses around that operation, 3 * (5 + 2) = 3 * 7 = 21.

2 + 5 * 3, the numbers and operators all reversed, gives us the exact same situation. Order of operations tells us to do a multiplication before an addition, even though the multiplication is second from left to right. 2 + 5 * 3 = 2 + 15 = 17. If I really want to do the addition first, I need parentheses to make that clear (2 + 5) * 3 = 7 * 3 = 21.

Jan Łukasiewicz, pronounced "Yawn WooKAshayvitz", was a mathematician of Polish ancestry born in Lwow in what was then the Austro-Hungarian empire and now is part of the Ukraine. His main field was logic, and his best known development combines computers and computation, and is known now as Reverse Polish Notation.

Instead of the tricky order of operations we teach students as PEMDAS (parentheses first, then exponents, multiplication and division next, followed by addition and subtraction, where if no other rule takes precedence we should work from left to right), Łukasiewicz's method is based completely on order of the number and symbols, without needing parentheses. It uses the idea of storing information in what is known as a stack, a common storage method in computers where things are stored in the order they arrived, with the most recent thing put on the stack is the first thing you retrieve. Physically, it's like a stack of dishes, where the easiest thing to retrieve is the thing you just put on the top. The things we will be storing are numbers and operators, where the operators are things like addition, subtraction, multiplication, division and exponentation.

In Polish Notation, if we get an operator, a number and then another number, we would store the first two things, and when the second number in a row comes up, we pull the first number off the stack, then the operator, do the operation on the two numbers, then store the result back on the stack.

In Reverse Polish Notation, known as RPN for short, we are looking for two numbers, then an operator. Any time we get an operator, there should be at least two numbers on the stack, and the program knows to go get the last two and perform the operation, then put the answer back on the stack. It's easier to implement on a computer and it avoids having to ever use parentheses.

Example #1: 3 5 * 2 +
Here is how a computer using RPN would read this.
3: Put 3 on the stack.
Stack = 3.
5: Put 5 on the stack, so the stack now has 5 on top and 3 in the second position.
Stack = 5, 3.
*: * means multiplication, so pull the 5 and the 3 off the stack, multiply them to get 15, and put 15 on the stack.
Stack = 15.
2: Put 2 on the stack.
Stack = 2, 15.
+: Pull 2 and 15 off the stack, add them together to get 17, then put 17 on the stack.
Stack = 17.

Since the string of numbers and operators has terminated, the answer is 17, and it now resides on the top of the stack where it is easily accessed by the computer.

Example #2: 3 5 2 + *
3: Put 3 on the stack.
Stack = 3.
5: Put 5 on the stack.
Stack = 5, 3.
2: Put 2 on the stack.
Stack = 2, 5, 3.
+: Pull 2 and 5 off the stack, add them together to get 7, then put 7 back on the stack.
Stack = 7, 3.
*: Pull 7 and 3 off the stack, multiply them together to get 21 and put it on the stack.
Stack = 21

The string is terminated, so the answer is on the top of the stack.

RPN makes the programmer's job a breeze, much easier than the odd order of operations people are taught in grade school, and programmers at Hewlitt-Packard decided their calculators should read input in RPN. The general public took to RPN the same way they took to Esperanto, which is to say there were some loyal and enthusiastic adopters, but a lot of resistance in general. Hewlitt-Packard's championing of RPN is one of the reasons it lost market share to Texas Instruments, which produced many calculators that input numbers and symbols the way people expected, instead of the way that is simpler for the writer of the software.


bobmando said...

I loved RPN and had a couple of different HP calculators... the last one was a scientific programmable that I left programmed to calculate interest payments. And over the past decade I have gone over to the majority view... A shame really... RPN was easy and elegant for me.

Matty Boy said...

RPN is a nice idea, actually better than Esperanto. I know what a mess students make of the order of operations rules. But old habits die hard.

Karen Zipdrive said...

Math- yeecch.

Mathman6293 said...

As soon as I saw the HP pic, I knew you were writing about RPN because I never read titles.