The joys of Reverse Polish Notation

The big deal about Reverse Polish Notation (RPN) is that it eliminates the need for operator precedence and brackets. We will symbolise multiplication by the "*" symbol rather than x to keep with programming tradition.

Why brackets are needed
take the sum
2*3+4 can be interpreted 2 ways
2*(3+4)=14 & (2*3)+4=10, without brackets typically we assume multiplication has higher precedence than addition ,in most programming languages in that multiplication is done before addition, meaning that we interpret the otherwise
ambiguous sum 2*3+4 as (2*3)+4 in computer languages like C.

In short brackets are a bad inelegant idea in Mathematics and never should have been invented,
they are as stupid as Roman Numerals.

Youtube video here.

Wikipedia RPN explanation here which is quite thorough.

Well what use is this for programming and science?
Well we can count all possible equations within a solution space in reverse polish notation, somewhat similar to a Turing machine can compute all possible algorithms by counting them, see also Halting Problem.

For instance if we only allow the integers 1 & 2 & The operators + & *

All possible sums upto depth 5 are as follows.
1 1 +
1 1 *
1 2 +
1 2 *
2 1 +
2 1 *
2 2 +
2 2 *
1 1 1 + +
1 1 1 + *
1 1 2 + +
1 1 2 + *
1 2 1 + +
1 2 1 + *
skipping a few here.... ,
2 2 2 * *
1 1 + 1 +
1 1 + 1 *
and skipping another few here..... ,
2 2 * 2 *

As + & * are both binary operators the only criterions, for the counting algorithm, which generates all possible sum permutations, within the solution space, is, that there are one less operators ( + & * thingys ) than operands ( numbers ), & the first operand can only be as far left as the third term in the sum as a binary operator pulls 2 items off the RPN stack.

Minor enhancements to the counting algorithm can handle unary operators as well.
e.g. factorial (!) 3 is written as 3!=1*2*3=6
The following is a legitimate RPN sum
3 ! ! = 6 ! = 1 * 2 * 3 * 4 * 5 * 6=720 &
3 ! ! 2 + ! is an example of a complex but valid sum using both unary and binary operators.

Well what can we do with this?
If we had a lists of constants of physics and mathematical numbers like the following.
m pi 3.14159265
m e  2.718281828
p speed_of_light 2.99792458e+8
p magnetic_constant 1.25663706144e-6
p electric_constant 8.854187817e-12
p charge_of_electron 1.60217733e+19
p mass_of_electron 9.1093897e-31
p mass_of_proton 1.6726231e-27
p mass_of_neutron 1.674929e-27
p electronic_radius 2.81794092e-15
p planck_constant 6.626076e-34
p avodagro_constant 6.0221367e+23
p loschmidt_constant 2.686736e+25
p molar_gas_constant 8.314510
p faraday_constant 9.6484531e+4
p stefan_boltzmann_constant 5.67051e+8
p rydberg_constant 1.0973731534e+7
p gravitational_constant 6.67259e+11
p acceleration_due_to_gravity 9.80665

We could put one of the constants on the left hand side, &, count all possible sums
within a solution space using the remaining constants to see if any of the constants are redundant within an error tolerance. Set the error tolerance too large and we get too many false positives, set it too low errors in calculations or the accuracy of the constants will cause us to dismiss valid answers, a reasonable error tolerance is 0.01% one in 10,000.

With this we could make a wild discovery like Eulers Identity  ( click the link for a look ) if our algorithm was enhanced to handle complex numbers.

A formula which does come out in the wash using this algorithm is  if square root (sqrt) is one of the allowed operands is
sqrt(magnetic_constant*electric_constant ) = speed of light.
one of maxwells equations so our algoithm could have made a discovery simplifying the laws of physics by making oue of the constants of physics redundant.

With another enhancement to the program, we can find formulas for sequences of numbers, e.g. 0, 3, 6, 9, 12, 15 even ones too complex for a human to find. We have an alternative to least squares method which can only do finite polynomials and can't handle things like sin(x)

More info on the program which I call fundamental and the actual source code can be found here I'm now marketing it under Dirac because it implements that crazy genius's talents to pull inhuman equations out for curve fitting praise jesus sorry about the bugs it's still a work in progress, watch out for the hopelessly broken loopvar implementation and error tolerance division by zero bugs.

About the author

D.J. Barrow is an Engineer Linux Consultant based in Ireland, his website is here

Other potentially interesting links on this site


Popular posts from this blog

Lowdown of everything I know about how to get good at programming fast

How the Multiiverse is programmed by God..., well at least to a first approximation, Physics the Shamanic Way