C++ division by bit shifting and substractiing won't work correctly

Question

I'd like to implement a 256bit integer type for working with large numbers. That being said, I cannot use the default arithmetic operators so I have to reimplement them with bitwise operations.

So far I have most of them working and tested individually, but I can't get past division.

I'm doing this partly for learning purposes, so while bignum libraries are welcome, they aren't something I'm looking for at the moment.

I modified a code from an another answer, here: https://stackoverflow.com/a/19780781/1619594

Int_256 operator/(Int_256 dividend, const Int_256 &divisor) {
    Int_256 quotient = { 0, 0, 0, 0 };
    int nPos = -1;
    Int_256 tempDivisor = divisor;

    while (tempDivisor < dividend) {
        tempDivisor = tempDivisor << 1;
        nPos ++;
    }

    tempDivisor = tempDivisor >> 1;

    while (nPos > -1) {
        if (dividend >= tempDivisor) {
            quotient = quotient + (1 << nPos);
            dividend = dividend - tempDivisor;
        }

        tempDivisor = tempDivisor >> 1;
        nPos -= 1;
    }

    Int_256 remaining = dividend;

    return quotient;
}

Everything's supposed to be unsigned, in fact the "Int_256" is just 4 64bit unsigned integers together.

The problem is that while it sometimes will work fine, but at other times, it won't.

E.g.: 10/5 == 1, with a remainder of 5, and 8/2 == 3, with a remainder of 2, etc.

However 35/5 and 10/2 will give correct results.

Does anyone know what the issue could be that I missed?

Update: Here's the whole code as it was requested: http://fecka.ddns.net/gogs/fecka/int256test

It is incomplete and messy, there are probably a lot of things wrong with it, a minute ago I found out, that even multiplying won't work properly, so any help would be much appreciated.

*I'm doing this partly for learning purposes* -- What about using the debugger? You are getting wrong values, you know the data that reproduces the wrong values, you wrote the program. So where in that function does it diverge from your expectations? — PaulMcKenzie, Jan 08 '18 at 00:37
It's actually a python+cuda "project", that's why I'm using a POD struct, and that's why I couldn't debug it properly. I didn't want to post the whole code, because it's long, incomplete, and pretty much spaghetti. However, if anyone would like to suffer (would be much appreciated though), here's a git repo which has the important parts stripped from the cuda stuff: http://fecka.ddns.net/gogs/fecka/int256test — tamasfe, Jan 08 '18 at 01:44
Two problems that I can see offhand. The first is the loop condition, as per 1201's answer. The second is that the first loop produces a value of `npos` between `0` and `255` - which will cause the later statement `quotient = quotient + (1 << nPos)` to have undefined behaviour, since `1` is of type `int` and bitshifting any `int` 255 places gives undefined behaviour (it will not produce a result of type `Int_256`). — Peter, Jan 08 '18 at 07:35

score 2 · Accepted Answer · answered Jan 08 '18 at 01:47

The problem is with an edge case. Your initial while loop should be

while (tempDivisor <= dividend)

checking for equality as well. Without that (in the 10/5 case), tempDivisor comes out of that loop as 10, gets immediately cut in half to 5, which results in the wrong answer.

C++ division by bit shifting and substractiing won't work correctly

1 Answers1