Wednesday, September 27, 2017

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 n2). 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.

No comments:

Post a Comment

All comments are moderated. I have a life, so it may take some time to show up. I reserve the right to delete any comment for any reason or no reason at all. Be nice. Racist, homophobic, transphobic, misogynist, or rude comments will get you banned.

Programmer vs Software Engineer: The Interview

A common question presented in interviews for developer positions goes something like this: Given an array of numbers, write a function th...