units icon indicating copy to clipboard operation
units copied to clipboard

Non-recursive pow

Open JohelEGP opened this issue 7 years ago • 2 comments

The constexpr pow uses recursion, which is potentially expensive and slow when not used in a constexpr context. I suggest that it be changed to use a loop instead. I guess the implementation dates back to being C++11 constexpr compliant.

There are also some uses of it in this library, at least in convert, which aren't guaranteed to be constexpr evaluated. I suggest refactoring these calls as initializers to constexpr variables.

JohelEGP avatar May 17 '18 22:05 JohelEGP

Is the exponent known at compile time? If so, you might do better by progressively halving the exponent, e.g.:

n^9 = n*(n^4)^2 = n*((n^2)^2)^2

potentially some branches to test what the exponent is but if the exponent is known at compile time, this reduces the multiplications down from 8 to 4. Here's an implementation that is geared toward compile-time efficiency but the saving is the same when the base is dynamic.

Here's an example optimized for static exponent and variable base. It would be very difficult to make this as efficient using a loop.

johnmcfarlane avatar May 18 '18 01:05 johnmcfarlane

I think #262 and #265 fix this issue?

Strictly speaking, it's still a recursive implementation, but they're tail-recursive and at least based on quick checks on godbolt compilers can transform that to an iterative implementation.

ts826848 avatar Nov 26 '20 05:11 ts826848