Approach to simplifying an algorithm

For completely random reasons*, I wrote some code that calculates and displays the following expression:

P=1*(2+2)(3+3+3)(4+4+4+4)..(n+n...…

Which is equivalent to (n!)^2

The version I wrote (listed below the line) isn't terribly efficient; especially not in how it calculates the inner product.

How should I go about simplifying the algorithm so it will operate faster and be more easily understood?

And yes, I know I should use something other than int for the variables. That aspect of my code isn't as interesting as re-working the algorithmic approach.

* In the spirit of full disclosure this off-topic question sparked my working on the code

int sequence(int n)
{
int i, accum, prod, j;

accum = 1;
for (i = 2 .. n)
{
prod = i;
for (j = 1 .. i-1)
{
prod += i;
}
accum *= prod;
}
return accum;
}
• questions on how to improve a working piece of code should go to codereview.SE Apr 23 '13 at 14:48
• @ratchetfreak - explicitly looking for answers regarding the algorithmic approach and not a code-review. Pseudo-code would be perfectly fine within an answer. I can already see things such as squaring the inner value (p) instead of looping and summing it. I'm looking for approaches to improving algorithms not just fixing this algorithm.
– user53019
Apr 23 '13 at 14:51
• Then I'll contribute a response that I hope will answer your question.
– Neil
Apr 23 '13 at 15:20
• exp(fact(n),2) seems pretty clean. To generalize, optimize your algorithms by having someone else already have done it.
– psr
Apr 23 '13 at 16:49
• Migrated by accident. This has kind of been fixed but I need people to repost answers as I can't undelete those until Code Review rejects this. Sorry. You may mock me mercilessly if you so desire.
– user28988
Apr 23 '13 at 18:12

How it goes for me usually is to first write code that literally performs the calculation or carries out some operations in the obvious non-clever way. Then I look for patterns where I can substitute "better" code.

Some red flags or "code smells" I see in the example code:

1. There's one 'for' loop inside another. If we're looping over i and j, maybe we could consider the sum i+j and difference i-j, with appropriate limits. Very handy in quantum mechanics. Probably nonsense for the typical business app. There may be other ways to index things. Just a simple swap of inner/outer loops might lead to insight although probably not in itself improve speed.

2. Again, with nested loops. maybe there's a clever way to look at the two-dimensionality as a one dimensional problem. Precalculate something, perhaps. In the course of trying to improve the code, I may have an insight that lets me change the math or algorithm at an abstract level.

3. Look for obvious or almost-obvious math simplifications. (4+4+4+4) of course is 4*4=4^2, and so for the general term I'd use n^2. Right there, we lose a loop. After that, recognizing the formula as computing 1*2*3*4*... is just n!, I will choose to use a lookup table. If we weren't adding or multiplying but using trickier things like Legendre polynomials, root-sum-square, or using noisy experimental data instead of nice neat integers, then more sophisticated math is needed. But then I work in physics and graphics not business, so most programmers in general may not need to get so deep into such things.

4. Plucking out things that are done over and over. In your example we want to do "for n times: add n to a running total" and that could be put into a black box function or object or something. Suppose your "4+4+4+4" and the like weren't just numbers and simple addition but something fancier such as images or audio tracks, and digital filters, FFTs, and modulators. Shovel it into a black box. It may not reduce the big-O complexity right away, but the contents of that black box could always be studied and optimized later. Hopefully we'd reduce its big-O growth but if not, we're likely to find some optimization to reduce the coefficient. (E.g. it still helps to change an algorithm's execution time from 8*n^3 to 4*n^3.)

Sometimes, while doing the optimization work and waiting for compiles, I may websurf for other attempts to solve the problem, and find a whole different formula or method of solution, something so good that my algorithm can be ditched, never mind how it's implemented.

If there were an algorithm that could optimize algorithms, we programmers would all be out of a job. However, we already perform small optimizations in compilers. Small optimizations can be made which do not change the intended meaning of the operation, however our limitation is precisely that: intended meaning. For instance, if we knew that a number is always positive, we could replace multiplication by 2 with bit shifting. However, when we are left with signed integers, even if they are used purely for positive numbers, the compiler cannot make these sorts of assumptions.

The real trick is understanding what the algorithm is supposed to do. If you understand that, then you realize that an algorithm is not about the steps it takes but about the end result. Without this, there is very little hope to improve on an algorithm. For example, if you give your friend instructions for getting to your house and you don't see the bigger picture, you may never realize that you made your friend take a longer route to get there.

So how do you define the context of an algorithm? It boils down to input and output. If you can make mathematical assumptions on the input and describe the expected assumptions on the output, then an algorithm is simply a mathematical proof in its purest form, describing all the steps you'd need to perform in order to guarantee that for the given input, you receive the expected output.

Each step is transformed into an equivalent mathematical transformation (for instance, performing a loop which accumulates values could be thought of as a sum operation). Once you have this, you can not only begin to prove soundness and correctness but you can also simplify much like you would combine like terms in a mathematical formula.

Of course this is all very theoretical and ongoing, but the idea is that we can one day write compilers which can not only tell you that your algorithm won't work as expected, but also on what line and how to fix it as well as any optimizations which can be made to improve performance (this would likely be done upon automatically).

Unfortunately we are not yet at this stage, but I hope to see it sometime in my lifetime anyway. I hope that answers your question.

• To your last comment, I think existential type systems are currently the largest hope trying to do precisely that; define the intent of things rather than just the process Apr 23 '13 at 16:00
• @JimmyHoffa I think that requires rethinking a bit how we program in general, but I think we'd find that the advantages far outweigh the disadvantages to doing without.
– Neil
Apr 23 '13 at 16:06

n! is an O(n) operation. n^2 (square) is O(1).

Why not calculate the factorial, and then square it, as implied by your (n!)^2 remark?

• It appears that the question is about recognizing ways to improve a given algorithm, not about calculating values for that particular expression. The expression is just an example to study. Apr 23 '13 at 22:01

Can't you just square i in the inner loop, rather than multiplying-by-adding?

EDIT: It ain't rocket science.

(3 + 3 + 3)

equals

3 * 3

It's not clear what you mean by "improving the algorithm".

FURTHER EDIT: Since you clarified the question, let me try to answer it. Let me make a distinction between 1) algorithms (1-page programs), and 2) programs (1000 LOC and up).

1. Algorithms. First get familiar with searching, sorting, and big-O. The way these work is by executing a series of decision points. At each decision point, ask what is the probability of taking each branch of the decision. If those probabilities are very much unequal, cycles are being wasted, big time. So if your inner loop is basically for(i=0; i<n; i++) what's the probability that i<n? Almost always almost 1, right? That's a red flag. So the difference between, say, linear search and binary search, is whether or not the probabilities are very different or almost the same at each decision point.

2. Programs. This is a very different subject. Here the issue is that due to the way you or I or someone else designed the program, it contains dumb stuff that you would never guess is in there. The bigger the program, the more dumb stuff is hiding in it. The way to clean it out is to expose the biggest stuff first. I do it by random pausing, as in this example. It is a 3rd cousin to profiling. People will tell you "use a profiler", but what they won't tell you is how much speedup they got that way. That example shows a 43-times speedup. The secret is after you find and fix the first problem, find and fix the second, and so on until you truly can't find any more. What happens is after you fix each problem, the remaining ones become larger as a percentage, because the total time has become smaller. In this way, you can keep squeezing it until you've got it down to the absolute bare minimum.

• sure, but I'm looking for approaches to improving the algorithm. So would the only step from this sample be "look for redundant operations and simplify them?"
– user53019
Apr 23 '13 at 14:57
• Apologies if I wasn't more clear. I'm looking for generalized approaches to examine an algorithm and identifying areas to improve the algorithm. One suggestion would be to square the values instead of looping & summing. Another suggestion would be to calculate the factorial and then square that. The crux of my question is how do I identify those types of suggestions.
– user53019
Apr 23 '13 at 19:51