# Error analysis of a non restoring division algorithm. Studying the iteration.

I'm not sure my derivation is correct, and I also need to find out the error of the iteration/sequence I'm about to derive, but I can't figure out the error once the iteration is finished.

Let $x,y,q,r$ integers (expressed in binary) such that

$$\begin{array}{l} x = x_{2k-1} \ldots x_0 = \sum_{j=0}^{2k-1} x_j 2^j\\ y = y_{k-1} \ldots y_0 = \sum_{j=0}^{k-1} y_j 2^j\\ q = q_{k-1} \ldots q_0 = \sum_{j=0}^{k-1} q_j 2^j\\ r = r_{k-1} \ldots r_0 = \sum_{j=0}^{k-1} r_j 2^j \end{array}$$

The idea would be write down an algorithm such that $$x = qy + r$$

To derive the iteration we define for $0 \leq j \leq k$

$$q^{(j)} = q_{k - 1}2^{k - 1} \ldots q_{k-j}2^{k-j} = \left\lfloor \frac{q}{2^{k-j}} \right\rfloor$$

We define $r^{(j)}$ as the solution of $$q^{(j)}y + r^{(j)} = x$$ It is in particular clear that $q^{(0)} = 0 \Rightarrow r^{(0)} = x$ For $0 \leq j \leq k-1$ taking the finite difference of the previous equation provides \begin{multline} \Delta_j (q^{(j)}y + r^{(j)}) = \Delta_j x \Rightarrow (\Delta_j q^{(j)})y + \Delta_j r^{(j)} = \Delta_jx \Rightarrow \\ (q^{(j+1)} - q^{(j)})y + r^{(j+1)} - r^{(j)} = 0 \Rightarrow q_{k-j-1} 2^{k-j-1}y + r^{(j+1)} - r^{(j)} = 0 \Rightarrow \\ r^{(j+1)} = r^{(j)} - q_{k-j-1}2^{k-j-1}y \end{multline} therefore I end up with the following sequences of partial reminder $$r^{(j+1)} = \left\{ \begin{array}{l} r^{(j)} - q_{k-j-1}2^{k-j-1}y & 0 \leq j \leq k - 1\\ x & j = - 1 \end{array} \right.$$

Choosing $q_{k-j-1} = \text{signum}(r^{(j)} - 2^{k-1-j}y)$ allow the sequence to converge. The question is... how do analyse the sequence in order to derive a bound on $r^(j)$?

I have easily derived

$$|r^{(j+1)} - r^{(j)}| = 2^{k-1-j}y$$

But this doesn't seem to lead at anything...