Radix Subtraction

Question

I have a really basic question about the Radix Subtraction.

In the lecture slides on page 39 in Integer Arithmetic, i dont understand the c[3]=1. In the step before you calculate, sm=1-3=-2 and then c[i+1]=-(-2/4)=0.5, according to the algorithm.

Then in i=4 we calculate sm=1-(1+1)=-1 and for s[i]= sm%B=-1%4 and get 3?! I would have said 1 is left after modulo.

Thanks in advance!

Answer 1

When i=2, we compute the following in the mentioned example:

    sm = +x[2] - (y[2] + c[2]) = +1 - (3 + 0) = +1 - 3 = -2

Now, we have do compute division with remainder for computing q := sm / B and r := sm % B. These numbers are defined as those uniquely defined numbers that satisfy the following

    sm = q * B + r & 0 <= r < B

Note that the division is an integer division, so the result is not 0.5

For sm = -2 and B = 4, we get -2 = -1 * 4 + 2, and hence, we have q=-1 and r=2, which then leads to

    c[3] = -(sm / B) = 1
    s[2] = sm % B = 2

For i=4, we compute

    sm = +x[4] - (y[4] + c[4]) = +1 - (1 + 1) = +1 - 2 = -1

Again, we have to compute the integer division, and get q = -1 and r = 3 since we have sm = -1 = -1 * 4 + 3 & 0 <= 3 < 4. Hence, it continues with 

    c[5] = -(sm / B) = 1
    s[4] = sm % B = 3

Hint: You should have a look at the next slide, i.e., slide 40, where the problem with integer division is explained. Unfortunately, neither programming languages nor microprocessors did agree on a unique solution.