Derrick Coetzee wrote:
result.quotient = x * FIVE_INVERSE;
As an aside, on platforms with no hardware multiply, we can exploit the
regular bit pattern of FIVE_INVERSE to write this statement like this:
unsigned int temp = (x << 3) + (x << 2);
temp = (temp << 4) + temp;
temp = (temp << 8) + temp;
temp = (temp << 16) + temp;
result.quotient = temp + x;
The final program is then this, with 6 shifts, 1 AND, and 5-13 adds:
struct div_result {
unsigned int quotient;
unsigned int remainder;
};
#define FIVE_INVERSE 3435973837u
struct div_result divide10(unsigned int x) {
struct div_result result;
unsigned int xdiv4, temp;
result.remainder = x & 1;
x >>= 1;
xdiv4 = x >> 2;
temp = (x << 3) + (x << 2);
temp = (temp << 4) + temp;
temp = (temp << 8) + temp;
temp = (temp << 16) + temp;
result.quotient = temp + x;
if (result.quotient <= xdiv4) return result;
result.remainder += 2;
result.quotient -= FIVE_INVERSE;
if (result.quotient <= xdiv4) return result;
result.remainder += 2;
result.quotient -= FIVE_INVERSE;
if (result.quotient <= xdiv4) return result;
result.remainder += 2;
result.quotient -= FIVE_INVERSE;
if (result.quotient <= xdiv4) return result;
result.remainder += 2;
result.quotient -= FIVE_INVERSE;
return result;
}
Once again, exhaustively tested.
--
Derrick Coetzee
I grant this newsgroup posting into the public domain. I disclaim all
express or implied warranty and all liability. I am not a professional.