3 Examples of How Mathematics Can Help in Programming

It often seems that mathematics goes hand in hand with programming — you need to know one to be good at the other. But is it really the case? Well, it strongly depends on the domain you are working in — you probably need matrix multiplication, vector spaces, projection, and algebra if you are dealing with graphics and game development, good knowledge of statistics if you are a data scientist, algebra for ML problems and that is just to name a few.

But in general (at least from my limited experience) the average programmer uses a little arithmetic and some basic algebra.

But this does not mean that knowing mathematics will not help you in your day-to-day job and I will try to prove it with three simple examples.

1. Boolean algebra

As a programmer, you should be familiar with booleans and if statements. Apparently, knowing a few simple rules called De Morgan’s laws might save you time when writing, refactoring, or trying to understand more complex cases.

Let’s start with an example. Imagine you came upon the expression like this:

not(not A or not B) and not C and not D and not E

And you need to understand it, or better — rewrite. I am sure you could do it without knowing any logical rules, but I am also sure it would take some time. But rewriting this expression is pretty easy if you know De Morgan’s laws:

• The negation of a disjunction is the conjunction of the negations.
• The negation of a conjunction is the disjunction of the negations.

Or in programming:

• not (A or B) = (not A) and (not B)
• not (A and B) = (not A) or (not B)

So now our expression can quickly and with confidence be rewritten as:

A and B and not(C or D or E)

Another advantage of using de Morgan’s laws, besides making code look cleaner and more readable, is to bypass short-circuiting (for !A || !B most of the languages stop evaluating if !A is true because it then doesn't matter what !B value is, which might be important if A and B are functions) and saving a CPU cycle or a few if you invert one value instead of two (e.g. !(A or B) instead of !A and !B).

2. Graph theory

As Steve Yegge put it in his blog post “Get that job at Google”:

Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship, so it’s about a 50–50 shot that any interesting design problem has a graph involved in it. Make absolutely sure you can’t think of a way to solve it using graphs before moving on to other solution types.

Although this might be a bit of an exaggeration there are indeed a lot of problems that might be, and are, solved using graph theory. Almost every time you google something, stalk people on Facebook, or are using a map app to find the fastest or shortest route, the graph theory is in action.

I will not go into the graph theory itself as there are plenty of wonderful resources out there (for example Introduction to Graph Theory: A Computer Science Perspective by Reducible) but instead will start with the practical example.

Imagine you need to implement Rock Paper Scissors Lizard Spock to play against the computer (because that’s indeed the kind of problem programmers deal with daily). The rules are:

“Scissors cuts paper, paper covers rock, rock crushes lizard, lizard poisons Spock, Spock smashes scissors, scissors decapitates lizard, lizard eats paper, paper disproves Spock, Spock vaporizes rock, and as it always has, rock crushes scissors.”

The initial instinct would probably be to write something like this, with plenty of if’s:

if computer_action == "scissors" & user_action == "paper":
    print("You loose")
elif computer_action == "rock" & user_action == "paper":
    print("You win")
elif computer_action == "rock" & user_action == "lizard":
    print("You loose")
...

It would take 21 conditionals (20 for win-lose situations and 1 accounting for 5 tie situations). Sure, you could optimize it by nesting some of the cases:

if computer_action == "scissors":
    if user_action == "paper" or user_action == "lizard":
        print("You loose")
    else:
        print("You win")
if computer_action == "paper":
    if ...
...

Although this looks a bit better, what if you need to simulate a game with 7, 51, or 101 characters?

That is where “thinking graphs” (and knowing some modular arithmetic) can help (*) :

First, let’s visualize the game as a directed graph where edges are characters and vertices connecting them are directed so that the winner of the match is indicated by an arrowhead pointing its way.

Although this representation looks less complex than the rules in plain English or a bunch of if statements it is still not very mathematical. Hence we will replace characters with the numbers, i.e. rock — 0, lizard — 1, Spock — 2, scissors — 3, and paper — 4.

Now we need a way of representing matches. This can be done by subtraction — e.g. if your opponent (in this case — computer) chooses Spock (2) and you choose paper (4) we will represent this match as 2–4=-2. Note that this representation makes sure that there is a distinction between players’ choices —i.e. if the computer chooses paper (4) and you choose Spock (2) the match will be represented by the opposite number 4–2=2.

If we will now look closely into the numbers by which matches are represented we will notice that modulo 5 (mod5) of every match yields something interesting — every match you win results in an odd number, while for every match won by the computer the result is an even number.

(computer - you) mod5

So after representing the game as a graph and using some modular arithmetic we can rewrite our solution with only a few lines of code:

result = computer_action - user_action
result_mod = result % 5
if result_mod == 0: print("It's a tie")
elif (result_mod)%2 == 0: print("You lost")
elif (result_mod)%2 == 1: print("You won")

* This approach only works if the following tournament graph is not even and k-complete.

3. Mathematical induction

Mathematics is often associated with a way of thinking — i.e. people with mathematical (or, I would argue, with any scientific background) are expected to think in a more structured, analytical way, therefore be good problem solvers. But how this skill can be quantified? Is there something specific that can be learned to apply in an everyday job?

Mathematical induction is a mathematical proof technique used to prove that a statement P(n) holds for every natural number n = 0, 1, 2, 3, . . .

The process of proving something using a mathematical induction is fairly simple and consist of three main steps:

1. Defining a base case that proves the statement for initial n without assuming any knowledge of other cases.
2. Assuming statement holds for n=k.
3. Showing that it also holds for subsequent step n=k+1 (using assumption made in step 2).

Let’s go through a simple example and prove that 1+3+5+⋯+(2n−1)=n² is true for every n∈ℤ+ (i.e. for every positive integer).

Steps:

1. The base case: n=1 (since we are prooving this for n∈ℤ+) is indeed true:

2 ⋅1–1 =1²

2. Assuming statement holds for n=k: let the result be true for n= k, that is

1+3+5+⋯+(2𝑘−1)=𝑘²

3. Showing that it also holds for n=k+1:

1+3+5+⋯+(2𝑘−1)+(2(𝑘+1)-1)=1+3+5+⋯+(2𝑘−1)+(2𝑘+1)=(𝑘+1)²

since by our assumption 1+3+5+⋯+(2𝑘−1)=𝑘² (see step 2) we can rewrite this as

k² + (2𝑘+1)=(𝑘+1)² which is indeed true.

So this proves that the equation holds for any positive natural number because it holds for 1, and since it holds for every k+1, it, therefore, holds for 1+1=2, then 3 (2+1), 4, and so on, for all positive integers.

What we did here was expressed perfectly by Tristin Cleveland:

Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step).

How this relates to programming? Well, as stated by Robert Harper in “Programming in Standard ML”:

when programming recursively, think inductively

Let’s go through the recursion example — find a sum m for

One possible solution for it (the code is extensively verbose for explanatory reasons):

def recursive_sum(m):
    if m == 0: 
        return 0
    else: 
        k = m*(m+1)/2 
        k_minus_one = recursive_sum(m-1)
        return k + k_minus_one

Which can be broken into three steps:

1. Establishing a base case (0 in this case).
2. Finding value for m=k.
3. Using value k from step 2 and consecutive member k-1 of the equation (it is k-1 instead of k+1 since we are moving in the decreasing order) to get the final answer.

Since this is a fairly simple example it might seem that mathematical induction is of no help here. But “thinking induction way” to implement recursion can help organize thoughts to solve more complex cases.

So after all — do programmers need math? Although it depends on the domain, I think in most cases the answer is no. Nevertheless, as we showed earlier, knowing it might make your life easier.

So watch that math video Youtube keeps suggesting because you never know when it might help.

Further readings that I discovered when researching for this story but did not include:

• Project Euler — set of computational problems for people interested in mathematics and computer programming.
• Mathematics in Computer Science Journal.