strength reduction (idea)

Strength reduction is the process of simplifying a program by replacing an operation in a loop (or recursive function) with a simpler operation using state from the previous loop iteration (or function call).

The canonical example is array indexing. Consider this snippet of C code:

struct Person {
  char *name;
  unsigned age;
  unsigned height;
};

unsigned total_age_of_everyone (int n_people, struct Person people[])
{
  unsigned total = 0;
  unsigned i;
  for (i=0; i<n_people; i++)
  {
    total += people[i].age;
  }
  return total;
}

Naively, the array address in the loop must be calculated by a multiplication: the address required to access people[i].age is:

	people + i * sizeof(struct Person) + sizeof(char*)

However, on most machines, that multiplication would take a while to calculate. At least a couple ofcycles, which is annoying since the rest of the loop probably doesn't take much more than that to execute.

If our compiler is clever enough, and most of them are, it'll spot that there's a faster way to calculate that address. Between each successive iteration of the loop, that address increases by a nice, constant value: sizeof(struct Person). So instead of performing a slow multiplication, the compiler can just add sizeof(struct Person) to the value that it calculated on the last iteration.

The code the compiler produces would be equivalent to the code it would produce for:

  unsigned total = 0;
  unsigned i;
  unsigned *age_pointer = & people[0].age;

  for (i=0; i<n_people; i++)
  {
    total += *age_pointer;
    age_pointer = (unsigned *) ( (char*) age_pointer
                                         + sizeof(struct Person) );
  }
  return total;

Note that we've introduced a loop-carried state element (person_pointer) that wasn't there before, and that where the loop previously had an expensive multiplication, it now only has an addition (which, on most architectures, can probably be merged with the load operation, saving even more on complexity).

This strength reduction can be applied to any function which can be expressed as a simpler, iterative function. For example, to compute a power series, we must calculate xⁿ (which can be quite expensive to calculate) for all values of n from 0 onwards, but each can be calculated simply from the last value by simplying multiplying by x.