CEO at http://www.softwareandfinance.com 

Introduction

Is it possible to use indexing method (lookup table method) for mathematical functions such as SIN, COS, TAN, SQRT rather than calculating the value each and every time? The answer is yes but indexing would be based on integer values. Can we use a floating point number as a index? Yes, it is possible with certain limitations. In this article I am going to explain how to use a floating point number to index.

The sample code used here for tested with Microsoft Visual C++ compiler.

A Sample Lookup table method with integer values

static float arrSinValues[361]; // for 0 - 360 degrees

void InitMathFunc()
{
for(int i = 0; i <= 360; i++)
arrSinValues[i] = sin(i * PI_OVER_180);
}

float SinOptimized(int angle)
{
ASSERT(angle >= 0 && angle <= 360);
return arrSinValues[angle];
}

This look up table method is good however it does not support floating point numbers. It is based on our requirement. This is good in performance but not good in accuracy.

A Sample Lookup table method with floating Point number, converting floating point to integer values to index

static float arrSinValues[360 * 1000 + 1]; // for 0.000 - 360.000 degrees

void InitMathFunc()
{
int nIndex = -1;
for(float fAngle = 0.0; fAngle <= 360.0; fAngle += 0.001f) { nIndex = static_cast (fAngle * 1000.0f);
arrSinValues[index] = sin(fAngle * PI_OVER_180);
}
}

float SinOptimizated(float fAngle)
{
int nIndex = static_cast (fAngle * 1000.0f);
return arrSinValues[nIndex];
}

However this version is also useless because multiplication and casting to integer eliminates the effect of optimization.

Efficient way of indexing a floating Point number

Floating point numbers use IEEE (Institute of Electrical and Electronics Engineers) format. The real numbers are represented as real * 4, real * 8 and real * 10. In C++, the word float is used for representing the real * 4 numbers, the word double for real * 8 number and the word long double for real * 10 numbers. The real number bit pattern representation is given below:

a. Real * 4 number (float): 1 sign bit, 8 bit exponent, 23-bit mantissa
b. Real * 8 number (double): 1 sign bit, 11-bit exponent,52-bit mantissa
c. Real * 10 number (long double): 1 sign bit, 15-bit exponent, 64-bit mantissa

For example, the number 110 - As it is having the bias value of 127. 127 will be treated ass -1 and 110 with be -17. To support the range of 0 to 1, the entire 8 bit mantissa is used for index calculation.

The other option is store -360 to +360 degrees, the exponent value always falls in the range of 110 to 135. The delta here is 25 that can be accommodated in 5 bits. If the exponent value is subtracted by 110; then it always falls with in the range of 0 - 25. The memory will also be reduced by 8 times. But the subtraction takes significant amount of time at the time of computing the index. This reduces the optimization performance a lot. Consequently this option is also not appropriate to achieve good results.

Algorithm to calculate indexing for float numbers is given below:

1. Copy the floating-point bit pattern into a long value. Union consisting of a float and long value is most appropriate to do this work.

2. Mask the sign bit to Zero. It is an optional step. If the result of the library function does not vary with the positive and negative number, this step can be performed. Example: COS(...) function.

3. Decide the number of unused bits (N), for example: 10 Remember that if reducing the number of unused bits will get more accuracy but increase in the memory.

4. Do right shift the number by N time. It will insert zeros in the Mobs.

5. Total number of used bits is the 8 bits for exponent + (23 bit mantissa - 10 (N - no. of unused bits). So the total used bits are 8 + 13 = 21 bits. If step 2 is not performed, then the sign bit has to included. As a result it becomes 22 bits.

6. The index range is 0 - 2 ^ 21 with out sign bit. The lookup table float array should allocated to accommodate this entire range. The lookup table needs 8 MB with out sign bit and 16 MB with sign bit.

Written by Kathir, California.

CEO at http://www.softwareandfinance.com