Comment by JakDrako

That's a fun puzzle. I converted the code to C# and managed to get a 20x speedup. Not sure how the code would fare in Java, but I presume that things that are slow in C# are probably also slow in Java.