0

I've managed to get a hand on how SRT division works, but I haven't been able to construct a working example. My current sticking point is that e.g. the Pentium floating-point division bug came about because of a few errors in a look-up table for a 5-bit divisor and 7-bit numerator, which obviously is less than the floating point word size; but I have no idea how that actually works.

I'm unable to find an example of e.g. a 16-bit division, and am particularly interested in fixed-point division, to see precisely how this process works step by step. It's the most effective and cheap division algorithm I can find for pipelining, unless someone has a better way to find a reciprocal or $\dfrac{1}{\sin(x)}$ (CORDIC can't give me $\csc(x)$) without doing division or multiple multiplication operations (multiplication and division by powers of 2 are always welcome). In any case, it'd be good to have something somewhere clarifying how SRT works.

For the curious, I need to calculate $\dfrac{(\pi K)^3}{3}\times \left(\dfrac{1}{4K\sin(f_0\times\dfrac{pi}{f_s})}\right)^3$ which for $f_0=20$ and $f_s=96000$ can be…fun.

John Moser
  • 151
  • 8
  • This seems to be an ill posed problem. For 20 Hz this comes out to be almost 20 million, for 24000Hz it's 0.015. There is no way you can represent this in 16-bit fixed point. – Hilmar Nov 18 '21 at 15:22
  • An example of a 48-bit division would be excessive, and every example I've seen on the net has been like dividing a 7-bit numerator by a 4-bit divisor while talking about how you can use this to divide 64-bit numbers. Literally nowhere have I found an example of dividing numbers wider than the entries in the table, but I did find something saying the divisor absolutely had to be in the range 1 to 1.1111 or it won't work. I think I might have figured out how? Trying to construct a working one in Python to test, but Verilog is better at expressing this kind of thing. – John Moser Nov 19 '21 at 03:59

1 Answers1

0

After more research, I've found the answer to this. There are a few principles a person with little to no familiarity will need to understand.

Radix-4 SRT division itself produces two bits of a $q$ or quotient output, adds them to the prior result, and shifts left. The formula for this is $R_{i+1}=4\left(R_{i}+qD\right)$, where $D$ is the divisor and $R$ is the partial remainder. $q$ can be any value of $\{-2,-1,0,1,2\}$, which amount to a shift left and a negation; $4$ is a shift left by two bits.

The $q$ value is determined by considering the first several bits of $R_i$ and the first several bits of $D$. The redundant binary representation of the quotient allows for significant error here: it is sufficient to examine the first several bits of $R$ even if only propagating carry bits at the top few bits. This requires a carry-save adder.

Because addition is expensive itself, requiring each bit to be added in series to propagate the carry, Radix-4 dividers use a carry-save adder. Three bits can only ever produce one carry, and the carry bit is stored in a separate word. For example:

  1010 10
  1011 11
+ 1111 15
------
 10110 22 carry
 01110 14 result

Each step in Radix-4 division produces a partial remainder output and a quotient output. The quotient is shifted left two bits, and $q$ is added; so if the quotient coming in is $1101$ and the new $q$ bit is -1, then -1 is added to $110100$. Carry-save comes into play here as well: redundant binary representation is used, so the digits can be base 4 $[2,0,-1,1,-2,0]$. Converting this to non-redundant binary requires a series of additions. This is done on-the-fly, as subtraction in carry-save is simple: two's complement subtraction inverts all the bits and adds 1; carry-save inverts all the bits and sets the carry word LSB to 1, adding a simple xor to the path.

In short: each quotient digit is generated by appending two $0$ bits to the quotient carry and result, then adding or subtracting $1$ or $2$, or adding zero. For 16-bit division, this requires 8 operations, plus a final addition of the carry and result.

For a 16-bit addition, Radix-4 addition may examine the first 6 bits of $R$, but may need to propagate carry for the first 7 bits. In other words:

  1011 010|1 0010 1001 carry
+ 0110 111|1 0101 1100 result
----------------------
  0010 001

This is clearly erroneous: the last digit of the top 7 MSB should be 0; and the carry should propagate further, producing $0010010$. In the extreme, this propagation can flip all the output bits from 1 to 0. This turns out to not matter, which allows the use of a smaller, faster adder when dividing figures of unbounded size: 8,192-bit division requires a 7-bit addition here, just like it can perform the carry-save add in parallel as a number of 1-bit additions.

The redundant binary representation causes errors in the opposite direction, on balance, so the result comes out correct anyway: a given integer can be represented in multiple ways in RBR. This also creates a sort of gray area where so long as you consistently produce the same $q$ value, your table of $q$ values can have arbitrary selections between two values for some ranges, for example a particular $R_i$ and $D$ may allow either $q=1$ or $q=0$, so long as it always produces the same $q$.

I'll update this later with an example pointing out each of these things as they come into play.

John Moser
  • 151
  • 8
  • That was it, yeah. I've since switched to an SRT divider since it's twice as fast and trivial to pipeline (generating the q value only takes like 25 gates on ASIC or 3 LUT6 on Xilinx 7-series, logic depth of 7 gates or 2 LUTs…32-bit division is tiny and incurs almost the same delay as a 32-bit adder apparently).

    For the final shift, I came up with a trivial modification of a barrel shifter (and then optimized to be much smaller and lower delay) that takes a positive/negative value and demarcates a mask, and use that and a barrel rotate to shift by a positive/negative number of bits.

     – John Moser Dec 17 '21 at 20:13