FPGA-FAQ    0018

Divide An Integer by N.5

FAQ Entry Author Philip Tsao
FAQ Entry Editor Philip Freidin
FAQ Entry Date 2004/07/31

Q. Divide by N.5

Dividing an integer by (N + 1/2) where N is an integer and rounding
the quotient towards zero not any more difficult than plain integer
division. (N + 1/2) can also be expressed as (2N+1)/2. Simply shift
both the dividend and N (the divisor minus 1/2) left by one bit
(multiplication by 2) and add 1 to 2N. Find the integer quotient of
twice the dividend divided by (2N+1), chop off the least significant
bit and you're left with the desired result!

There are several ways to perform integer division. They range from the
simple but agonizingly slow...

  // this takes O(2^N) time where N is number of bits
  remainder := dividend;
  quotient := 0;
  while remainder >= divisor do
    remainder := remainder - divisor;
    quotient := quotient + 1;
  end while

...to the faster but more complicated
circuits detailed here
and here.