HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can loops like this one be algorithmically transformed into multiplication

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thiscantransformedmultiplicationintoloopslikealgorithmicallyone

Problem

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?

Solution

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

Context

StackExchange Computer Science Q#81316, answer score: 4

Revisions (0)

No revisions yet.