Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!cbatt!ihnp4!inuxc!pur-ee!uiucdcs!uiucdcsm!mccaugh
From: mccaugh@uiucdcsm.UUCP
Newsgroups: comp.lang.c
Subject: Re: induction variable optimization
Message-ID: <4700002@uiucdcsm>
Date: Wed, 11-Feb-87 02:07:00 EST
Article-I.D.: uiucdcsm.4700002
Posted: Wed Feb 11 02:07:00 1987
Date-Received: Fri, 13-Feb-87 01:50:30 EST
References: <182@ndmath.UUCP>
Lines: 25
Nf-ID: #R:ndmath.UUCP:182:uiucdcsm:4700002:000:1218
Nf-From: uiucdcsm.cs.uiuc.edu!mccaugh    Feb 11 01:07:00 1987


 Yes, the two fragments of code are semantically equivalent in that they
 should yield as final value j(final) = j(initial) + 315. Of course, if
 j(initial) = undefined, they will still be equivalent!
 A loop-invariant for the first fragment is: 
       (i=#) & (j(#) = j(initial) + 7*(1 + ... + #-1))
 where '#' = number of cycles (of the FOR-loop); a loop-invariant for the
 second fragment is similar: (i=7*#) & (j(#) = j(initial) + 7*(1 + ... + #-1)).
 Both fragments will cycle 10 times, so that:
     j(final) = j(10) = j(initial) + 7*(9*10)/2 
              = j(initial) + 315.

 (But the final values of i of course differ: i(final) = 10 in the first
  fragment, and 70 in the second -- I here assumed that 'i' was a loop-
  counter and that 'j' was the variable of interest.)

 The efficiency gained in the second fragment is to replace a multiplication
 by an addition, considered "efficient" since the simplification is repeated
 ten times.

 I apologize for this verbose response, which I only entered after reading the
 first 5 and being disappointed to find no demonstration of the equivalence
 claimed for the 2 fragments. (I sincerely hope this fills that gap.)

 -- Scott McCaughrin (mccaugh@uiucmsl)