DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 4 of 4

Thread: SQRT lookup, slower than sqrt()?

  1. #1
    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[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;
    }

  2. #2
    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
    DKyb
    -------------------------------
    Life is a short warm moment -
    Death is the long cold rest.
    Pink Floyd
    -------------------------------

  3. #3
    Join Date
    Jan 2007
    Posts
    145
    Use hash lookup. you are running through for loop.

  4. #4
    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.

Similar Threads

  1. To Lookup or not to Lookup, that is the issue.
    By Otis in forum Architecture and Design
    Replies: 7
    Last Post: 09-07-2003, 02:33 PM
  2. Lookup list required for entry of a ROW of data
    By Mike Turner in forum VB Classic
    Replies: 0
    Last Post: 04-07-2002, 11:24 AM
  3. Table Lookup
    By Dan in forum Database
    Replies: 2
    Last Post: 11-08-2001, 01:13 PM
  4. Designing standard lookup table editing
    By Vikas Chopra in forum VB Classic
    Replies: 0
    Last Post: 06-27-2000, 11:11 AM
  5. Designing standard lookup table editing
    By Vikas Chopra in forum VB Classic
    Replies: 0
    Last Post: 06-27-2000, 11:10 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center