SQRT lookup, slower than sqrt()?

[pirateninja]

I made a program to compare the speeds of getting the square root of a number using a lookup table and using sqrt() found in math.h. The entire purpose of a lookup table is to sacrifice memory and accuracy for increased speed.

What I found is that I am getting extremely fast(like something is wrong fast?) table generation times, and very similar test times for my lookup and sqrt().

My lookup table generates a look up table for all the numbers (to two decimal places) between 0 and 1000.99.

Here is the code, maybe someone can explain to me how getting an double out of an address takes up more computation time than calculating the square root of a number, something that takes many cpu cycles.

#include <cstdlib>
#include <iostream>
#include <math.h>
#include <windows.h>
#include <fstream>

using namespace std;

double lookupTable[1000][100]; 

void lookupInit()
{
    // Initilize to zero
    for (int i = 0; i < 1000; i++)
    {
        for (int i2 = 0; i2 < 100; i2++)
        {
            lookupTable[i][i2] = 0; 
        }
    }
    // Populate table
    for (double i = 0; i < 1000; i++)
    {
        for (double i2 = 0; i2 < 100; i2++)
        {
            lookupTable[(int)i][(int)i2] = sin(i+(i2/100)); 
        }
    }
}

// Pull a square root off of the table
double LUTsqrt(double n)
{
    int temp = n;
    return lookupTable[temp][(int)((n-temp) * 10)];
}

int main(int argc, char *argv[])
{
    // Generate table
    DWORD start = GetTickCount();
    lookupInit();
    double lookupTime = ((double)(GetTickCount() - start)) / 1000;
    
    // Generate LUT file
    ofstream LUT;
    LUT.open("C://lut.txt");
    
    // Used for displaying the % done
    int newPer;
    int oldPer = 0;
    
    // Used for keeping track of calculation time
    start = GetTickCount();
    
    // Test calculations
    for (double i = 0; i < 1000; i+= 0.01)
    {
        // Get current square root of I, write it to file
        LUT << (double)i << " - " << LUTsqrt(i) << endl;
        
        // if percentage has changed, clear screen, update displayed %
        newPer = (i/10);
        if (newPer > oldPer)
        {
            system("cls");
            cout << "LUT: " << newPer << "%" << endl;
            oldPer = newPer;
        }
    }
    
    double LUTTime = ((double)(GetTickCount() - start)) / 1000;
    LUT.close();
    
    // Generate SQRT file
    ofstream SQRT;
    SQRT.open("C://sqrt.txt");
    
    oldPer = 0;
    newPer = 0;
    
    start = GetTickCount();
    for (double i = 0; i < 1000; i+=0.01)
    {
        SQRT << (double)(i) << " - " << sqrt(i) << endl;
        newPer = (i/10);
        if (newPer > oldPer)
        {
            system("cls");
            cout << "SQRT: " << newPer << "%" << endl;
            oldPer = newPer;
        }
    }
    
    double SQRTTime = ((double)(GetTickCount() - start)) / 1000;
    SQRT.close();
    
    system("cls");
    cout << "LUT generation took " << lookupTime << " seconds." << endl;
    cout << "LUT file output generation took " << LUTTime << " seconds." << endl;
    cout << "SQRT file output generation took " << SQRTTime << " seconds." << endl;
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

[drkybelk]

I guess the creators of your compiler had a similar idea to you !! ;-)
My guess is that they implemented sqrt() as a lookup (or bit - algorithm) and because they did it using assembly language directly and manually optimized it they show your algorithm the backside...
Another hint is that when you index your table, you're using double - multiplication. You gotta do better than that, if you want to beat your built-in functions.

Cheers,
D

[it career]

Use hash lookup. you are running through for loop.

[jonnin]

sqrt is built into X86 processors, it is an assembly language instruction and you will not beat its efficiency (hardware circuit) with any other code. Is the chip you use in this family or other CISC family? its the fsqrt function, so 4 or 5 lines of assembly should get you the result.