First and foremost, you should generally push off optimizing code until the end and instead be thinking about a coherent and simple design during most of your coding. This approach will often allow you to avoid duplicating (or triplicating, quadrupling…) effort or allow you to bypass certain computations entirely. However, if at the end of the day you find you’ve done all this and you would still like to accelerate your program lookup tables are one thing to try. They boil down to, it can be faster to retrieve a value stored in memory than it is to compute the value. So if you need to compute a given function 10^5 times on the range [0-1] you might be able to compute the function at intervals of 1/10^3 and then use the nearest value stored in the table instead of computing every time. Of course you’re losing accuracy, but you gain speed, and if you are willing to tolerate this tiny bit of error you might do a lot better. You could also think about doing some sort of linear interpolation between values in the lookup table which will decrease your error significantly, but again at the cost of speed.

Here’s a little program that allows you to change the operation in only one place. You can also change the size of the lookup table and the number of computations (if you’re doing fewer than the number of entries in the table you’re always better computing directly).

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <time.h> #include <math.h> #include <vector> using namespace::std; double my_rand(); double my_operation(double input); void init_sqrt_table(vector <int> & sqrt_table, double & step); #ifdef FAST double my_sqrt(double input, vector <int> & sqrt_table, int & num_steps); #else double my_sqrt(double input); #endif int main() { time_t start,end; double execution_time, tmp, maxval; vector sqrt_table(1000); double step = 0; int num_steps; time (&start); #ifdef FAST init_sqrt_table(sqrt_table, step); #endif srand (1); maxval = 0; num_steps = sqrt_table.size(); for(int i = 0; i < num_steps*100000; i++) { tmp = my_rand(); #ifdef FAST tmp = my_sqrt(tmp, sqrt_table, num_steps); // gets it from a lookup table #else tmp = my_sqrt(tmp); // just calls c sqrt #endif if(maxval < tmp) { maxval = tmp; } } cout << maxval << endl; time (&end); execution_time = difftime (end,start); cout << "Program execution time: " << execution_time << endl; return 0; } double my_rand() { return rand()*1.0/(RAND_MAX + 0.0); } void init_sqrt_table(vector <int> & sqrt_table, double & step) { cout << "filling sqrt table" << endl; step = 1.0 / sqrt_table.size(); for(int i = 0; i < sqrt_table.size(); ++i) { sqrt_table[i] = my_operation(i * step); } } #ifdef FAST double my_sqrt(double input, vector <int> & sqrt_table, int & num_steps) { return sqrt_table[rint(input*num_steps)]; } #else double my_sqrt(double input) { return my_operation(input); } #endif double my_operation(double input) { return exp(sqrt(exp(input))); }

## Leave a Reply