Hi there! I’m back, with the latest part in the series: Pregenerated arrays. This is a fairly simple concept that can treble the speed of your code, so have a look.

DENTHOR, coder for ...
_____   _____   ____   __   __  ___  ___ ___  ___  __   _____
/  _  \ /  ___> |  _ \ |  |_|  | \  \/  / \  \/  / |  | /  _  \
|  _  | \___  \ |  __/ |   _   |  \    /   >    <  |  | |  _  |
\_/ \_/ <_____/ |__|   |__| |__|   |__|   /__/\__\ |__| \_/ \_/
smith9@batis.bis.und.ac.za
The great South African Demo Team! Contact us for info/code exchange!  

Grant Smith, alias Denthor of Asphyxia, wrote up several articles on the creation of demo effects in the 90s. I reproduce them here, as they offer so much insight into the demo scene of the time.

These articles apply some formatting to Denthor's original ASCII files, plus a few typo fixes.

Why do I need a lookup table? What is it?

A lookup table is an imaginary table in memory where you look up the answers to certain mathematical equations instead of recalculating them each time. This may speed things up considerably. Please note that a lookup table is sometimes referred to as a pregenerated array.

One way of looking at a lookup table is as follows: let us say that for some obscure reason you need to calculate a lot of multiplications (e.g. 5*5 , 7*4 , 9*2 etc.). Instead of actually doing a slow multiply each time, you can generate a kind of bonds table, as seen below :

	1	2	3	4	5	6	7	8	9
1	1	2	3	4	5	6	7	8	9
2	2	4	6	8	10	12	14	16	18
3	3	6	9	12	15	18	21	24	27
4	4	8	12	16	20	24	28	32	36
5	5	10	15	20	25	30	35	40	45
6	6	12	18	24	30	36	42	48	54
7	7	14	21	28	35	42	49	56	63
8	8	16	24	32	40	48	56	64	72
9	9	18	27	36	45	54	63	72	81

This means that instead of calculating 9*4, you just find the 9 on the top and the 4 on the side, and the resulting number is the answer. This type of table is very useful when the equations are very long to do.

The example I am going to use for this part is that of circles. Cast your minds back to (see part 3 on lines and circles. The circle section took quite a while to finish drawing, mainly because I had to calculate the Sin and Cos for EVERY SINGLE POINT. Calculating Sin and Cos is obviously very slow, and that was reflected in the speed of the section.

How do I generate a lookup table?

This is very simple. In my example, I am drawing a circle. A circle has 360 degrees, but for greater accuracy, to draw my circle I will start with zero and increase my degrees by 0.4. This means that in each circle there need to be 8000 Sins and Coss (360 / 0.4 = 8000). Putting these into the base 64k that Pascal allocates for normal variables is obviously not a happening thing, so we define them as pointers in the following manner:

        TYPE   table = Array [1..8000] of real;

        VAR    sintbl : ^table;
               costbl : ^table;

Then in the program we get the memory for these two pointers. Asphyxia was originally thinking of calling itself Creative Reboot Inc., mainly because we always forgot to get the necessary memory for our pointers. (Though a bit of creative assembly coding also contributed to this. We wound up rating our reboots on a scale of 1 to 10 ;-)). The next obvious step is to place our necessary answers into our lookup tables. This can take a bit of time, so in a demo, you would do it in the very beginning (people just think it’s slow disk access or something), or after you have shown a picture (while the viewer is admiring it, you are calculating pi to its 37th degree in the background ;-)) Another way of doing it is, after calculating it once, you save it to a file which you then load into the variable at the beginning of the program. Anyway, this is how we will calculate the table for our circle :

    Procedure Setup;
    VAR deg:real;
    BEGIN
      deg:=0;
      for loop1:=1 to 8000 do BEGIN
        deg:=deg+0.4;
        costbl^[loop1]:=cos (rad(deg));
        sintbl^[loop1]:=sin (rad(deg));
      END;
    END;

This will calculate the needed 16000 reals and place them into our two variables. The amount of time this takes is dependent on your computer.

How do I use a lookup table?

This is very easy. In your program, wherever you put

cos (rad(deg)),

you just replace it with:

costbl^[deg]

Easy, no? Note that the new deg variable is now an integer, always between 1 and 8000.

Where else do I use lookup tables?

Lookup tables may be used in many different ways. For example, when working out 3-dimensional objects, sin and cos are needed often, and are best put in a lookup table. In a game, you may pregenerate the course an enemy may take when attacking. Even saving a picture (for example, a plasma screen) after generating it, then loading it up later is a form of pregeneration.

When you feel that your program is going much too slow, your problems may be totally sorted out by using a table. Or, maybe not. ;-)

In closing

As you have seen above, lookup tables aren’t all that exciting, but they are useful and you need to know how to use them.