# Low-Latency Bit-Accurate Architecture for Configurable Precision Floating-Point Division
## 3 Predict-Correct Algorithm for Division
### Predict-Correct Algorithm with Accurate Quotient Approximation  
In the Predict-Correct algorithm, truncated versions of the integer dividend \(X\) and divisor \(Y\) are used, denoted \(X_{h}\) and \(Y_{h}\). \(X_{h}\) is defined as the high-order \(p\) bits of \(X\) extended with 0s to obtain a \(q\)-bit number, i.e., \(X_{h}=X_{(q-1)}\dots\ X_{(q-p)}00\dots\ 00\) where the number of 0 in \(X_{h}\) is \(q-p\). Similarly, \(Y_{h}\) is defined as the high-order \(m\) bits of \(Y\) extended with 1s to obtain a \(q\)-bit number, i.e., \(Y_{h}=Y_{(q-1)}\dots\ Y_{(q-m)}11\dots\ 11\) where the number of 1 in \(Y_{h}\) is \(q-m\). Due to the definitions, \(X_{h}\) is always less than or equal to \(X\), and \(Y_{h}\) is always greater than or equal to \(Y\). Let \(\Delta X=X-X_{h}\) and \(\Delta Y=Y-Y_{h}\). The deltas \(\Delta X\) and \(\Delta Y\) are the adjustments needed to obtain the true \(X\) and \(Y\) from \(X_{h}\) and \(Y_{h}\). This implies that \(\Delta X\) is always nonnegative and \(\Delta Y\) nonpositive. The fraction \(1/Y_{h}\) is always less than or equal to \(1/Y\), and, therefore, \(X_{h}/Y_{h}\) is always less than or equal to \(X/Y\). The Taylor series approximation equation for \(1/Y\) about \(Y=Y_{h}\) is:  
\[B=1/Y_{h}-\Delta Y/{Y_{h}}^{2}+(\Delta Y)^{2}/{Y_{h}}^{3}-(\Delta Y)^{3}/{Y_{ h}}^{4}+(\Delta Y)^{4}/{Y_{h}}^{5}+\dots+(-1)^{t-1}\ (\Delta Y)^{t-1}/{Y_{h}}^{t}+\dots. \tag{1}\]  
The Predict-Correct algorithm (Algorithm 1) is conceptually summarized as follows. ```
1: Set \(Q\) and \(j\) to \(0\) initially. 2: With index of the leading \(m\) bits of \(Y\), look \(b_{1}\) bits wide approximation of \(1/Y_{h}\) up in the table \(G_{1}\). 3: Similarly, look \(b_{2}\) bits wide approximation of \(1/{Y_{h}}^{2}\) up in the table \(G_{2}\),..., look \(b_{t}\) bits wide approximation of \(1/{Y_{h}}^{t}\) up in the table \(G_{t}\). 4: Table sizes are \(b_{i}=(m\times t-t)+\lceil\log_{2}t\rceil-(m\times I-m-i)\), \(i=1,2,\dots,t\), where \(t\) is the number of the used leading terms of (1). The relationship of parameter \(p\) and \(m\) is \(p=m\times t-t+2\). 5: Compute an approximation \(B\) to \(1/Y\) using the leading \(t\) terms of (1): \(B=1/Y_{h}-\Delta Y/{Y_{h}}^{2}+(\Delta Y)^{2}/{Y_{h}}^{3}-\dots+(-1)^{t-1}( \Delta Y)^{t-1}/{Y_{h}}^{t}\). Truncate \(B\) to the most significant \(m\times t-t+4\) bits, which reduces the sizing of multipliers. 6: Compute intermediate value \(P=X_{h}\times B\) and round \(P\) to \(m\times t-t-1\) bits to obtain \(P^{\prime}\). 7: List \(2^{m}\) kinds of \((m\times t-t+n-1)\)-bit quotients that dominate the \((m\times t-t-1)\)-bit intermediate value \(P^{\prime}\) with subsequent \(2^{m}\) kinds of \(n\)-bit predictive values ranging from \(00\dots\ 0\) to \(11\dots\ 1\). 8: Pick up the most approximative \((m\times t-t+n-1)\)-bit quotient \(Q_{a}\) from the \(2^{m}\) kinds of \((m\times t-t+n-1)\)-bit quotients by multiplication and comparison. 9: Calculate \(j^{\prime}=j+m\times t-t+n-1\). 10: Update \(j\) with \(j^{\prime}\). 11: New dividend is \(X^{\prime}=X-Q_{a}\times Y\). 12: New quotient is \(Q^{\prime}=Q+Q_{a}\times 1/2^{(q-j)}\). 13: Left-shift \(X^{\prime}\) by \(m\times t-t+n-1\) bits. 14: Update \(Q\) with \(Q^{\prime}\). 15: Update \(X\) with \(X^{\prime}\). 16: Repeat Step 4 through 10 until \(j\geq q\). 17: Final quotient is \(Q=Q_{(q-1)}\dots\ Q_{0}Q_{-1}\dots\ Q_{-e}=Q_{h}+Q_{l}\) where \(Q_{k}=Q_{(q-1)}\dots\ Q_{0}\), \(Q_{l}=Q_{-1}\dots\ Q_{-e}\) and \(e\) is the number of redundant bits of the last cycle in Step 1. ```  
**Algorithm 1** Predict-Correct Algorithm. In the Predict-Correct algorithm, Parameter \(t\) represents the number of the used leading terms of (1). For instance, if \(t=2\), the approximation to \(1/Y\) is \(B=1/Y_{h}-\Delta Y/{Y_{h}}^{2}\); if \(t=3\), the approximation to \(1/Y\) is \(B=1/Y_{h}-\Delta Y/{Y_{h}}^{2}+(\Delta Y)^{2}/{Y_{h}}^{3}\). Parameter \(m\) represents the digits number of the index of look-up table \(G_{1}\), \(G_{2}\),..., \(G_{l}\).