Re: Mathematical models for loop calculations

Tim Frink <plfriko@xxxxxxxx> writes:

Hi,

I'm looking for an approach to represent calculations within
a loop (of a computer program) by mathematical models. To make
things clear, here is a simple example for a loop that iterates
10 times:


The traditional approach to what you are looking for is called
"strength reduction" and it is a typical compiler optimization
technique. Variables whose values behave in well-defined ways are
called "induction" variables. You can generally turn them into sum
forms (the big sigma operator).

Then, you simply calculate sigma for the number of times the loop
iterates. The standard rules apply. Thus, if a variable starts at 5
and increments by 3 each iteration, and the loop runs 7 times. The
variable wil be 8 after the 1st iteration, 11 after the 2nd, 14 after
the 3rd, ..., and 26 after the 7th and final iteration. As I said,
the standard rules apply and we know from algebra that the sum of n
copies of the constant k is n*k, which we add to the initial value to
get the final result.

Similarly, if the variable is multiplied by a fixed amount, ones gets
an exponential form. If the variable is the sum of another induction
variable, you get a nested summation form.

BTW, when I mentioned strength reduction, the traditional use of
strength reduction was to reduce multiplications into sigmas (see
below), but the technique works both ways. It just depends upon which
you want.

i = 1; while (i < 10) { i = i + 1; j = i * 2; }

is the same as:

i = 1; j = 2; while (i < 10) { i = i + 1; j = j + 2; }

is the same as (excuse my ascii art if it doesn't line up well):

10
j = sigma 2
i = 1

is the same as:

i = 10; j = 20;

The one final point worth making is Paul Black wasn't just spouting
nonsense when he declared this problem to be unsolvably hard. If you
allow some of the variables to be arrays where the elements can get
mutated and make the halting condition depend on the values in the arrays
and not some fixed bound and you can quickly and easily turn this in a
Turing Machine computation.

Hope this helps,
-Chris

*****************************************************************************
Chris Clark Internet : compres@xxxxxxxxxxxxx
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------
.

Relevant Pages

  • Problem with Loop
    ... i have a problem with the following loop: ... function M = SimulateMC(n, m, S0, dT, mu, sigma, lambda) ... The function returns a vector on n+1 elements, the first element being S0. ...
    (comp.soft-sys.matlab)
  • Re: Fastest MacIntel Forth?
    ... loop Sum; ... VALUE imb ... VALUE sum ... VALUE sel ...
    (comp.lang.forth)
  • Re: Seriously struggling with C
    ... Do your textbook examples, get used to the various loop constructs, try ... and then outputs their sum. ... int main{ ... or at the top of the array) I really like to do it a bit more cryptic, ...
    (comp.lang.c)
  • Re: While statement
    ... > sum off all the odd numbers. ... > inputed value some of the eben integers and sum of odd integers. ... > start loop ... It sounds like your pseudocode will more or less actually do what the ...
    (comp.lang.java.programmer)
  • Re: reduce()--what is it good for? (was: Re: reduce() anomaly?)
    ... > Any reduction that doesn't involve summing won't be handled by sum. ... A plain loop on .extend is much ... > totally inappropriate given that it's there for a reason and there will ... You claim "there will be no replacement", ...
    (comp.lang.python)