1
$\begingroup$

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

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