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;
}

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:

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.
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.
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.
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.

It seems to me you have answered your own question.

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?

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).

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.
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.

Filed under: softwareengineering - @ 11:16

Thẻ: algorithm-analysis, algorithms

Thiết kế website giá rẻ

Danh mục

Approach to simplifying an algorithm