• Advertisement
Sign in to follow this  

Fractions for division?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok. Optimisation for software division using fractions and lut's is the name of the game. Basically, i've got two 32 bit numbers, and i would like to use fractions to find out the results of the division. I've thought of
a * 2^0 + b * 2^1 + c * 2^2
---------------------------
d * 2^0 + e * 2^1 + f * 2^2
As a 3 bit egsample. Now, my problem, is how would i use this to work out the division? From, Nice coder

Share this post


Link to post
Share on other sites
Advertisement
Easy. For your 3-bit example, you just create a lookup table with 26 3-bit entries. The index would be (in binary) abcdef.

For 32-bit division, it is just as easy. You just create a lookup table with 264 32-bit entries (only 64 exabytes of memory needed).

Share this post


Link to post
Share on other sites
Ok. I'm willing to have a 32^2 element lut.

Maybe a bit more.

But not over a few mb.

And an eb. NO way....

From,
Nice coder

Share this post


Link to post
Share on other sites
If x and y are bytes,

x/y is more or less equal to (x * ((1<<24)/y)>>24

and you can store (1<<24)/y in a lookup table with 256 entries.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Seems to me a cheap way to perform division on processors with multiplication but not division support is to first generate a good first guess interval (upper bound and lower bound) and then binary search the interval.

Worst case for 32-bit division would be 32 passes in the binary search but a good first guess interval table should get that down to 8 or fewer.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
If x and y are bytes,

x/y is more or less equal to (x * ((1<<24)/y)>>24

and you can store (1<<24)/y in a lookup table with 256 entries.


x & y are 32 bit numbers.

This makes it a little impractical.

From,
Nice coder

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Seems to me a cheap way to perform division on processors with multiplication but not division support is to first generate a good first guess interval (upper bound and lower bound) and then binary search the interval.

Worst case for 32-bit division would be 32 passes in the binary search but a good first guess interval table should get that down to 8 or fewer.


Yes. I know. I was just thinking for an alternitive to the bsearch.


From,
Nice coder

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement