#26343 - funkeejeffou - Mon Sep 13, 2004 2:29 pm
Hi,
I already use div tabs in my project as they are simple to implement, but I've been thinking lately about using reciprocal div tabs.
After thinking and googling around, I still can't figure out how to compute it in an array form(the only way I found by myself was using a binary tree).
The main issue is determining what x value is when I have 1/x value in an FixedPoint format.
Example :
1/x = 106 in FP16
is equivalent to 2^16/x = 106
is equivalent to 65536/x = 106
x = 65536/106
x = 618
so I'd like to avoid that division by having an array :
reciprocal[106] = 618
I've seen on the forum some posts concerning reciprocal LUT tables, is it the same thing? How are they precomputed?
Thanks, Jeff.
#26345 - lordmetroid - Mon Sep 13, 2004 3:03 pm
you create your table by dividing with N where N is the range you would like to be able to divide any number with...
For example 1 to 255...
you create the table by dividing 1 as it would be in the fixed point, ie if you use an X.8 fixed point your one would be 256... and so you would need to divide 256 with all N...
However this isn't enough further more you need to add +1 to every element in the table as it seems it doesn't round the number correctly otherwise...
Also as you divide by using a multiplication Y*table(N) you need to shift your result to the left like you would be doing in a FP multiplication.
_________________
*Spam*
Open Solutions for an open mind, www.areta.org
Areta is an organization of coders codeing mostly open source project, but there is alot of sections like GBA dev, Language learning communities, RPG communities, etc...
#26351 - funkeejeffou - Mon Sep 13, 2004 5:37 pm
Thanks lord metroid, but I'm not sure I'm getting what you are telling me.
Could you just post an example or some algorithmic so I can figure it out?
Cheers, Jeff.
#26354 - Master S - Mon Sep 13, 2004 6:02 pm
For a tabel in range 1 to 255 you would do
| Code: |
static unsigned int Divtab[256];
void BuildDivTab(void)
{
int i;
for(i=1;i<256;i++)
DivTab[i] = 256 / i;
}
|
to divide by 8 you do
| Code: |
| x = (40 * DivTab[8]) >> 8; // x = 40 / 8 |
Hope that helps :)
#26356 - lordmetroid - Mon Sep 13, 2004 6:11 pm
actually do:
| Code: |
for(i = 1;i<256;i++)
gba_fpm_div[i] = (256/i)+1;
|
but don't use only X.8 fixed point, the precision will be so awfull it becomes useless to try to calculate anything, rather use a 1.15 format... for your table, however after you used the division table you would need to shift it an additional 7 left in order to get it to become X.8
_________________
*Spam*
Open Solutions for an open mind, www.areta.org
Areta is an organization of coders codeing mostly open source project, but there is alot of sections like GBA dev, Language learning communities, RPG communities, etc...
#26360 - funkeejeffou - Mon Sep 13, 2004 6:26 pm
Erf...
Looks like there is a quiproco here :)
I know how to build div tabs as my first post said, and I wanna reverse the operation, that is why it is a RECIPROCAL div tab.
From the result of the division, i'd like to guess the denominator.
My example was pretty clear thought, thanks anyway ;)
So how about the reciprocal stuff?
#26361 - DekuTree64 - Mon Sep 13, 2004 6:52 pm
Well, it's the same thing. If you go through doing table[x] = 65536/x, then like in your original post, table[106] = 618, and table[618] = 106. Both are true all the time, because the reciprocal of the reciprocal is the original number.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#26365 - funkeejeffou - Mon Sep 13, 2004 7:40 pm
Geez... Thanks DekuTree64, sometimes we try to complicate things as they do not need it.
I definitely should sleep more :)
Thanks again !
Cheers, Jeff.
#26488 - keldon - Thu Sep 16, 2004 11:50 pm
So in summary if I wish to build a table it needs bits^2 entries, and each entry recTable[f]= bits^2 / f; and to divide by f, I would write a = num * recTable [f].
I tried it with 8; pretty neat, I didn't know that.