Calculating pow(x, y) when one value is fixed

Viewed 159

Consider the calculation of pow(x, y) for double values. We can assume that standard library implementations are relatively efficient for the case where both x and y vary arbitrarily, but how about the case where where either x or y are fixed for a large number of calls to pow?

How can we take advantage of this fact to speed up evaluation, e.g., by hoisting out work which depends only the fixed parameter, so that is only done once?

Note that the fixed values are not known at compile-time, but at runtime, so any compile-time analysis isn't useful.

1 Answers

Can we take advantage of this fact to speed up evaluation, e.g., by hoisting out work which depends only the fixed parameter, so that is only done once?

Yes, you may achieve correct and faster results if you are well versed in math and floating point, some compiler knowledge, and exploit application use on a limited range of the remaining variable x or y.

Else like the other 99.9% of coders, realize such code is likely a little wrong in many cases, greatly wrong in special cases and even if faster on one platform, not certainly so in a portable sense.

Various compilers analyse pow(x,y) and will emit efficient code with select constants. Consider allowing the compiler to do its job and if still in doubt, profile against your best attempt and see what gains are had. The tricky part of testing your code will be to see how much precision you lost.


Given OP's additional info, some ideas:

pow(x,y) is mathematically as exp(y*log(x)) with infinite precision and when x > 0.

Let double u = y*log(x).
With C code, pow(x,y) is more like exp(u + u_err), where u_err is the accumulated error of the log(), multiplication and finite precision of double.

The error in the result of v = exp(u + u_err) is very sensitive to the magnitude of u. When u is [-1…1], u_err makes little difference. When |u| is 10, u_err eats away at the 11 or so LSBits of v. Good pow() handles this loss with extra internal precision.


If precision loss is a concern

To successfully manage precision loss, the first step is to use exp2(), log2() instead of exp(), log(). Base 2 tends to be faster and at least select results are exact. If x is “fixed” and x > 0, we could pre-calculate xlog2 = log2(x) and then later repetitively use exp2(y * xlog2). Also we could take advantage of extra precision of long double, when it exist.

long double vs. double cost performance in at least 3 places:

  • log2l(x), a one time cost.

  • xlog2l * y to reduce u_error.

  • exp2l(u) to reduce computational error or just exp2() if |u| < 1.

    // Using `long double` to help maintain precession    
    void pow_x_pos_fixed(size_t n, double x, const double *y, double *xy) {
      assert(x > 0);
      long double xlog2l = log2l(x);  // Using long double here is a one time cost
      for (size_t i = 0; i<n; i++) {
        long double u = xlog2l * y;
        xy[i] = (double) exp2l(u); 
      }
    }
    

In the end, I suspect the above may not be much faster than pow(x,y) and so the only real faster approaches loss precision. In that case is tolerable, also consider powf((float)x, (float)y)).

Related