1
$\begingroup$

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 you

More details:

Extrapolated from the book enter image description here

By 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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.