CODEWITHSUNDEEP
algorithmmathbinaryinteger-divisiondivider
ollo
ollo

Reputation: 946

Non-restoring signed integer division post-corrections

I cant figure out the post-corrections to non-restoring integer division. For some reason I keep getting cases where I correct where no corrections are needed or don't correct when needed

heres pseudocode of the algorithm. Dividend is 16bits and others 8 bits. By Dividend_Sign, Remainder_Sign I mean their MSB is 1, so they are negative by 2's complement. 

LoopCounter = 8;
do {
    Shift Dividend Left with 0 in LSB;

    if (Dividend_Sign XOR Divisor_Sign) {
        Shift 0 into Quotient;
        DividendHighByte = DividendHighByte + Divisor;
    } else {
        shift 1 into Quotient;
        DividendHighByte = DividendHighByte - Divisor;  // subtraction by 2's complement
    }
} while (loopCounter != 0);

Remainder = DividendHighByte;

// here i do the Quotient conversion
invert MSB;  // shifted out anyway. Probably should be used for overflow check, not important atm.
shift 1 into Quotient;

now im at a point where i basically have the right answer, it just needs to be post-corrected in one way or another... OR not post-corrected at all. Im not sure what all the correction cases are. right now i have something that isnt working half the time, but here it is anyway:

if (Dividend_Sign XOR Remainder_sign) {     // diff signs so correct
    if (Remainder_Sign XOR Divisor_Sign) {  // diff signs just add
        Remainder = Remainder + Divisor;
        Quotient = Quotient - 1;
    } else {
        Remainder = Remainder - Divisor;
        Quotient = Quotient + 1;
    }
}

http://en.wikipedia.org/wiki/Division_%28digital%29

http://www.acsel-lab.com/arithmetic/papers/ARITH17/ARITH17_Takagi.pdf

Upvotes: 1

Views: 3289

Answers (1)

ollo
ollo

Reputation: 946

The algorithm works, the problem is 2s complement has a negative zero. If the final remainder is 0 no corrections are ever necessary. But the algorithm must detect a 0 remainder within cycles and if one is encountered corrections are always necessary.

Just added a 0 remainder flag and did this:

if (!Remainder.isEmpty() && (zeroFlag || (Dividend.Sign() XOR Remainder.Sign())))
      ...do corrections

Upvotes: 1

Related Questions