We found that for many applications a substantial part of the time spent in software vertex processing was being spend in the powf function. So quite a few of us in Tungsten Graphics have been looking into a faster powf.

## Introduction

The basic way to compute powf(x, y) efficiently is by computing the equivalent exp2(log2(x)*y)) expression, and then fiddle with IEEE 754 floating point exponent to quickly estimate the log2/exp2. This by itself only gives a very coarse approximation. To improve this approximation one has to also look into the mantissa, and then take one of two alternatives: use a lookup table or fit a function like a polynomial.

## Lookup table

See also:

### exp2

unionf4 { int32_t i[4]; uint32_t u[4]; float f[4]; __m128 m; __m128i mi; };#defineEXP2_TABLE_SIZE_LOG2 9#defineEXP2_TABLE_SIZE(1 << EXP2_TABLE_SIZE_LOG2)#defineEXP2_TABLE_OFFSET(EXP2_TABLE_SIZE/2)#defineEXP2_TABLE_SCALE((float) ((EXP2_TABLE_SIZE/2)-1))/* 2 ^ x, for x in [-1.0, 1.0[ */staticfloat exp2_table[2*EXP2_TABLE_SIZE]; voidexp2_init(void) { int i;for(i = 0; i < EXP2_TABLE_SIZE; i++) exp2_table[i] = (float)pow(2.0, (i - EXP2_TABLE_OFFSET) / EXP2_TABLE_SCALE); }/*** Fast approximation to exp2(x).* Let ipart = int(x)* Let fpart = x - ipart;* So, exp2(x) = exp2(ipart) * exp2(fpart)* Compute exp2(ipart) with i << ipart* Compute exp2(fpart) with lookup table.*/__m128exp2f4(__m128 x) { __m128i ipart; __m128 fpart, expipart;unionf4 index, expfpart; x =_mm_min_ps(x,_mm_set1_ps( 129.00000f)); x =_mm_max_ps(x,_mm_set1_ps(-126.99999f));/* ipart = int(x) */ipart =_mm_cvtps_epi32(x);/* fpart = x - ipart */fpart =_mm_sub_ps(x,_mm_cvtepi32_ps(ipart));/* expipart = (float) (1 << ipart) */expipart =_mm_castsi128_ps(_mm_slli_epi32(_mm_add_epi32(ipart,_mm_set1_epi32(127)), 23));/* index = EXP2_TABLE_OFFSET + (int)(fpart * EXP2_TABLE_SCALE) */index.mi =_mm_add_epi32(_mm_cvtps_epi32(_mm_mul_ps(fpart,_mm_set1_ps(EXP2_TABLE_SCALE))),_mm_set1_epi32(EXP2_TABLE_OFFSET)); expfpart.f[0] = exp2_table[index.u[0]]; expfpart.f[1] = exp2_table[index.u[1]]; expfpart.f[2] = exp2_table[index.u[2]]; expfpart.f[3] = exp2_table[index.u[3]];return_mm_mul_ps(expipart, expfpart.m); }

### log2

#defineLOG2_TABLE_SIZE_LOG2 8#defineLOG2_TABLE_SIZE(1 << LOG2_TABLE_SIZE_LOG2)#defineLOG2_TABLE_SCALE((float) ((LOG2_TABLE_SIZE)-1))/* log2(x), for x in [1.0, 2.0[ */staticfloat log2_table[2*LOG2_TABLE_SIZE]; voidlog2_init(void) { unsigned i;for(i = 0; i < LOG2_TABLE_SIZE; i++) log2_table[i] = (float)log2(1.0 + i * (1.0 / (LOG2_TABLE_SIZE-1))); } __m128log2f4(__m128 x) {unionf4 index, p; __m128i exp =_mm_set1_epi32(0x7F800000); __m128i mant =_mm_set1_epi32(0x007FFFFF); __m128i i =_mm_castps_si128(x); __m128 e =_mm_cvtepi32_ps(_mm_sub_epi32(_mm_srli_epi32(_mm_and_si128(i, exp), 23),_mm_set1_epi32(127))); index.mi =_mm_srli_epi32(_mm_and_si128(i, mant), 23 - LOG2_TABLE_SIZE_LOG2); p.f[0] = log2_table[index.u[0]]; p.f[1] = log2_table[index.u[1]]; p.f[2] = log2_table[index.u[2]]; p.f[3] = log2_table[index.u[3]];return_mm_add_ps(p.m, e); }

### pow

staticinline__m128powf4(__m128 x, __m128 y) {returnexp2f4(_mm_mul_ps(log2f4(x), y)); }

## Polynomial

For more details see:

- Posts from Nick from Ghent, Belgium in Approximate Math Library thread.
- Minimax Approximations and the Remez Algorithm

### exp2

#defineEXP_POLY_DEGREE 3#definePOLY0(x, c0)_mm_set1_ps(c0)#definePOLY1(x, c0, c1)_mm_add_ps(_mm_mul_ps(POLY0(x, c1), x),_mm_set1_ps(c0))#definePOLY2(x, c0, c1, c2)_mm_add_ps(_mm_mul_ps(POLY1(x, c1, c2), x),_mm_set1_ps(c0))#definePOLY3(x, c0, c1, c2, c3)_mm_add_ps(_mm_mul_ps(POLY2(x, c1, c2, c3), x),_mm_set1_ps(c0))#definePOLY4(x, c0, c1, c2, c3, c4)_mm_add_ps(_mm_mul_ps(POLY3(x, c1, c2, c3, c4), x),_mm_set1_ps(c0))#definePOLY5(x, c0, c1, c2, c3, c4, c5)_mm_add_ps(_mm_mul_ps(POLY4(x, c1, c2, c3, c4, c5), x),_mm_set1_ps(c0)) __m128exp2f4(__m128 x) { __m128i ipart; __m128 fpart, expipart, expfpart; x =_mm_min_ps(x,_mm_set1_ps( 129.00000f)); x =_mm_max_ps(x,_mm_set1_ps(-126.99999f));/* ipart = int(x - 0.5) */ipart =_mm_cvtps_epi32(_mm_sub_ps(x,_mm_set1_ps(0.5f)));/* fpart = x - ipart */fpart =_mm_sub_ps(x,_mm_cvtepi32_ps(ipart));/* expipart = (float) (1 << ipart) */expipart =_mm_castsi128_ps(_mm_slli_epi32(_mm_add_epi32(ipart,_mm_set1_epi32(127)), 23));/* minimax polynomial fit of 2**x, in range [-0.5, 0.5[ */#ifEXP_POLY_DEGREE == 5 expfpart =POLY5(fpart, 9.9999994e-1f, 6.9315308e-1f, 2.4015361e-1f, 5.5826318e-2f, 8.9893397e-3f, 1.8775767e-3f);#elifEXP_POLY_DEGREE == 4 expfpart =POLY4(fpart, 1.0000026f, 6.9300383e-1f, 2.4144275e-1f, 5.2011464e-2f, 1.3534167e-2f);#elifEXP_POLY_DEGREE == 3 expfpart =POLY3(fpart, 9.9992520e-1f, 6.9583356e-1f, 2.2606716e-1f, 7.8024521e-2f);#elifEXP_POLY_DEGREE == 2 expfpart =POLY2(fpart, 1.0017247f, 6.5763628e-1f, 3.3718944e-1f);#else#error#endifreturn_mm_mul_ps(expipart, expfpart); }

### log2

#defineLOG_POLY_DEGREE 5 __m128log2f4(__m128 x) { __m128i exp =_mm_set1_epi32(0x7F800000); __m128i mant =_mm_set1_epi32(0x007FFFFF); __m128 one =_mm_set1_ps( 1.0f); __m128i i =_mm_castps_si128(x); __m128 e =_mm_cvtepi32_ps(_mm_sub_epi32(_mm_srli_epi32(_mm_and_si128(i, exp), 23),_mm_set1_epi32(127))); __m128 m =_mm_or_ps(_mm_castsi128_ps(_mm_and_si128(i, mant)), one); __m128 p;/* Minimax polynomial fit of log2(x)/(x - 1), for x in range [1, 2[ */#ifLOG_POLY_DEGREE == 6 p =POLY5( m, 3.1157899f, -3.3241990f, 2.5988452f, -1.2315303f, 3.1821337e-1f, -3.4436006e-2f);#elifLOG_POLY_DEGREE == 5 p =POLY4(m, 2.8882704548164776201f, -2.52074962577807006663f, 1.48116647521213171641f, -0.465725644288844778798f, 0.0596515482674574969533f);#elifLOG_POLY_DEGREE == 4 p =POLY3(m, 2.61761038894603480148f, -1.75647175389045657003f, 0.688243882994381274313f, -0.107254423828329604454f);#elifLOG_POLY_DEGREE == 3 p =POLY2(m, 2.28330284476918490682f, -1.04913055217340124191f, 0.204446009836232697516f);#else#error#endif/* This effectively increases the polynomial degree by one, but ensures that log2(1) == 0*/p =_mm_mul_ps(p,_mm_sub_ps(m, one));return_mm_add_ps(p, e); }

## Results

The accuracy vs speed for several table sizes and polynomial degrees can be seen in the chart below.

The difference is not much, but the polynomial approach outperforms the table approach for any desired precision. This was for 32bit generated code in a Core 2. If generating 64bit code, the difference between the two is bigger. The performance of the table approach will also tend to degrade when other computation is going on at the same time, as the likelihood the lookup tables get trashed out of the cache is higher. So by all accounts, the polynomial approach seems a safer bet.