Example: Computing Squares

Assume that multiplication is an expensive operation. Consider the problem of computing squares of succesive integers.


for i := 0 to 99 do
  x[i] := i*i;
versus

next := 0;
delta := 1;
for i := 0 to 99 do
  begin
     x[i]  := next;
     next  := next + delta;
     delta := delta + 2
  end;
The second version has more code, but does no multiplication.

This form of computation has a long history; it was the basis of Babbage's Difference Engine.

Contents    Page-10    Prev    Next    Page+10    Index