I want to call out: <i>But sometimes the opposite happened. Glancing through the results of an algorithmic run showed a pattern I wasn't aware of. Taking that back to paper allowed me to make further theoretical breakthroughs that sped up runtime by additional orders of magnitude.</i><p>I worked with some mathematicians on an online load balancing problem, and we were trying to model the behavior of our connections. I did not have the mathematical chops to come up with the ideas for the models. But I was running the experiments and diving into the data and figuring out where and why our models broke, so I could reason about the behavior we were trying to model in the same way that I can walk around my apartment with my eyes closed.<p>Having this level of intuition of the behavior we were trying to model was invaluable during discussions. I may not have been able to come up with the mathematical models, or even understand them completely from first principles, but once they were explained to me, I could give instant feedback on how well it might work based on my understanding of the data.<p>Short version: know your data.
Excellent write-up!<p>I don't think enough people appreciate (or understand) your point 4. I am fairly good at algorithmic optimizations and pretty good at your implementation optimizations, but I do not have the math to do much mathematical optimizations, so spending any time on these kinds of problems gives me a visceral understanding of your point 8.<p>But I've talked to too many people who don't understand that such problems exist, and therefore don't see the point of <i>any</i> optimization (and then wonder why others consider their products to be hideous monstrosities), or believe that micro-optimizations or algorithms are the best you can do. In reality, all three are closely tied together and, in fact, applicable to almost any problem.<p>Your points 6 and 7 could be elaborated more. Or at least stamped on the foreheads of some educators of my acquaintance. One of the things I learned from what math education I have had is that you won't really understand something without seriously using it.<p>I hope that this was actually part of your PhD research, or if not that it didn't delay you too much. And if you're out in the "real world", all you have to do to succeed is to forget you ever heard of your point 10.
OK, now you've set aside that problem, here's another:
<a href="http://en.wikipedia.org/wiki/Golomb_ruler" rel="nofollow">http://en.wikipedia.org/wiki/Golomb_ruler</a>
Quite similar in its maddening simplicity.
I was bored, so I wrote a short visualisation of the solution in d3:
<a href="http://jsfiddle.net/vdNnJ/" rel="nofollow">http://jsfiddle.net/vdNnJ/</a>
>As I started writing code for this problem, I found out I could work on it for hours on end without distraction, quite unusual for me. I chalk this up to a tight feedback loop. Have an idea, implement it, get back a number. Think of ways to improve the number, start the cycle all over again. This is a cycle I would run dozens of times a day. Obviously more fundamental ideas would take more time to see the fruits of, and that's when I actually lost focus, but when the brain has been rewarded so richly with small cycles, it can afford to go a bit longer without reinforcement. This tells me that A/B testing or a similar numeric optimisation area would be quite motivating to me and I've made a mental note to go into this in the future.<p>I've had this experience before. I have a severe problem of not being able to focus on anything, and it feels great to be working on a problem like this. I'd love to find a problem like that again.
For more stuff like this, check out Love and Math (<a href="http://www.amazon.com/gp/product/0465050743/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0465050743&linkCode=as2&tag=benryyipcom-20" rel="nofollow">http://www.amazon.com/gp/product/0465050743/ref=as_li_ss_tl?...</a> , disclaimer: affiliate link). It's a great book I'm just in the middle of that talks a little about doing maths and the mindset and heart behind it. Some of the OP's observations are echoed in the book and it's nice to have the OP and the author of Love and Math give words to my own obsession to problems I've tackled and failed to solve.
"Of course, I also cheated. I realised that my code spent a huge amount of time counting the set bits on a byte. I could implement that on my side, or get a CPU that implements that as a single instruction."<p>Why not use a lookup table to memoize the results? There are only 256 possible cases for a single byte. Or is this still considerably slower than a single processor instruction on the i7?
Too bad these problems were solved: they are perfect candidates for automatic rewards using bitcoin's scripting language (see <a href="https://news.ycombinator.com/item?id=6997020" rel="nofollow">https://news.ycombinator.com/item?id=6997020</a>)
Haha before I clicked I knew it would be that goddamn 17x17 problem. Hadn't heard that someone had solved it, but it will be interesting to read how they did it.