Faster way for any number(16bit) divide by 3 in assembly without DIV opcode

Question

I want to divide a unsigned integer by 3, in 8086 assembly or similar , any way to do it faster which I dont want to use DIV opcode.

Answer 1

The essential answer is to "multiply by the reciprocal of your desired constant", using shifts-and-adds to carry out the multiply, and then some possible post-shifts to position the binary point properly.

The trick is figuring out what the precision of the reciprocal must be, to handle the size of the largest input dividend you expect. You can obviously decide the largest input operand is the entire register, but if you know more, you can use a reciprocal with fewer bits which gets you a faster shift-add style multiply.

Cuoq's answer provides good reference material.

Answer 2

Read the appropriate chapter 10 “Integer division by constants” of the book Hacker's Delight. Bonus content is available for that chapter (but not the chapter itself).

Or use libdivide, a library that will apply known algorithms in a first step to find the proper constants, so that the division by a given denominator is then faster.

As pointed out on the libdivide page, compilers know how to transform divisions by compile-time constants into multiplications and shifts, so the simplest way may just be to use a compiler. I would do it for you but I do not have a 16-bit compiler. If done with a 32-bit compiler, the result is as follows:

    movw    $-21845, %ax
    mulw    8(%ebp)
    andl    $65534, %edx
    movl    %edx, %eax
    shrl    %eax

For the C function:

int f(unsigned short d)
{
  return d / 3;
}