I'm studying the chapter Division by Digit Recurrence in Digital Arithmetic of Ercegovac. I like this book is overall well written. Although sometimes I struggle understanding some aspect like the one I'm about to expose.First of all let me give some introduction to the method, almost everything is taken from the book I mentioned, so please refer there mainly if you're interested. Let $r > 2$ be the considered radix.Let's consider two fractional number $x,y$ such that$$\begin{array}{l}x = 0.x_{-1} \ldots x_{-2k} \\y = 0.y_{-1} \ldots y_{-k} \\\frac{1}{2} \leq y < 1 \\x < y,\end{array}$$the goal is to find two numbers $q$ and $s$ such that$$\begin{array}{l}q = 0.q_{-1}\ldots q_{-k} \\s = 0.s_{-1} \ldots s_{-k} \\r^{-k} s < y \\x = qy + r^{-k}s\end{array} .$$To derive the recurrence let's define$$q[j] = \left\{\begin{array}{ll}0 & j = 0 \\0.q_{-1} \ldots q_{-j} & 1 \leq j \leq k\end{array}\right.,$$and$$s[j] = r^k (x-yq[j]) \;,\; 0 \leq j \leq k,$$observe that $s[0] = r^{k}x$.Observing that $q[j+1] - q[j] = q_{-j-1}r^{-j-1}$ we can write the following recursion for $s[j]$:$$\left\{\begin{array}{ll}s[j+1] = s[j] - q_{-j-1}r^{k-j-1}y & 0 \leq j \leq k - 1 \\s[0] = r^kx\end{array}\right.$$Multiplying both sides of the recursion by $r^{j+1-k}$, and defining $w[j] = r^{j-k}s[j]$ we end up with the following$$\left\{\begin{array}{ll}w[j+1] = rw[j] - q_{-j-1}y & 0 \leq j \leq k - 1 \\w[0] = x\end{array}\right.$$which is the actual recursion implemented in hardware/software when the division is performed. Now let's move on... let $a$ be an integer such that$$\left\lceil \frac{r}{2} \right\rceil \leq a \leq r - 1$$we define the redundancy factor $\rho$ as$$\rho = \frac{a}{r-1}$$easy to show that$$\frac{1}{2} < \rho \leq 1.$$We finally define the set $D_a = \left\{-a,-a+1,\ldots,-1,0,1,\ldots a-1,a \right\}$.It can be proven that if$$| w[j] | < \rho y$$then the division algorithm will converge with $1$ ulp error. Please keep in mind such bound because it is where my problem arise, also observe that $\rho$ is actually a real number (specifically is rational, but I don't think it matters for this discussion, we can therefore assume it is real in general).What I'm trying to work out is how many digits do I actually need to represent these shifted partial reminders $w[j]$, I'm struggling because of that $\rho$ factor in the bound.Is there any hint you could give me in order to find out the bitwidth?Thank youMore details: Extrapolated from the bookBy looking at first point specifically, if $\rho = 1$ then $w[0]$ has to be initialized to $x/2$ therefore to represent $w[0]$ I would need $2k+1$ bits, otherwise $w[0] = x/4$, therefore $2k+2$ bits. Given at each I have to compute $rw[j]$ this means I need $n_1 = \left\lceil \log_2(r) \right\rceil + 2k + 1$ when $rho=1$ otherwise $n_2 = \left\lceil \log_2(r) \right\rceil + 2k + 2$, is this correct (It's not a formal proof... just a guess).
Bitwidth requirements for the division algorithm using redundant radix
algorithms;algorithm analysis;computer architecture;arithmetic