Patrick Jeeves Patrick Jeeves - 1 year ago 101
C Question

Fast powers of two with floating exponent [C]

Essentially, I'm trying to use the values calculated in the code below, but when I storing the values in all the objects that have their own rates is adding just enough bytes to cause a cache miss. And using a lookup table obviously doesn't help matters.

So I'm looking for a way to get these values faster than with the standard power functions, are there any tricks I can use due to the possible inputs being very restricted?

static inline
double __attribute(( pure )) get_decay_rate(uint8_t rate)
if(rate >= 128)
return 65535.0/65536.0;

double k = pow(2, rate/8.0);
return (k - 1.0) / k;

/* pseudocode:
double k = (int) pow(2, k/8.0);
k = (k - 1) / k;
return log(65535/65536)/log(k);
static inline
uint16_t __attribute(( pure )) get_decay_modulus(uint8_t rate)
if(rate <= 128)
return 1;
//turns out to be the same as the above pseudocode, for some reason.
return pow(2, (rate - 128) / 8.0);

Answer Source

Take this line:

double k = pow(2, rate/8.0);

Basically what you are doing here is raising 2 to the power of a fixed point number.

You can make use of the fact that pow(a, b+c) = pow(a, b) * pow(a, c).

Store the 8 fractional exponents in a lookup table:

double fractionalPowersOf2[8];

for(int i = 0; i < 8; i++)
    fractionalPowersOf2[i] = pow(2.0, i / 8.0);

Then you can do your calculation like this:

double k = (double)(1 << (rate >> 3)) * fractionalPowersOf2[rate & 7];

This masks out the fractional part and uses it for a table lookup, then multiplies that by 2 raised to the power of the integral part using bitshifts. If the cast to double is too slow you can use a lookup table for that too.

You might also be able to use some fancy bitmagic type approach where you use your value as the exponent of a double by casting pointers etc but this will not be portable.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download