a * 2^0 + b * 2^1 + c * 2^2
---------------------------
d * 2^0 + e * 2^1 + f * 2^2
Fractions for division?
Author
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
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).
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).
Author
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
Maybe a bit more.
But not over a few mb.
And an eb. NO way....
From,
Nice coder
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 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.
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.
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.
Author
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
Author
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement