Implementing BigInteger

JDK 8 Version:
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/math/BigInteger.java

    final int signum;
    /**
     * The magnitude of this BigInteger, in <i>big-endian</i> order: the
     * zeroth element of this array is the most-significant int of the
     * magnitude.  The magnitude must be "minimal" in that the most-significant
     * int ({@code mag[0]}) must be non-zero.  This is necessary to
     * ensure that there is exactly one representation for each BigInteger
     * value.  Note that this implies that the BigInteger zero has a
     * zero-length mag array.
     */
    final int[] mag;
    public BigInteger add(BigInteger val) {
        if (val.signum == 0)
            return this;
        if (signum == 0)
            return val;
        if (val.signum == signum)
            return new BigInteger(add(mag, val.mag), signum);

        int cmp = compareMagnitude(val);
        if (cmp == 0)
            return ZERO;
        int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
                           : subtract(val.mag, mag));
        resultMag = trustedStripLeadingZeroInts(resultMag);

        return new BigInteger(resultMag, cmp == signum ? 1 : -1);
    }

     * Compares the magnitude array of this BigInteger with the specified
     * BigInteger's. This is the version of compareTo ignoring sign.
    final int compareMagnitude(BigInteger val) {
        int[] m1 = mag;
        int len1 = m1.length;
        int[] m2 = val.mag;
        int len2 = m2.length;
        if (len1 < len2)
            return -1;
        if (len1 > len2)
            return 1;
        for (int i = 0; i < len1; i++) {
            int a = m1[i];
            int b = m2[i];
            if (a != b)
                return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
        }
        return 0;
    }

    public int compareTo(BigInteger val) {
        if (signum == val.signum) {
            switch (signum) {
            case 1:
                return compareMagnitude(val);
            case -1:
                return val.compareMagnitude(this);
            default:
                return 0;
            }
        }
        return signum > val.signum ? 1 : -1;
    }

http://interviewqa4java.blogspot.com/2012/02/how-to-add-2-big-integers.html
    private static String sumArray(int[] array1, int[] array2) {
        int carry=0;
        int sumArray[] = new int[array1.length + 1];
        
        //sum arrays
        for (int i = 0; i < array1.length; i++) {
            sumArray[i] = (array1[i] + array2[i] + carry) % 10 ; //sum digits + carry; then extract last digit
            carry = (array1[i] + array2[i] + carry) / 10; //Compute carry
        }
        sumArray[array1.length] = carry;
        return arrayToString(sumArray);
    }
http://www.codeproject.com/Articles/2728/C-BigInteger-Class
http://silentmatt.com/blog/2011/10/how-bigintegers-work/
Java Script Implementation:
Addition:

var c = { sign: 1, digits: [] }; // We'll store the result in c
var carry = 0;                   // Nothing to carry yet
for (var i = 0; i < a.digits.length; i++) {
    c.digits[i] = a.digits[i] + b.digits[i] + carry;
    if (c.digits[i] >= 10) { // Oops, too big.
        carry = 1;           // Set the carry to be added into the next digit
        c.digits[i] -= 10;   // Adjust to be one digit
    }
    else {
        carry = 0;           // It fit, so there's nothing to carry
    }
}
if (carry) { // Don't forget to add the final carry if it's needed
    c.digits[i] = carry;
}

Instead of the if (c.digits[i] < 10) {... statement, we can use the remainder and (integer) division operators:

c.digits[i] = (a.digits[i] + b.digits[i] + carry) % 10;
carry = Math.floor((a.digits[i] + b.digits[i] + carry) / 10);

Subtraction

Subtraction is basically the exact opposite of addition. You loop through each digit andsubtract. If the result is negative, borrow a 10 from the next digit. Again, for simplicity we’ll assume the numbers are positive, padded to be the same length, and that a > b (if it’s not, we can force it by playing with the signs).

var c = { sign: 1, digits: [] }; // We'll store the result in c
var borrow = 0;                  // We didn't borrow anything yet
for (var i = 0; i < a.digits.length; i++) {
    c.digits[i] = a.digits[i] - b.digits[i] - borrow;
    if (c.digits[i] < 10) { // Oops, we can't have a negative digit
        borrow = 1;         // We'll borrow 10 from the next pair of digits
        c.digits[i] += 10;  // Add the borrowed 10
    }
    else {
        borrow = 0;         // We don't need to borrow anything
    }
}
// We made sure a < b to make sure we never have to borrow after the last digit, so we're done

With the combination of addition and subtraction, we can handle adding any combination of positive and negative numbers (e.g. to subtract a negative from a positive, pretend both are positive and add them).

http://silentmatt.com/blog/2011/10/how-bigintegers-work-part-2-multiplication/
Simple Multiplication

function multiply(a, b) {
    var product = ZERO;
    while (notZero(a)) {
        product = add(product, b);
        a = subtract(a, ONE);
    }
    return product;
}

function multiply(a, b) {
    // To keep track of all the partial products
    var partialProducts = [];

    // For each digit of b
    for (var i = 0; i < b.digits.length; i++) {
        var carry = 0;
        var digit;
        var partial = {sign: 1, digits: []}; // Initialize a new partial product

        // For each digit of a
        for (var 0; j < a.digits.length; j++) {
            digit = (b.digits[i] * a.digits[j]) + carry; // Multiply the digits, adding in any carry
            carry = Math.floor(digit / 10);              // Integer divide by 10 to get the first digit
            partial.digits[j] = digit % 10;              // Mod 10 gets the second digit
        }
        // Don't forget the final carry (if necessary)!
        if (carry > 0) {
            partial.digits[j] = carry;
        }

        // Shift the digits to the left to multiply by the next power of 10
        for (var shift = 0; shift < i; shift++) {
            // Unfortunately, JS's naming is backwards from ours.
            // "array.unshift(0)" pushes a zero into the front of the array, which is what we want
            partial.digits.unshift(0);
        }

        // Append this partial product to the list
        partialProducts.push(partial);
    }

    // Now add up all the partial products
    var product = ZERO;
    for (var i = 0; i < partialProducts.length; i++) {
        product = add(product, partialProducts[i]);
    }

    return product;
}

For each digit of b, loop through each digit of a, multiplying the digits and storing them in the partial product, then add up the partial products at the end.

The Real AlgorithmThe problem is all those partial products. Instead of building up a list (taking up a potentially large amount of memory) then adding them up at the end, we can just add in each product as we go. We can also avoid pushing all the zeros in by adjusting how we index into the arrays.

unction multiply(a, b) {
    var partial = { sign: a.sign * b.sign, digits: [] }; // digits should be filled with zeros

    // For each digit of b
    for (var i = 0; i < b.digits.length; i++) {
        var carry = 0;
        var digit;

        // For each digit of a
        for (var j = i; j < a.digits.length + i; j++) {
            // Multiply the digits, and add them to the current partial product, along with any carry
            digit = partial.digits[j] + (b.digits[i] * a.digits[j - i]) + carry;
            carry = Math.floor(digit / 10); // New carry
            partial.digits[j] = digit % 10; // Put the result back into the partial product
        }
        // Don't forget the final carry (if necessary)!
        if (carry) {
            digit = partial.digits[j] + carry;
            carry = Math.floor(digit / 10);
            partial.digits[j] = digit % 10;
        }
    }

    // That's it!
    return partial;
}

They are mostly based on Karatsuba multiplication, which is a recursive “divide and conquer” algorithm. The added complexity and overhead of recursive function calls makes it slower for “reasonably sized” numbers, so it’s best to use simple long multiplication until you get to some threshold then switch to Karatsuba multiplication.