Mathematical models for loop calculations

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:

i = 0,
b = 2,
c = 2,
d = 2,
e = 2;

while( i < 10 ) {
a = a + 1;
b = b + b;
c = c * c;
d = d + e;
e = e + 1;
i++;
}

Within the loop, the identifiers 'a'-'e' and 'i' will be updated for
each loop iteration and after the loop execution each symbol is assigned
its final result. I want to omit this approach done by the computer which
adjusts the value for the identifiers 10 time but want to express the
calculations as mathematical models to have a formula that determines
the values (depending on the number of loop iterations).

My first idea was to express the calculations by mathematical series
but I still don't know exactly how to do this. A somehow harder problem
is the calculation of 'd' which depends on the subsequent identifier
'e'.

Do you know any approaches for this? Any comments/solutions are
appreciated.

Best regards,
Tim

On Wednesday 26 September 2007 09:10, Tim Frink wrote:

> 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:
>
> i = 0,
> b = 2,
> ...
>
> while( i < 10 ) {
> a = a + 1;
> b = b + b;
> ...
> i++;
> }

So you would want to come up with

a' = a + 10
b' = 2^11

where a' and b' are the values of "a" and "b" after the loop exits,
right?

(If you didn't know the beginning value of i, it is
a' = a + 10-i
b' = 2^(i+1)
instead.)

In the broadest case, the problem is unsolvable: you can't always
prove a loop ends (think Fermat's last theorem or halting problem);
even for the cases you can, you can't easily prove how many times it
will loop (think cascading numbers); even if you can, there may be no
simple way to express the result (think sum of randomoid numbers).

That said, there are lots of ways to get some results.

> My first idea was to express the calculations by mathematical series
> but I still don't know exactly how to do this.

Yes, solving a mathematical series is probably the best all-around
approach. Some arithmetic and geometric series have nice forms
you can use. There are classes to teach how to solve a series.

Powerful math packages, like Mathematica or Maple, are great at
solving a series.

Sincerely,
-paul-
Paul E. Black (p.black@acm.org)

Tim Frink <plfriko@yahoo.de> 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@world.std.com
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)
------------------------------------------------------------------------------