3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – rici Sep 18 '17 at 1:29
  • $\begingroup$ 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. $\endgroup$ – D.W. Sep 18 '17 at 6:16
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – rici Sep 18 '17 at 2:11
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Simple

if(x < 0) {
    x = 60 - ((-x) % 60);
}
$\endgroup$
  • $\begingroup$ I think OP asks for algorithm that has only additions/multiplications. Maybe inverting the number, but that requires floating point. $\endgroup$ – rus9384 Sep 23 '17 at 3:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.