# Fractions for division?

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

## 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 on other sites
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 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 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 on other sites
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 on other sites
Quote:
 Original post by ToohrVykIf x and y are bytes,x/y is more or less equal to (x * ((1<<24)/y)>>24and 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 on other sites
Quote:
 Original post by Anonymous PosterSeems 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

1. 1
Rutin
33
2. 2
3. 3
4. 4
5. 5

• 10
• 14
• 9
• 9
• 9
• ### Forum Statistics

• Total Topics
633331
• Total Posts
3011395
• ### Who's Online (See full list)

There are no registered users currently online

×