Lookup Tables

[CoreyWhite]

The future of computer architecture will use lookup tables. Currently
computer processor speed outweighs the benefits of using computer
memory for lookup tables, except in some cases. As computer memory
increases, new ROM chips will be built with lookup tables hardcoded
into them. Here is an example of what using a lookup table can do for
you. The following program divides to integers from 0 to 4 using
lookup tables and times itself against the same operation using the
division operator in c++.

I came up with this idea myself, and met critisism everywhere I brought
it up. It is actually a handy algorithm and you can read more about it
on wikipedia:
http://en.wikipedia.org/wiki/Lookup_table

#include <cstdlib>
#include <iostream>
#include <ctime>

using namespace std;

int main(int argc, char *argv[]){
time_t t1, t0;
double elapsed;

float div[5][5]={ {0,0,0,0,0}, {1,0.5,0.3333,0.25,0.2},
{2,1,0.6666,0.5,0.4}, {3,1.5,1,0.75,0.6}, {4,2,1.3333,1,0.8} };
int a=1, b=2;
float ans=0;

time(&t0); /* start time */
for(int cnt=0; cnt<1000000000; cnt++){

ans=div[a][b];

}
time(&t1);
elapsed = difftime(t1, t0);
cout<<"Time: "<<elapsed<<" seconds."<<endl;

time(&t0); /* start time */
for(int cnt=0; cnt<1000000000; cnt++){
ans=a/b;
}
time(&t1);
elapsed = difftime(t1, t0);
cout<<"Time: "<<elapsed<<" seconds."<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}

[Victor Bazarov]

Co********@gmail.com wrote:

The future of computer architecture will use lookup tables. Currently
computer processor speed outweighs the benefits of using computer
memory for lookup tables, except in some cases. As computer memory
increases, new ROM chips will be built with lookup tables hardcoded
into them. Here is an example of what using a lookup table can do for
you. The following program divides to integers from 0 to 4 using
lookup tables and times itself against the same operation using the
division operator in c++.

I came up with this idea myself, and met critisism everywhere I
brought it up. [..]

Well, out of all floating-point divisions, how much do you think is
done with both operands integer and between 0 and 4? I mean, it is
a great idea to use lookup tables where possible and feasible, but
to say that the increase in computer memory will turn the tables on
such thing as lookup tables? Really? Let's say I in my problem need
to divide a floating point value (2^50 or about potential FP numbers)
by, say, a dozen other values (2^4 dividers). I would need to pre-
calculate and keep 2^54 * sizeof(double) results (2^58 bytes or so)
if I were to use a lookup table instead of utilising the CPU's ability
to divide. Is that feasible? Nope. So, lookup tables do have their
application but they are limited. You should definitely promote the
idea (even if you do claim that you "came up with" it yourself), but
try to give a well-rounded set of examples where it is applicable and
does give an advantage. Floating-point division is just not one of
them, trust me. I bet that's why you "met criticism everywhere".

V

[Jack Klein]

On 21 Aug 2005 15:20:24 -0700, Co********@gmail.com wrote in
comp.lang.c++:

The future of computer architecture will use lookup tables.
That's amazing. I always thought the past and present of computer
architectures used lookup tables. Apparently I was wrong, because
according to you they haven't been invented yet.
Currently
computer processor speed outweighs the benefits of using computer
memory for lookup tables, except in some cases. As computer memory
increases, new ROM chips will be built with lookup tables hardcoded
into them. Here is an example of what using a lookup table can do for
you. The following program divides to integers from 0 to 4 using
lookup tables and times itself against the same operation using the
division operator in c++.

I came up with this idea myself, and met critisism everywhere I brought
it up.
Did you even stop to consider that the critics were right?

They laughed at Einstein. They laughed at the Wright brothers. They
laughed at Corey White. Then they stopped laughing at Einstein and
the Wright brothers.

Exactly what qualifications do you have that we should take your
half-baked and unoriginal ideas seriously? What credentials do you
have? What expertise have you demonstrated in previous post to
comp.lang.c++.
It is actually a handy algorithm and you can read more about it
on wikipedia:
http://en.wikipedia.org/wiki/Lookup_table

#include <cstdlib>
#include <iostream>
#include <ctime>

using namespace std;

int main(int argc, char *argv[]){
time_t t1, t0;
double elapsed;

float div[5][5]={ {0,0,0,0,0}, {1,0.5,0.3333,0.25,0.2},
{2,1,0.6666,0.5,0.4}, {3,1.5,1,0.75,0.6}, {4,2,1.3333,1,0.8} };
int a=1, b=2;
float ans=0;

time(&t0); /* start time */
for(int cnt=0; cnt<1000000000; cnt++){

ans=div[a][b];

}
time(&t1);
elapsed = difftime(t1, t0);
cout<<"Time: "<<elapsed<<" seconds."<<endl;

time(&t0); /* start time */
for(int cnt=0; cnt<1000000000; cnt++){
ans=a/b;
}
time(&t1);
elapsed = difftime(t1, t0);
cout<<"Time: "<<elapsed<<" seconds."<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}

I will explain to you exactly why, at this time and for at least some
time in the future, your idea is, to put it kindly, impractical. The
greatest limiter on processor performance right now is bandwidth.

On a typical desktop processor today, your toy array of 25 floats
occupies 100 bytes, and ends up in the processor cache quickly. In
fact many compilers will notice that neither 'a', 'b' ever change, and
neither do the contents of the array member 'div[a][b]'. So they
might well read the value of 'div[1][2]' exactly once, or substitute
the value from the initializer.

In fact, a good many compilers will notice that the value assigned to
'ans' is not used, and omit the loop completely.

Now build a two dimensional array for all float values an IEEE 754
representation can represent, some 2^48 values of sizeof(float) bytes.
Then a 2^100 or so matrix of sizeof(double) to accommodate all the
doubles. And of course the long doubles, except on Mickeysoft
implementations.

And after you find a system with enough memory to hold the tables,
start doing your table lookup divisions with random values. Come back
and show us the results.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html