« ""
"" »
"The power of algorithms"

I had a bit of a tricky thing to solve over the summer.

I had to perform 100,000,000 calculations, each of which took nearly a second, and I didn’t have 1,150 days spare, unfortunately.

No problem – throw it on a big beasty computer cluster (60 CPUs), do some multi-threading magic, and realise that actually the solutions are symmetrical so there’s ‘only’ 50,000,000 to do – there you are, job done in about 10 days (including faff time). I was quite pleased with this.

However it turns out that there’s a much better way to do it.

Tweak the algorithm a little, and instead of needing to do 10,000 x 10,000 calculations that each take a second, you can do just 10,000 calculations that each take a second, and get the 10,000 results for each of those for ‘free’. Well, there’s a little bit of magic to weave, but we’re talking 1/250 of a second for each.

So suddenly, instead of taking 10 days on a 60 processor brute, you can do it 5 days on a single desktop computer, or overnight if you hijack 5 office computers. And this is without taking advantage of the symmetry.

I’m a little embarrassed I didn’t think of this over the summer – sometimes big isn’t always beautiful, and raw power is not (always!) the answer to thorny problems!!

W Wordpress