A brief study in optimization (Part 1)

For this series we're going to look at writing, then optimizing an algorithm for generating triangle square numbers.

Wait, what is a triangle square number?

To understand what a triangle square number is, we first need to look at what a triangle number and square number are. Triangle numbers are numbers of the form 1 + 2 + 3 + ... + n. They have a neat property in that if you have a triangle number of things you can arrange them into an equilateral triangle. As in -

A square number is just a perfect square, like you learned about all those years ago in math class. A square number can be represented mathematically as n * n (or n²). Similar to the triangle number, if you have a square number of objects, you can arrange them into a square.

A triangle square number is a number that's both. Like 36, which is 6 * 6 so it's a square number, and 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 so it's also a triangle number.

Ok, so what does that mean to me?

Nothing. It's just a basic example we can use to look at algorithm design, and an iterative process for improving it. Also, stop being so judgemental, you're a figment of my imagination.

Point taken. Where do we start?

Next time we're going to start with the naive implementation, then work forward towards a better solution. Hopefully you learn something along the way.

* I stole the whole "arguing with an imaginary foil" thing from Ken over at Popehat. He's better at it than I am. No, I have no shame.