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 \begin{equation} 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. \end{equation}

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


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.