6

Hi all I'm trying to divide by an unsigned constant using only shifts and adds/subtracts - I have no problem with this if it were multiplication, but I'm a bit stumped by the division.

For example, lets say the constant divisor is 192 and lets say the dividend is 8000

"full result" y = 8000/192 = 41 (assuming I'm not keeping fractional bits)

y = 8000 >> 8 ... 31 y = 8000 >> 7 ... 62

But how do I get a more accurate solution?

Many thanks!

3
  • On further reflection the answer is obvious .... 1/192 = 5.208x10^-3 there 1/2^8 + 1/2^10 + 1/2^12 .... adding terms until sufficient accuracy is reached.
    – trican
    Commented Feb 3, 2011 at 13:24
  • Just a note: assuming this is for an architecture with a good optimizing compiler, for a given divisor you could compile the division using full optimization and look at the output. Modern optimizing compilers are very good at determining what sort of math/bit-manipulation (if any) would run fastest for a given computation. Commented Feb 3, 2011 at 20:30
  • That is equivalent to multiplication by a fixed point representation of the number. This will not have the same rounding behavior as an actual division, so an optimizing compiler probably won't do it.
    – phkahler
    Commented Feb 3, 2011 at 20:48

4 Answers 4

10

There is almost certainly a more elegant way to do it, but here's enough to get you started.

Usually division in this way is done by multiplying by the reciprocal, i.e., first multiplying and then right-shifting.

(Note: remember that multplication can be accomplished by shifts and adds (e.g. n * 3 = (n*2) + (n*1) = (n << 1) + (n) ) but I'm just going to use multiplication here. Your question said "shifts & adds" and I'm justifying my shorthand use of multiplication)

In the examples below, I'm trying to explain the concepts with an example. In your specific case, you'll want to consider issues such as

  1. sign (I'm using unsigned ints below)

  2. overflow (below I'm using 32-bit unsigned longs to hold intermediate values but if you're on a smaller uC beware, adjust accordingly

  3. rounding (e.g. should 9/5 return 1 or 2? In C, it's 1, but maybe you want 2 because it's closer to the correct answer?)

  4. To the extent that you can (available bits), do your all of your multiplies before your divides (minimizing truncation errors). Again, be aware of overflow.

As I said, read the below to understand the concepts, then tailor to your needs.

Dividing by 192 is the same as multiplying by 1/192, which is the same as dividing by (64 * 3). There is not an exact (finite) binary representation of 1/3, so we're approximating it with 0x5555/(1 << 16).

To divide by 192, we divide by 64 and then divide by 3. To divide by 3, we multiply by 0x5555 and shift right by 16 (or multiply by 0x55 and >> 8, or...)

//                8000/192          =
//                ((8000/64)/3)     =
//                ((8000 >> 6) / 3) =
//                (((8000 >> 6) * 0x5555) >> 16)
//                (((8000 * 0x5555) >> 22

Please note that the parentheses are intentional. You don't want to compute (8000 * (0x5555/(1 << 16)) because the 2nd term is 0, and the product would be 0. Not good.

So a 1-liner in code would be something like:

 printf("Answer:  %lu\n", ((8000UL * 0x5555UL) >> 22));

This will yield 41, which is what "C" would yield for 8000/192, even though 42 is "closer". By checking LSBs you could round if you wanted to.

One could write a treatise on this topic, but fortunately someone much smarter than me already has.

3
  • problem is you have a multiply. supposed to be only shift, add, sub
    – old_timer
    Commented Feb 4, 2011 at 14:36
  • @dwelch, please read the 3rd paragraph again. It starts with (Note:
    – Dan
    Commented Feb 4, 2011 at 23:47
  • this answer provides an explanation and a link to another source. It uses enough bits in the inverse to make sure the result is a truncated (rounded down) result of the exact answer. In the case of divisors like 7, the inverse is one bit larger than single word size so a 5 instruction sequence is used instead of a 3 instruction sequence.
    – rcgldr
    Commented Dec 1, 2023 at 20:48
6

i have developed a constant division generator that can easily give you optimized divisions by any constant. It follows the ideas from "Hacker's Delight".

The tool named "kdiv" is available at sourceforge:

http://sourceforge.net/projects/kdiv/

2

I would look at the hackers delight book for this sort of thing. I dont have my copy with me, but independent of that if you look at your divisor 192, that is 0xC0, so you can divide the top and bottom by 0x40, shift 8000>>6 = 125. 8000/192 -> 125/3, but then you have to do that divide by 3. We know the answer will be somewhere between 125/2 and 125/4. With these specific numbers 125 is 0x7d or b1111101 which is 3 times b100000 + 11101 which is (3 times 0x20) + (3 times 8) + 5 so 125/3 = 0x20 + 0x8 + (5/3) and 5/3 is quickly determined as more than 1 but less than 2 so 0x28+1 = 41. Only continues to reduce with shifts if the divisor bit pattern keeps showing up on the upper bits of the numerator bit pattern. I dont know what the hackers delight or other similar sources say about the matter, I just happened to notice this pattern for these specific numbers.

0
0

If you sum a pack of shift downs you divide by a non power of 2.

How you get the powers you need is to get the msb and divide it by the number, and then this will output the number with the bits on where you add them together to get the divide you need.

The problem is, it requires a divide to get the number, so your stuck only dividing by constants.

There is a way to compute the number without divide, but in hardware it doesnt look much different or better than the divide with the condition in it, on the surface, but im not sure if its better of worse.

But if u want to do a variable divide, get the msb and multiply it by the number your dividing by. (So it requires a multiply at the start, but u have those variably.)

then shift it down by 2.

Then check if its above or below the msb, and that is if the msb is on or off as a component in the divide sum.

shift it down by 2 again.

And ur either above the last test, or below the last test by this number, depending on if you were on or off as a component on the last significance.

Keep going like that, then you can do the sum of shifts divide variably.

So its->

CIELING=MSB*DIVIDING NUMBER // do this via sum of shifts.
CHECK1=CIELING/2
if(above CHECK1) { component0=on. }
            else {component0=off.}
CHECK2=CIELING/4
if(component0 on) { CHECK2=CHECK1+CHECK2}
             else { CHECK2=CHECK1-CHECK2}
if(above CHECK2) { component1=on. }
            else {component1=off.}
CHECK3=CIELING/8
if(component1 on) { CHECK3=CHECK2+CHECK3}
             else { CHECK3=CHECK2-CHECK3}    
if(above CHECK3) { component2=on. }
            else {component2=off.}

//then once have all components, do the final sum of shifts.

ANSWER=(INPUT>>component0)+(INPUT>>component1)+(INPUT>>component2);

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.