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

Question

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?

Answer 1

By using Booth's restoring division algorithm

Answer 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.