For most people, the word math is a scary word, it invokes memories of being back at school and having trigonometry and calculus forced down your throat by an imposing teacher who didn’t understand why you couldn’t recognise the power of the language. They didn’t want to teach you because you didn’t care and you didn’t want to learn because you found it boring. Or was that just me?

My journey into math didn’t really begin until I got outside of school. I was studying mechanical engineering as an apprentice heating and ventilation engineer. As I learned my trade I found I had to do things like measure the length of a room, subtract from that the distance a bracket stood out from a wall to the centre of a pipe, knock off the thread length and finally cut a piece of pipe to suit. I found my way into math through practical application, if I add these two numbers and subtract this I can cut here and have something that fits into that gap.

Today I work as a technical specialist for an internet service provider and the math has changed. These days it’s all algorithms, transferring data through the use of defined logic.

Recently one of our architects proposed an algorithm for filtering a set based on a series of expected pre-conditions. Whilst the overall behaviour of the algorithm is fairly straight-forward (given input A, return a subset of all matching items in set S), the algorithm itself is very complex. This in turn makes it very difficult to express without a detailed and somewhat convoluted description.

This algorithm is reasonably well defined but when I looked at it, it has invoked a sense of fear, partially because the algorithm is complex, partially because it changes shape and finally because said algorithm needs to be invoked on a monstrous beast.

To my mind then, the problem turns from one of “how best to implement an algorithm” to one of “how best to represent an algorithm”.

The world of computer science has a plethora of ways to describe system behaviour with Unified Modelling Language (UML) being the most widely accepted of all of these. For the most part, this language covers the majority of scenarios in order to build a system. What it doesn’t supply easily is a way to represent algorithmic formulae. Instead, these are usually represented in a form of pseudo-code, for example:

if age is less than 16
	I must go to school and learn math
else
	math is optional

In most cases, this is enough to represent the solution being proposed but as algorithms become more complex, this isn’t necessarily enough to clearly illustrate the condition being described.

A good example of this would be if we wished to represent a way of determining if two characters in a string were the same distance apart alphabetically as they are within the string. For example, within the string ‘NYPVTTMZFPK’, the character at position 4 (V) is 4 characters from the Z, likewise the M is 3 characters from P.

If this was to be written as a scenario, it would take the form of:

Given I have message c
When I compare subsequent characters
And the distance of the characters are of an equatable distance
And the character distance is alphabetically equivalent
And the character has not previously been solved
Then I solve the character with the next unused alphabetical instance

Simple right?

Hmm, maybe not…

pseudo code

Within pseudo-code, this would be expressed as:

FOR character IN cipher
	FOR another IN cipher
	    IF another position IS GREATER THAN character position 
	    AND another position in alphabet MINUS character position in alphabet IS EQUAL TO another position MINUS character position
	    AND another position in message is empty
	    THEN message AT another position EQUALS message at character position

Already we can see that for what is seemingly a basic comparison (check two positions, if they are the same, write the next alphabetical letter), the algorithm has become fairly complex.

Propositional logic

Now let’s have a look at how this might be expressed mathematically using propositional logic by first looking at what is happening within the scenario definition above and working backwards.

In the last line we know that we are doing an assignment to a message so this is written as mi =. The line above states clearly that the character must not have been solved before so this takes the expression ¬mi leaving our expression as mi = ¬mi (¬ is the boolean not operation in mathematics).

Next we look at line 4 which states “And the character distance is alphabetically equivalent”. This line indicates we need to solve line 3 first which in turn requires we solve line 2.

First looking at line 2, we get the character indexes ci and cj. This is determined by the fact we are looking at subsequent character indexes (implying a comparison on two elements). Theoretically we want to compare the second item against the first in sequence so this part of the expression becomes cj > ci. Writing out the expression from lines two and three now we get the formula
c1partial

We can now solve line 3 of the algorithm in the same way as we have solved for c to leave the right hand side of the expression as
c2partial
Finally we can put the whole expression together leaving us with

c3final
This final formula tells us to assign to mi if and only if mi has not been assigned, and cj is greater than ci, and the difference between ci and cj is equal to the difference between ai and aj.

Solution

If we now process through the cipher-text, N and P are two letters apart in the cipher-text and two letters apart in the alphabet so we fill these with A indicating that these are a potential match. Now we start again from P and look for another sequence which matches but find there isn’t one so we go back to the start and choose the next unsolved letter (being Y) of which there are no matches within the sequence.

Because P has already been solved, the equation tells us to skip this letter and move on to V which matches on Z, likewise M matches on P so we fill these with B and C respectively to leave us with a partially solved message as:

NYPVTTMZFPK
A_AB__CB_C_

Conclusion

Whilst the output of this algorithm may not seem to achieve very much, the whole point of the article is to demonstrate how math can be used to articulate an algorithm in a more understandable form than pseudo-code or English representations directly. Using math we can recognise where an algorithm requires a loop, where comparisons are required and where conditionals should be stated. Whilst this is a simple example, it demonstrates in one line what pseudo-code required six to demonstrate.

To my mind, however theoretical, a complex algorithm should always have a propositional formula to accompany it. This makes it easier to understand what the algorithm is doing and to work out how many items are being handled by the algorithm. As we develop more complex algorithms, it can be used to detail how many sets are required, how many loops are happening within it, how many conditions are being solved and where the edge-cases may lie. After all, a well written Mathematical formulae is, in principle, a form of pseudo-code in itself.

Symbols

The symbols used in equations within this article are:

Symbol Description LaTeX command
If and only if If and only if \iff
Logial not Logical not \neg
wedge Logical and \wedge

Leave a Comment