0

Today while programming I stumbled upon the following question - are there any compilers which optimize based on mathematical assumptions?

For instance in cases like

unsigned int i,b;
(i,b not constant)
if(sqrt(i) == b)
...

In this case it would be a lot more effective to use

unsigned int i,b;
(i,b not constant)
if(i == b*b)
...

Assuming a sqrt() function, that handles unsigned integers and rounds sensefully.

Since I was not able to find useful information (probably because I did not know what to search for specifically), can someone please tell me or point me to a relevant source?

Are there compilers (for imperative languages) who optimize such things using some kind of heuristic? Or more specifically - what about gcc and microsoft visual c++ and matlab?

Improve this question
12
  • 5
    Presumably this is only possible in languages that do symbolic math and totally hopeless in the many languages with less-than-infinite precision arithmetic. When you're stuck with finite precision, these two code snippets are not equivalent, so a compiler in those languages that tried to do this would simply be broken. – Ixrec Jan 22 '16 at 21:17
  • Thanks for the hint, ofc it does not make sense for floats. – NeinDochOah Jan 22 '16 at 21:23
  • 2
    How does the compiler know that sqrt(x) and operator*(y,y) are equivalent in this context? You need to answer that question first. – user22815 Jan 22 '16 at 21:25
  • 3
    Of course there is also the case where in your example someone may expect the sqrt of a negative to cause an error that you are removing with your change just as something to note. – JB King Jan 22 '16 at 21:34
  • 2
    For all practical intents and purposes, the answer would be "no". For example, cc -O3 wouldn't do that particular example. And, in general, in computationally intensive situations, you'd better think through the best algorithm and implementation yourself. – John Forkosh Jan 23 '16 at 8:50
4

Compilers routinely engage in strength reduction.

One common example of which is reducing multiples to adds (as adds are typically faster than multiplies).

i*2 transformed to i+i is faster on many machines, (and this is sometimes transformed to i<<1 instead).

Implicit multiplies commonly happen in for-loops over arrays (whose element size is > 1 byte), and can sometimes be reduced to adding, with optimization induction variable, which is similar in that the mathematical relationship between multiply and add is involved.

Improve this answer
3
  • The way I understand it, this depends on a couple of facts, array (so consecutive data), word size or access of only every n-th element. So yes thats the general idea, but not based on a mathmatical decision, but rather using the way the data is read. – NeinDochOah Jan 22 '16 at 21:52
  • If you're taking about induction variables, it is indeed based on access pattern, but it would be hard to argue that the transformation of repetitive multiply to cumulative addition didn't depend upon on the mathematical relationship between multiply and add. – Erik Eidt Jan 22 '16 at 22:02
  • Yes and I therefore upvoted your post. – NeinDochOah Jan 22 '16 at 22:09

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.