DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: SQRT lookup, slower than sqrt()?

1. Registered User
Join Date
Jun 2007
Posts
1

## SQRT lookup, slower than sqrt()?

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.

Code:
```#include <cstdlib>
#include <iostream>
#include <math.h>
#include <windows.h>
#include <fstream>

using namespace std;

double lookupTable;

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;
}```  Reply With Quote

2. Registered User
Join Date
Jan 2005
Location
UK
Posts
604
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  Reply With Quote

3. Banned
Join Date
Jan 2007
Posts
145
Use hash lookup. you are running through for loop.  Reply With Quote

4. Senior Member
Join Date
Dec 2003
Posts
3,366
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.
Last edited by jonnin; 06-18-2007 at 08:49 AM.  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• 