# 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  
There are three sources of inaccuracy affecting the approximation \(B\approx 1/Y\). Define the source by \(B=1/Y-R_{b}-R_{c}-R_{d}\). \(R_{b}\) represents an error due to truncating the Taylor series after \(t\) terms. Since the truncated terms in the series are all nonnegative, \(R_{b}\) is nonnegative. \(R_{c}\) represents the error in using look-up table with finite width words to calculate \(B\). As tables are rounded down, \(R_{c}\) is always nonnegative. \(R_{d}\) represents the error in truncating the arithmetic used to calculate \(B\). To obtain the maximal value of \(X\), \(R_{b}\), \(R_{c}\), and \(R_{d}\) should be accurately bounded. The \((w+1)\)th term of the Taylor series for \(B\) is \(B_{w+1}=(-\Delta Y)^{w}/Y_{h}^{(w+1)}\). The worst case occurs when \(-\Delta Y=1/2^{m}-1/2^{q}\), the bound holds:  
\[B_{w+1}<\left(1/2^{(m\times w)}\right)\times\left(1/(Y_{h})^{(w+1)}\right). \tag{2}\]  
Therefore, the remainder \(R_{b}\) is bounded by  
\[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}\]  
For \(m>>1\),  
\[\frac{(1/2^{(m\times t)})\times(1/Y_{h})^{(t+1)}}{1-1/(2^{m}\times Y_{h})} \tag{4}\]  
is just greater than \((1/2^{(m\times t)})\times(1/(Y_{h})^{(t+1)})\). For \(m>>5\), a nonstringent bound can be posed on \(R_{b}\):  
\[R_{b}<\frac{1.1}{2^{(m\times t)}\times Y_{h}^{(t+1)}}. \tag{5}\]  
Suppose the error in each table look-up is \(\epsilon_{i}\) and the truncation error in computing each multiplicative term is \(\delta_{i}\). Let \(\delta_{0}\) be an additional term that represents truncating \(B\) to a certain number of bits after the summation. A cumulative error will be  
\[B=\sum_{i=1}^{t}\left[\delta_{i}+(\epsilon_{i}+1/Y_{h}^{i})\times(-\Delta Y)^ {i-1}\right]=\sum_{i=1}^{t}\left[\frac{(-\Delta Y)^{i-1}}{Y_{h}^{i}}\right]+ \sum_{i=1}^{t}\left[\epsilon_{i}\times(-\Delta Y)^{i-1}\right]+\sum_{i=1}^{t} \delta_{i}. \tag{6}\]  
Then,  
\[R_{c}=\sum_{i=1}^{t}\epsilon_{i}\times(-\Delta Y)^{i-1}, \tag{7}\]  
and  
\[R_{d}=\sum_{i=1}^{t}\delta_{i}. \tag{8}\]  
Since table \(G_{i}\) is \(b_{i}\) bits wide and \(1/2<Y_{h}<1\), the maximal value of \((1/Y_{h})^{i}\) is slightly less than \(2^{i}\). If words in table \(G_{i}\) can represent values up to but not including \(2^{i}\), the unit of the most significant bit in table \(G_{i}\) should have value \(2^{(i-1)}\) while the unit of the least significant bit should have value \(1/2^{(bi-i)}\). Each \(\epsilon_{i}\) is less than the unit of the LSB: \(\epsilon_{i}<1/2^{(bi-i)}\). The worst case for \(-\Delta Y\) occurs when \(-\Delta Y=1/2^{m}-1/2^{q}\). Replace \(-\Delta Y\) in (6) with \(1/2^{m}-1/2^{q}\) and yields  
\[R_{c}=\sum_{i=1}^{t}\ 1/2^{(b_{i}-i)}\times 1/2^{(m\times i-m)}, \tag{9}\]  
i.e.,  
\[R_{c}=\sum_{i=1}^{t}\ 1/2^{(b_{i}+m\times i-m-i)}. \tag{10}\]\(\delta_{i}\) represents each maximal permissible truncation error and it allows the arithmetic of \(B\) to be reduced into an appropriate size to accelerate the computation of \(B\). The allowable truncation error \(\delta_{i}\) can be used both in discarding least significant partial products to prune multiplier trees and in truncating results to smaller widths. As \(1\leq B<2\), the most significant bit (MSB) of \(B\) has unit 1. Suppose \(B\) is truncated to \(b_{b}\) bits. According to the definition of \(\delta_{0}\), \(\delta_{0}\) is less than the LSB, i.e., \(\delta_{0}<1/2^{(bb-1)}\).