for loop calculation question

[Chad]

I was looking through some old comp.lang.c posts and came across the
following comment made by Chris Torek

"This is a typical optimization in any compiled, imperative language.
The theory is that loops -- especially inner loops, when loops are
nested -- contain code that will be run quite a bit, so if there is
some way to move some computation outside the loop and run it just
once, instead of every time, that should help a lot. Another
technique is "strength reduction", in which a "strong" operation
(like a multiplication) is "reduced" to an equivalent "weaker" one
(such as repeated addition) that should go faster:

for i in [0..N1) do
for j in [0..N2) do
op(arr[i;j])

The subscript operation here may (depending on the language) involve
multiplication, but the result will be the sequence {0,4,8,12,16,...}
or some such."

The following comment is from the following url

http://groups.google.com/group/comp...-8&q=evaluation+vs+execution#76fa5a51b83cb3f1

How does he get the sequence {0,4,8,12,16,...} from the for loops?

Chad

 

[grocery_stocker]

Chad said:

I was looking through some old comp.lang.c posts and came across
the following comment made by Chris Torek

[...] Another
technique is "strength reduction", in which a "strong" operation
(like a multiplication) is "reduced" to an equivalent "weaker" one
(such as repeated addition) that should go faster:

for i in [0..N1) do
for j in [0..N2) do
op(arr[i;j])

The subscript operation here may (depending on the language)
involve multiplication, but the result will be the sequence
{0,4,8,12,16,...} or some such."

The following comment is from the following url
http://groups.google.com/group/comp.lang.c/browse_thread/thread/7933a...



How does he get the sequence {0,4,8,12,16,...} from the for loops?

If I'm reading him right, this is n * sizeof(int) for successive n -
i.e. he's saying that, to access element [j] of a
two-dimensional array of int, one must calculate &arr[0][0] + i *
N1 + j, which involves a multiplication, whereas - if one is
prepared to treat the two-dimensional array as if it were
one-dimensional, a trick that the careful C programmer avoids but
the compiler can do with carefree abandon because it knows its
platform, one can crack through the array with a single loop and a
single iterator ix, so that the compiler need only calculate
&arr[0][0] + ix.

My private professional objective is to be able to make sense out of
at least one comp.lang.c Chris Torek post before I reach 80.