CODEWITHSUNDEEP
arbitrary-precision
0x777C
0x777C

Reputation: 1047

Why not use two's compliment for subtraction in arbitrary precision integer?

Java's BigInteger class uses the following code for subtraction of a small number from a larger number:

    private static int[] subtract(int[] big, int[] little) {
        int bigIndex = big.length;
        int result[] = new int[bigIndex];
        int littleIndex = little.length;
        long difference = 0;

        // Subtract common parts of both numbers
        while (littleIndex > 0) {
            difference = (big[--bigIndex] & LONG_MASK) -
                         (little[--littleIndex] & LONG_MASK) +
                         (difference >> 32);
            result[bigIndex] = (int)difference;
        }

        // Subtract remainder of longer number while borrow propagates
        boolean borrow = (difference >> 32 != 0);
        while (bigIndex > 0 && borrow)
            borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);

        // Copy remainder of longer number
        while (bigIndex > 0)
            result[--bigIndex] = big[bigIndex];

        return result;
    }

My question is wouldn't it be far more straightforward to simply perform ~x+1 on little without changing the value of the sign and adding it to big? Would this be particularly slow and if so why?

Upvotes: 0

Views: 146

Answers (1)

sannaj
sannaj

Reputation: 370

A 2's complement representation for n-bit integers is effectively the convention, that a unsigned integer value b equal to or above Math.pow(2,n-1) don't represent the value stored but instead the value b-(Math.pow(2,n-1)+1), which is negative. Since computers now perform wrapping arithmetic (meaning a+b actually calculates (a+b) % Math.pow(2, n), basic arithmetic produces the correct result in this convention.

If you now go to BigIntegers you want to avoid this. You don't want a maximum integer value Math.pow(2,n-1)-1 above which the numbers suddenly turn negative. And you don't want wrapping arithmetic, you want real integer arithmatic. Two's complement representations are bound to the specific range of integers available.

Big integers are stored in a string of "digits" where the digits above the most significant one are said to be zero. In theory you might find some creative way to store integers by defining that all bits above the topmost stored should be equal to the topmost bit stored and that all negative numbers -b are then stored as Infinity-b or something, but this would make things very complicated in many ways. So it's much easier to use a sign & magnitude storage, even if it might need a little bit more storage.

Upvotes: 1

Related Questions