'Divide by a number which is not power of 2 in Verilog RTL coding

For multiplication and division, we can use the left and right shifts.

x>>2  // it will right shift by 2. ---> 2^2=4. (Multiply by 4 or divide by 4, depends on MSB/LSB)

However, if we want to divide by a number that isn't the power of 2, how can we achieve the required purpose?

verilogregister-transfer-level


Solution 1:[1]

By using Booth's restoring division algorithm

Solution 2:[2]

Booth's algorithm is an additive one and can take a comparatively longer time than the multiplicative algorithms, like the Newton-Raphson algorithms found in this educational PDF.

Each next approximation is calculated using the previous approximation.

X(N+1) = X(N)(2 - b * X(N)), where x(0)=1

So, to find the inverse of b, i.e. 1/b, where b=0.6 (error=e(x)), it takes about 5 iterations.

  1. X(000) = 1.000
  2. X(001) = 1.000 * (2 - (1.000 * 0.6)) = 1.400
  3. X(002) = 1.400 * (2 - (1.400 * 0.6)) = 1.624
  4. X(003) = 1.624 * (2 - (1.624 * 0.6)) = 1.6655744
  5. X(004) = X(003) * (2 - (X(003) * 0.6)) = 1.666665951
  6. X(005) = X(004) * (2 - (X(004) * 0.6)) = 1.666666668

which approximates the answer, which is 1.6666666667.

I included this example in case the referenced PDF disappears. See the referenced PDF or look up the Newton-Raphson algorithm for more information.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Edmund
Solution 2 MicroservicesOnDDD

Related Questions