Consider a really cool computational problem (project euler problems are the perfect candidates). To solve this problem, naive brute force won't work. There are two paths here.
I can keep the algorithm fixed and write heavily optimized code. This could be taking full advantages of the language features and/or compiler optimizations but no thought to the actual mathematics behind the problem. Just naive brute force in C/C++ for example.
I can find a better more efficient algorithm but then just implement it naively. Like not taking advantage of vectorized operations in MMA or MATLAB.
Zigzagging through both steps, I can optimize the algorithm and implement it efficiently in whatever language, taking full advantage of its strengths. This of course is the best desirable outcome where the most amount of learning happens, not to mention the crazy speedups.
I want to do this with MMA. My question is, what is the best way to do this on Mathematica StackExchange?
Several thoughts,
- I want to do this for pedagogical reasons. One for myself, as I want to learn more about MMA, its features and strengths. Second, for my students, colleagues, and fellow researchers. If I have examples, I can point and say "see, you need both algorithmic and implementation optimizations and look at the crazy speedups possible".
- I am not looking for PE solutions. I will have solutions for all of the problems before I post them here. I can easily provide proofs, if needed, without actually giving away the answers here.
- I will not be asking for algorithms. I will provide the algorithms and an implementation in MMA and then ask if the code can be made any faster.
- I know that code-complete answers are okay here. We even have a project euler tag. I can easily change the problem parameters before posting it here if it makes the community feel more comfortable.
- The criteria, in order of preference, will be
- Runtime
- Kolmogorov complexity
- Memory usage
First, we want the code to be fast. If we can have a terse code in MMA that is fast, then even better. We don't really care about RAM usage but if it can be reduced then okay.
For example, I have a problem P. Algorithm A1 is just brute force. Algorithm A2 is an improved algorithm over A1. Algorithm A3 is the most efficient I can think of. Now,
- A1 can be implemented in MMA in a very naive and slow manner. Call it M11. M12 is a better implementation and M13 is the fastest we can get. A1 is still naive but our run time has gone down from eight hours to fifteen minutes.
- Similarly with A2. We went from fifteen minutes to about thirty seconds.
- Similarly with A3. We went from a minute to a few microseconds.
So that it is easy to see how both factors affect the speed.
Is it better to ask separate questions for each algorithm A1, A2, and A3? Or should I ask in a single post where each answer can address one single algorithm, but everything related to the problem is contained in a single thread, like a community wiki? Or some other format entirely?
