A quick algorithms problem

Here’s a quick little problem to try. My solution (in python) is below but I’d love to see different ways to solve it.


Assume you have a list of 8 items numbered 0 through 7, however they are in some random order.  You would like to encode the order they are in using the least number of bits possible.

There are 8! possible options for how they are ordered, which could conceivably be numbered 1..40320.  This could then be encoded as a 16-bit int.

Find an efficient way to determine the correct encoding for a given list, and vice-verse to determine the ordering for a given encoding.


def decode(x):
    digits = [0,1,2,3,4,5,6,7]
    values = []
    for modval in [5040, 720, 120, 24, 6, 2, 1]:
        index, x = divmod(x, modval)
        digit = digits[index]
    return values

def encode(values):
    result = 0
    digits = [0,1,2,3,4,5,6,7]
    for mulval, value in zip([5040, 720, 120, 24, 6, 2, 1], values[:-1]):
        index = digits.index(value)
        result += mulval*index
    return result

for x in range(8*7*6*5*4*3*2*1):
    values = decode(x)
    xx = encode(values)
    assert x == xx

Trigonometry: The study of… circles?

Trigonometry, we are taught, is the study of triangles. In particular, right angled triangles come in for much attention, as they happen to have particularly nice properties. Pythagoras’ theorem relating the lengths of the sides of a right angled triangle could make a robust claim for being the most famous formula in all of mathematics.

Pythagoras' Theorem

Source: Pedro Sanchez

Pythagoras’ theorem is great; it’s easy to remember, it’s easy to compute, and it’s clearly useful. Most people don’t have a problem with this first foray into trigonometry. But the world of trig beyond Pythagoras quickly descends into a mess of sines, cosines, thetas and other confusing terminology. Not surprisingly, students resort to rote learning of formulae and rarely have a concrete understanding of what it is they’re doing.

As students progress, more trig functions are introduced and more identities committed to memory. HSC students across the state can be found before exams, huddled around cheat sheets jam packed with symbols and equations, desperately trying to load as much into short term memory as possible, hoping that when they splurge their “knowledge” onto the exam paper it will come up trumps.

Even as a maths nerd, I’ve always struggled with trig. I think this is largely due to the emphasis on remembering specific formulas and identities (SOHCAHTOA anyone?) without delving into the underlying geometry to understand where these relationships come from and how they’re related.

Today I’m going to give a brief refresher course on how trig is currently taught, so you can relive the confusion of your childhood. Once I’ve broken your souls, I’ll build them back up by presenting all the trig functions as they should have been taught (IMHO, IANA maths teacher, YMMV, etc).

Learning trig the hard way

To introduce students to trig, we start with a right angled triangle. One of the angles is labeled \theta, and the sides are labeled “adjacent”, “opposite” and “hypotenuse”.

We then define three functions,

\sin(\theta) = opposite / hypotenuse\\
\cos(\theta) = adjacent / hypotenuse\\
\tan(\theta) = opposite / adjacent,

and tell students that these functions are important, so they must remember them. In fact, remembering these equations is so important that we give them an acronym that will stick with students for life: SOHCAHTOA. I’m not going to lie, I used this acronym to write the equations out in this post.

In the fullness of time, it gets revealed that the full names for these functions are actually “sine”, “cosine” and “tangent”, although the etymology is not delved into. “Aren’t tangents related to curves?”, a bewildered student might ask. “Yes, but those are different, this tangent is the one about triangles”, the muddled teacher might respond.

And so from the simple right angled triangle we get this trio of function; sin, cos and tan. It’s not really clear why these functions are important, or how they’re related to each other, just that they can be used to “solve triangles”. Once the students have really got the hang of doing that, they get introduced to three new functions:

\sec(\theta) = \frac{1}{\cos(\theta)}\\
\csc(\theta) = \frac{1}{\sin(\theta)}\\
\cot(\theta) = \frac{1}{\tan(\theta)}

These are the (multiplicative) inverses of the normal trig functions (not to be (but often) confused with the inverse trig functions). It’s again not clear why these functions are important. Or why we need new names for these things. Or where the names came from. Or what they’re useful for. But they let us write down many more formulae! And of course, the students get to blindly learn many of these new formulae.

What have we learned here?

So, let’s summarise the take home message of high school trig:

  • Triangles
  • Memorise lots of formulas

Or something like that, the students are really sure. It’s no surprise that for many students this component of the curriculum is a baffling speed bump which needs to be overcome rather than understood.

But they are earnestly assured that trigonometry is important, that they’ll need it at university if they want to study science, economics, or engineering. How can something as demonstrably tedious as the study of triangles be useful in such a broad range of contexts? The answer is quite simple: it’s not.

Sure, triangles show up here and there when doing things like architecture or surveying, but aside from these fields which use lots of straight lines in a plane there’s just not that much of a demand for the services of this simple geometric shape.

It’s all about circles

The reason we see trig show up in so many fields of science and engineering is that trigonometry is not actually the study of triangles, it is the study of circles.

Allow me to repeat that so it really sinks in.

Trigonometry is the study of circles.

And circles show up everywhere! They are the simplest of all the shapes, yet the most powerful. Any system which has repeating motion can be described using circles, which leads us to have an understanding about the physics of everything from a pendulum to light. It tells us how electrical circuits work and how the waves in the ocean behave. In fact, one of the most fundamental ideas in physics, that of quantum mechanics, is based on the idea that “stuff” behaves like an oscillating wave, and can therefore be described using circles.

This is the reason why trigonometry is so important, and shows up in so many places. It is because circles show up everywhere, and trigonometry is the study of circles!

“OK, but hold on, didn’t we get the trig functions by looking at triangles and all that SOHCAHTOA stuff?”.

Sure, we did, and that was bad. It wasn’t wrong, because that’s a perfectly valid way to define the trig functions, but it turns out there’s a better way to define them. One that involves circles. One that fundamentally makes much more sense. One that will let you intuitively understand how these functions behave. One that will let you see the links between the trig functions and understand how they might be applied to problems involving circles (i.e. interesting, real world problems).

Learning trig the right way

So, let’s start with the simplest of all circles; a unit circle centered at the origin, O, of a cartesian coordinate plane. Now let’s draw a line from the origin to a point P on the circle, forming an angle \theta with the x-axis. Now, draw one half of a tangent line from P to the x-axis. Label the intersection with the x-axis T. Finally, drop a perpendicular line from P to the x-axis. Label the intersection the x-axis S. You should end up with a diagram which looks like this.

Now, based on this circle, we can define some functions.

\sin(\theta) = PS\\
\tan(\theta) = PT\\
\sec(\theta) = OT

These are the three fundamental trigonometric functions, and we can see that they all come from the circle. We also get another neat bonus. Notice that \tan(\theta), the tangent function, is actually related to the length of a tangent! Also, \sec(\theta), the secant function, is related to a secant! These functions have these names for a perfectly good reason, but you only get to see this meaning when you define them in terms of a circle. The word “sine” has a complicated origin but can be traced back to a Sanskrit word for “half-chord”. This is exactly what the line PS is, but you need a circle to have a chord.

If we now perform a “complementary” construction, focusing on the y-axis, we get three more functions. Extend the tangent to intercept the y-axis and label the intersection point T^\prime. Drop a perpendicular from P to the y-axis and label the point S^\prime. Your diagram should now look something like this:

We can now define three “complementary” functions,

\textrm{cosin}(\theta) = PS^\prime\\
\textrm{cotan}(\theta) = PT^\prime\\
\textrm{cosec}(\theta) = OT^\prime,

or \cos(\theta), \cot(\theta) and \csc(\theta) as they are more commonly known. These co-functions correspond directly to the fundamental functions in an obvious and simple way. Sine is the perpendicular distance to the x-axis, cosine is the perpendicular distance to the y-axis. Tan is the tangent distance to the x-axis, cotan is the tangent distance to the y-axis. Sec is the distance along the x-axis to the tangent intercept, cosec is the distance along the y-axis to the tangent intercept.

There are certain neat symmetries which become really obvious when we have this picture of the trig functions at our disposal. For example, if \theta = 45^\circ then we have a symmetric picture and we’ll get

\cos(45^\circ) = \sin(45^\circ)\\
\cot(45^\circ) = \tan(45^\circ)\\
\csc(45^\circ) = \sec(45^\circ).

This symmetry about 45^\circ also tells us that we can get a graph of a co-function by flipping its fundamental function around the line \theta = 45^\circ.

In fact, almost all of the interesting properties of the trigonometric functions shine through when we consider circles, while remaining hidden and obscured if we just think about triangles. This is all due to the simple fact that trigonometry is really the study of circles, not triangles.

It’s time for a change

What can we conclude from this change in perspective on trigonometry?

Well, we should not be teaching students about trigonometry using triangles. It is a confusing abstraction with few real world applications. Indeed, there are better systems for solving geometric problems involving triangles, which do not rely at all on the trigonometric functions.

Trigonometry in the real world is all about circles, and we do a disservice to students by pretending that it’s all about triangles. By teaching trigonometry based on circles we can provide students with a deeper understanding of the fundamental nature of the functions involved, while preparing them to use these functions effectively in their future studies.