# Can loops like this one be algorithmically transformed into multiplication

Are there known techniques for converting a loop like the following to an if and a multiplication?

while (x < 0) {
x += 60;
}


It seems clear that this could be replaced with something like the following

if (x < 0) {
x += f(x, 60);
}


where f contains no loops, presumably using multiplication. This would have the benefit of being faster for sufficiently large negative numbers.

Is there a well understood algorithm for finding f for an arbitrary loop of this form?

• Clang seems to be able to do that: godbolt.org/g/oZaf4Y (Note: it also replaces the division with an inverse scaled multiplication, which is a very common way of eliminating division by known constants.) – rici Sep 18 '17 at 1:29
• One approach could be to use known techniques for loop invariant synthesis (discovering a loop invariant). The loop invariant might characterize the value of x after existing the loop, which in some cases might enable replacing the entire loop with a simple function f as you seek. – D.W. Sep 18 '17 at 6:16

The name for this optimization seems to be induction variable elimination, there are some nice slides explaining the idea here.

What you want to do here is find a number, which when multiplied by 60 and added to x, will bring x above (or equal to) your chosen limit.

This number can be found by dividing the difference between x and 0 by 60, and taking the ceiling of the resulting value. The general function would be:

f(x,y) = ceil((limit-x) / y) * y


Note that when your limit is 0 the expression simplifies to:

f(x,y) = ceil(-x / y) * y

• Yes, that is how to simplify the expression. But OP is not looking for the simplification; rather, the algorithm for deriving that solution given (say) a control-flow graph of the function. – rici Sep 18 '17 at 2:11

Here's how I went about it-
We know the loop keeps adding 60, (let the general case be known as k) till the input becomes positive.
Let input be x, we observe that when x lies between -59 and 0, we add 60 once, i.e when x-1 lies between -60 and -1 we add 60 once.
We can say from the observation that when x belongs to [n*k,(n-1)*k) we multiply k by n.
f(x,k)= n*k if x belongs to [n*k,(n-1))
From the above we can easily get the function f(x,k)=ceil(|x-1|/k)*k.
These steps are mere implementation of the principles which Cody posted above.

Simple

if(x < 0) {
x = 60 - ((-x) % 60);
}

• I think OP asks for algorithm that has only additions/multiplications. Maybe inverting the number, but that requires floating point. – rus9384 Sep 23 '17 at 3:01