Building a lookup table for fixed point division

This topic is 4862 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hello there! I´m trying to make a look up table with reciprocals so that I can use it in my 16.16 format fixed-point division macro and replace the division by a multiplication (it´s a for a GBA project). Nonetheless, I´m having trouble in figuring out how should I create the table. This is the macro I´m currently using to perform the division: #define FIXP1616_DIV(fixpN1,fixpN2) ((fixpN1)<<8)/((fixpN2)>>8) And I would like to replace it by: #define FIXP1616_DIV(fixpN1,fixpN2) ((fixpN1)<<8)*(invlut[(fixpN2)>>8]) Which formula should I use to fill the invlut array? Thanks in advance for your help! --Ignacio

Share on other sites
With some basic manipulation:

Presume the two following defines are equal:
#define FIXP1616_DIV(fixpN1,fixpN2) ((fixpN1)<<8)/((fixpN2)>>8)
#define FIXP1616_DIV(fixpN1,fixpN2) ((fixpN1)<<8)*(invlut[(fixpN2)>>8])

After eliminating mathematically-unneeded parenthesis, it follows that:
(fixpN1<<8)/(fixpN2>>8) = (fixpN1<<8)*invlut[fixpN2>>8]

If (fixpN1<<8) is nonzero, it can be eliminated from the equation:

1.0 / (fixpN2>>8) = invlut[fixpN2>>8]

Thus, you just need to do a loop through all the fixpN2 that you want to use and set invlut[fixpN2>>8] to 1.0 / (fixpN2>>8), representing 1.0 correctly in your fixed point system, of course. Really, you can eliminate the shifts (only in the part where you calculate the table) and set invlut[fixpN2] to 1.0 / fixpN2 so at initialization time you do much less calculations.

If you'd rather have the table in memory than precompute it on each run, just make a program to compute the proper values and save them to a file. Then you can reformat the file and include it in your program as an array initializer.

Share on other sites
Extrarius, thanks for replying to my post!

Quote:
 Original post by ExtrariusReally, you can eliminate the shifts (only in the part where you calculate the table) and set invlut[fixpN2] to 1.0 / fixpN2 so at initialization time you do much less calculations.

I arrived at this very same result before opening this thread, but then I realized that 1.0f / fixpN2 (where 1.0 is 65536 in my 16.16 system) yields a floating point number and I´d like to store the table in integer format. Can you help me with this?

Quote:
 Original post by ExtrariusIf you'd rather have the table in memory than precompute it on each run, just make a program to compute the proper values and save them to a file. Then you can reformat the file and include it in your program as an array initializer.

Yes, someone else suggested me this trick in another thread and I´m using it to store the sin and cos tables. Thanks again for all your input!

--Nacho

Share on other sites
Quote:
 Original post by Ignacio Liverotti[...]I arrived at this very same result before opening this thread, but then I realized that 1.0f / fixpN2 (where 1.0 is 65536 in my 16.16 system) yields a floating point number and I´d like to store the table in integer format. Can you help me with this?[...]
It should generate a fixed point number, not a floating point number.

Basically, you're just using your first define with fixpN1 equal you 1 to initialize the table.

Share on other sites
I recommend the book "Hackers Delight". It has a chapter on how to do such divisions, with code and detailed discussions of techniques. It has a web page here:

http://www.hackersdelight.org/

but it only gives a taste of the book which is well worth tracking down for this and other fixed point techniques.

Share on other sites
Thanks for the replies!

@ Extrarius: I checked the math again in paper and realized that I was wrong: 65536 / fixpN2 is a fixed point number so thanks for pointing out my mistake. I managed to code a simple function that creates the table and dumps it into a text file:

voidCreateInvLUT(char *lpFilename){		int i;	FIXP1616 fixpVal,fixpAux;	FILE *lpFile;	if(NULL==(lpFile=fopen(lpFilename,"w"))) {		printf("Error al abrir el archivo.\n");		return;	}	fprintf(lpFile,"FIXP1616 fixpInvLookUp[65536] = {\n");	fprintf(lpFile,"0, ");	for(i=1;i<65536;i++) {		if(i%16==0)			fprintf(lpFile,"\n");		fixpAux = (i << 16);		fixpVal = FIXP1616_DIV(FIXP1616_ONE,fixpAux);		fprintf(lpFile,"%d, ",fixpVal);	}	fprintf(lpFile,"};\n");	fclose(lpFile);	return;} /* End CreateInvLUT() */

where:

#define FIXP1616_ONE 65536
#define FIXP1616_PROD(fixpN1,fixpN2) (((fixpN1)>>8)*((fixpN2)>>8))
#define FIXP1616_DIV(fixpN1,fixpN2) ((fixpN1)<<8)/((fixpN2)>>8)

I redefined the division macro in the following way:

#define FIXP1616_NEWDIV(fixpN1,fixpN2) FIXP1616_PROD((fixpN1),(fixpInvLookUp[(fixpN2)>>16]))

Now the program´s output (a spinning wireframe triangle) is slightly different than the one produced by the older version of the macro. That is, it displays a somewhat smaller triangle. I suspect that this has something to do with accuracy or maybe sign, but I´m not sure. Do you have any idea of what´s going on here? Thanks again for your input!

@ johnb: Very nice book. I´ve skimmed through the sample chapter and looks promising. Thanks for the link!

--Nacho

Share on other sites
Quote:
Original post by Ignacio Liverotti
Quote:
 Original post by ExtrariusIf you'd rather have the table in memory than precompute it on each run, just make a program to compute the proper values and save them to a file. Then you can reformat the file and include it in your program as an array initializer.

Yes, someone else suggested me this trick in another thread and I´m using it to store the sin and cos tables. Thanks again for all your input!
If you're storing sin & cos tables, then be aware that you can overlap three quarters of the cos table with the sin table reducing the memory usage FOR FREE (no additional operations necessary). Just make the sin table 25% longer and make the cos table simply a pointer to the sin table at the 25% mark.

If you add a little logic you can reduce the memory usage furthur by reflecting the answer in various ways, but only do that if you're short on memory.

One question... Is the division table purely because accurate 16.16 division really requires 48 bit maths (and you don't have math operations that large), or are you just wanting to make it faster by using tables?

I suggest that you make a few test cases to see if your division comes out very accurate. Try extremes, and things such as in the following psuedocode:
FIXP1616_NEWDIV(0x0000.1000, 0x1000.0000) == 0x0000.0001FIXP1616_NEWDIV(0x0000.0001, 0x0001.0000) == 0x0000.0001FIXP1616_NEWDIV(0x0000.0001, 0x0000.0001) == 0x0001.0000FIXP1616_NEWDIV(0x0001.0000, 0x0001.0000) == 0x0001.0000FIXP1616_NEWDIV(0x1000.0000, 0x1000.0000) == 0x0001.0000FIXP1616_NEWDIV(0x1000.0000, 0x0001.0000) == 0x1000.0000FIXP1616_NEWDIV(0x0000.1000, 0x0000.0001) == 0x1000.0000

Share on other sites
Quote:
 Original post by iMalcIf you're storing sin & cos tables, then be aware that you can overlap three quarters of the cos table with the sin table reducing the memory usage FOR FREE (no additional operations necessary). Just make the sin table 25% longer and make the cos table simply a pointer to the sin table at the 25% mark.

Thanks for the tip! I´ll change my current approach, then.

Quote:
 Original post by iMalcIf you add a little logic you can reduce the memory usage furthur by reflecting the answer in various ways, but only do that if you're short on memory.

Yes, but this would add a little overhead to the macro´s performance and I´d rather use a few extra bytes than getting a (small) performance hit. Thanks anyway for this tip, too!

Quote:
 Original post by iMalcOne question... Is the division table purely because accurate 16.16 division really requires 48 bit maths (and you don't have math operations that large), or are you just wanting to make it faster by using tables?

I´m doing this table because I´ve read that divisions in the Game Boy Advance are a definite no-no. Of course, I´ve found tons of optimized routine divisions in ARM assembly but I believe that the look up table approach might be a little bit faster and, since I perform lots of divisions every frame, I´d like to take the best route.

Quote:
 Original post by iMalcI suggest that you make a few test cases to see if your division comes out very accurate. Try extremes, and things such as in the following psuedocode: [...]

All right, I´ll try them and I´ll let you know about the results.

--Nacho

Share on other sites
@ iMalcI: Sorry for taking so long to reply! Today it´s the first day I managed to sat down for a couple of hours to troubleshoot my problem. I finally found the problem and fixed it so I´m going to explain it here in case somebody else experiences this problem someday.

The problem: In one of the last transformation functions in the pipeline (the one that performs the camera to perspective transformation) there is a division by 200. The precomputed value stored in the table for 1/200 is 327 (in fixed point format) which is okay since 327/65536.0f = 0.00498f = 1/200. The problem occurs when the FIXP1616_PROD macro (see above) is called because 327 is shifted 8 bits to the right and most lower bits are lost

The solution: Change the FIXP1616_PROD macro so that instead of shifting both numbers 8 bits to the right, it shifts the first one 12 and the second one 4, like this:
#define FIXP1616_PROD(fixpN1,fixpN2) (((fixpN1)>>12)*((fixpN2)>>4))

Of course, this change is made taking into account that the look up table´s element is fixpN2.

Thanks again to everyone that helped me on this issue!

--Nacho

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 11
• 15
• 14
• 46
• 22
• Forum Statistics

• Total Topics
634054
• Total Posts
3015274
×