# Low-Latency Bit-Accurate Architecture for Configurable Precision Floating-Point Division
## 3 Predict-Correct Algorithm for Division
### Guaranteed Bits per Cycle Using Predict-Correct Algorithm
To restrict \(R_{d}\) as follows: \(R_{d}<1/2^{(m\times t-t+2)}\), \(\delta_{0}\) should be restricted as follows: \(\delta_{0}<1/2^{(m\times t-t+3)}\), i.e., \(B\) can be truncated to be \(b_{b}=m\times t-t+4\) bits; meanwhile, the remaining \(\delta_{i}\) should be restricted to:  
\[\sum_{i=1}^{t}\delta_{i}<1/2^{(m\times t-t+3)}. \tag{11}\]  
We already have  
\[R_{b}=\sum_{S=t}^{\infty}B_{S+1}<\sum_{S=t}^{\infty}1/2^{(m\times g)}\times 1 /(Y_{h})^{(S+1)}=\frac{(1/2^{(m\times t)})\times(1/Y_{h})^{(t+1)}}{1-1/(2^{m} \times Y_{h})}. \tag{3}\]0  
where \(S\) is the follow-up \(n\)-bit digits after \(P^{\prime}\) in the partial quotient \(Q_{a}\). Since \(P^{\prime}\) is the truncated version of \(P=X_{h}\times B\) and \(X\) the left-shifted version of \(X^{\prime}\),  
\[ \begin{array}{l}X^{\prime}<X-P\times Y=X-X_{h}\times B\times Y\\ =\Delta X+X_{h}-X_{h}\times(1/Y-R_{b}-R_{c}-R_{d})\times Y=\Delta X+X_{h}\times (R_{b}+R_{c}+R_{d})\times Y\end{array}  \tag{13}\]  
Now substitute the bounds for \(R_{b}\), \(R_{c}\) and \(R_{d}\) into (13) to determine the maximum value of \(X^{\prime}\). Since \(X_{h}<1\) and \(\Delta X\leq 1/2^{p}-1/2^{q}\), the worst case for \(X^{\prime}\) is:  
\[X^{\prime}<\Delta X+R_{b}\times Y+R_{c}\times Y+R_{d}\times Y, \tag{14}\]  
\[X^{\prime}<1/2^{p}-1/2^{q}+\frac{1.1\times Y}{2^{(m\times t)}\times Y_{h}{}^{ (t+1)}}+\frac{Y}{2^{(m\times t-t)}}+\frac{Y}{2^{(m\times t-t+2)}}. \tag{15}\]  
Since \(Y_{h}\geq Y\), set \(Y_{h}=Y\) in the worst case for \(X^{\prime}\) and yield:  
\[X^{\prime}<1/2^{p}-1/2^{q}+\frac{1.1}{2^{(m\times t)}\times Y^{t}}+\frac{Y}{2 ^{(m\times t-t)}}+\frac{Y}{2^{(m\times t-t+2)}}. \tag{16}\]  
Take  
\[X_{2}=1/2^{p}-1/2^{q}+\frac{1.1}{2^{(m\times t)}\times Y^{t}}+\frac{Y}{2^{(m \times t-t)}}+\frac{Y}{2^{(m\times t-t+2)}}, \tag{17}\]  
then  
\[X^{\prime}<X_{2}. \tag{18}\]  
To determine the worst case of the value of \(X_{2}\) in the case of \(1/2\leq Y<1\), all possible maxima and minima should be located through setting the partial derivative \(\partial X_{2}/\partial Y\) to zero. It can be demonstrated that the highest possible value of \(X_{2}\) occurs at \(Y=1/2\). When \(p=m\times t-t+2\),  
\[X^{\prime}<\frac{0.25}{2^{(m\times t-t)}}-1/2^{q}+\frac{1.725}{2^{(m\times t -t)}}, \tag{19}\]  
\[X^{\prime}<1/2^{(m\times t-t-1)}. \tag{20}\]  
In Step 4 of every cycle, the highest-order bit of \(X^{\prime}\) that could possibly be 1 is the \((m\times t-t)\)th bit, \(X^{\prime}_{(q-m\times t+t)}\). For any \(p\) such that \(p\geq m\times t-t+2\), the worst case for the value of \(X^{\prime}\) is bounded by the above inequality. As a result, at least the front \(m\times t-t-1\) bits of quotient per cycle before Step 5 can be guaranteed in the proposed Predict-Correct algorithm. According to (12) and (13),  
\[X^{\prime}=X-P^{\prime}\times Y-S\times Y<X_{2}^{\prime}-S\times Y=X_{2} \times S-S\times Y. \tag{21}\]Since \(S\) is the follow-up \(n\)-bit digits after \(P^{\prime}\) in the partial quotient \(Q_{a}\), the worst case of the value of \(S\times Y\) also occurs in the case of \(1/2\leq Y<1\) after Step 5 and 6. Meanwhile, the highest possible value of \(X_{2}\) locates at \(Y=1/2\),  
\[X^{\prime}\leq 1/2^{(m\times t-t+n-1)}-1/2^{(m\times t-t+n)}, \tag{22}\]  
\[X^{\prime}\leq 1/2^{(m\times t-t+n)}. \tag{23}\]  
Similarly, the highest-order bit of \(X^{\prime}\) that could possibly be \(1\) is the \((m\times t-t+n)\)th bit. As for the subsequent \(n\)-bit predictive quotient values, the \(n\)-bit value is accurate within the least significant bit in Step 6. In short, at least the front \(m\times t-t+n-1\) bits of quotient per cycle after Step 6 can be guaranteed. Fast division [18] generates new quotient by \(m\times t-t-1\) bits per cycle. Therefore, the algorithm requires \(\lceil q/(m\times t-t-1)\rceil\) cycles where \(q\) is digit amount of dividend \(X\) and divisor \(Y\). Contrastively, the proposed Predict-Correct algorithm generates \(m\times t-t+n-1\) bits per cycle and its implementation requires \(\lceil q/(m\times t-t+n-1)\rceil\) cycles theoretically.