Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 5 down vote favorite
1

I'm writing an app which translates formulae into executable code. I've been experimenting with fairly obvious optimizations such as factoring (reducing number of multiplications) in order to make the code run faster. Can anyone suggest any other performance-related optimizations that could be performed when translating formulae to code? Thanks.

share|improve this question
4  
Make sure polynomials are always in Horner form. – J. M. Sep 16 '11 at 12:28
2  
Another one: isolate common subexpressions. For example, if you're optimizing something like $2\cos^3 x-\cos^2 x+1$, the right optimization is to cache the value of the cosine in some temporary variable $u=\cos\,x$, and then rewrite the polynomial in terms of the temporary variable in Horner form: $(2u-1)u^2+1$. – J. M. Sep 16 '11 at 12:59
@J.M. thanks, subexpression analysis is one of the things I'm already working on – Dmitri Nesteruk Sep 16 '11 at 13:02

2 Answers

up vote 2 down vote

The code

double x = a / b + c / d;

typically takes about twice as long to execute as the equivalent expression

double x = (a * d + b * c) / (b * d);

because floating point division is very slow whereas addition and multiplication are fast.

As well as that there are the obvious things to do like pre-computing constant values, and replacing

double x = a + 0.0; double y = b * 1.0; double z = c / 1.0;

with the equivalent expressions

double x = a; double y = b; double z = c;

This isn't quite so nonsensical as it may appear: the constants 1.0 and 0.0 might not be the values originally written, but rather the results of some intermediate computation.

You could also optimize pow(x, 2) to x * x and the like, although any decent compiler should do this for you.

share|improve this answer
Thanks! Is the performance difference a well-known value (say, on a modern-day Quad-core CPU)? – Dmitri Nesteruk Sep 16 '11 at 13:34
But are these two expressions equivalent in floating-point arithmetic? – lhf Sep 16 '11 at 13:38
@Dmitri, a rule of thumb is that addition takes 3 units, multiplication 4 units and division 32 units of time (e.g. clock cycles). – Chris Taylor Sep 16 '11 at 13:40
@lhf No (although I don't think that's really a problem - how often do you care about the exact floating point representation of your result?). A more serious problem is that if you perform this optimization you might induce an overflow, if any of your intermediate products are larger than the maximum double value supported on your system. – Chris Taylor Sep 16 '11 at 13:42
I optimize power methods already. As for calculations resulting in multiplication by 1, I think it's really hard to detect those unless I encounter something obvious like x*(y/y) – Dmitri Nesteruk Sep 16 '11 at 13:53
show 3 more comments
up vote 1 down vote

I think you'd better leave such optimizations to the compiler. Or do you have evidence that the compiler cannot do justice to your formulas?

share|improve this answer
1  
I don't think a compiler can optimize a*x*x + b*x to become x*(a*x + b) :) and that's just a simple case. – Dmitri Nesteruk Sep 16 '11 at 12:55
1  
@Dmitri, try gcc -S -O2 on the program int f(int a, int b, int x) { return a*x*x + b*x; } int g(int a, int b, int x) { return x*(a*x + b); }. The generated code is the same. Using double instead of int does generate different code but it's probably because the compiler is aware that floating-point arithmetic is not distributive. – lhf Sep 16 '11 at 13:17
Okay, so gcc can optimize this, but I don't think every compiler can do this. I don't think it's correct to rely on the compiler optimizing things for you. – Dmitri Nesteruk Sep 16 '11 at 13:22
2  
@Dmitri, sure, every compiler is gcc but you can bet that optimizing compilers will do a good job. There has been decades of research on that. My point is: don't try to outsmart the compiler; you may even force it to generated worse code than if you just wrote what you meant. – lhf Sep 16 '11 at 13:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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