Arithmetic shift to divide by ODD number - Microprogrammed Control

Question

I'm trying to write the following instruction:

AC <-- AC / 3.

I know I can use arithmetic shift right in order to preform division by 2 but how can I preform a division by an odd number using only the possible instrcutions in microprogrammed control (micro-instructions).

Thank you

Answer 1

Another answer suggests divide by two, multiply by 2/3.

If you can multiply by 2/3, you can multiply by 1/3 just as easily (1/3 = .0101010101.. in binary) and skip the divide by two.

To multiply by 1/3, you can right shift the dividend two positions (corresponding to to multiplying by .01!) and add to an accumulator. Repeat the multiply (er, right shift twice, multiplying by .0001, .000001, ...) and add as many times as you need to handle the maximum number of bits you expect the dividend to have. Be careful about dividend bits that "fall off the end"; you either need a double-precision shifter/accumulator, or you need to scale the dividend by a positive power of two corresponding to the number of bits before you start to avoid loss of precision, assuming you have enough spare bits.

Dividing by other constants can be accomplished by multiplying by the bit that make up their reciprocal. It isn't quite so neat but the ideas are the same. You can figure out a variant of this that computes modulo (remainder) after dividing by a constant. Both of these are common tricks in compiler-generated code, too.

Answer 2

To divide by 3, divide by 2 first, then multiply by 2/3. In binary, 2/3 is 0.101010101.... If you have a shift through carry capability, you can:

1. Q <- Dividend SHR 2 (divide Dividend by 2)
2. Multiply the value Q by 1010101010101010 by a shift/add loop, resulting in a 32-bit Q value (a top 16-bit word and bottom 16-bit word)
3. Test the high bit of the lower 16-bit word. If it's 1, add 1 to the high 16-bit word of Q
4. The quotient of Dividend/3 is the top 16-bit word of Q

It's a bit of shifting and adding, though. Also, you might need 1010101010101011 instead of 1010101010101010 due to rounding. I modeled this method quickly in Ruby and it seemed to work on a couple of simple cases.

You might also be able to run a straight division algorithm (shift through carry, compare, subtract,...) on binary 11 into Dividend. You'd need a couple of spare registers for that. But it's usable on any divisor, not just 3. That's just microcoding a div instruction.