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);
}
``````

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