Large Integer Computing - Introduction to Cryptography with Java Applets - page 46

//Initialize the answer to 0
Int result=new Int();
//If either operand is 0, return 0
if (this.equals(ZERO)||other.equals(ZERO)) return result;
//Now, multiply the first operand by each digit in the
//second operand, shifting left each answer by a power of ten
//as we pass through the digits, adding each time to result.
for (int i=0; i<other.digits.length; i++) {
result=result.add(this.multiply(other.digits[i])
.appendZeros(other.digits.length-1-i));

}
//If operands are same sign, result is positive
//otherwise, the result is negative; 0 is already taken care of
if (this.negative==other.negative) result.negative=false;
else result.negative=true;
//Return the result
return result.trimZeros();

}

Note that at the end of the multiply(Int) method we remove any leading zeros which may
come about. Another consideration is the sign of each operand: If they are equal, the result
is a nonnegative number; otherwise, the result is negative. Zero is treated as a special case.
At this point, you should be able to write the divide(Int), and remainder(Int) methods, and
will be asked to do so in the exercises. It would be prudent to write a divideAndRemain-
der() method, since both the quotient and remainder would probably be generated at the
same time. It could return an array of two Ints, with the quotient in slot 0, and the remain-
der in slot 1 of the array.
Division is the most costly (in terms of computer time) to run. For now, we only consider
problems where the dividend and divisor are both positive. One of the primary problems is
estimating the digits in the quotient. For example, consider the following division problem:

6772190 ÷ 37658.

Note that 3 (the leading digit of the divisor) goes into 6 (the leading digit of the dividend)
twice, but the real quotient of the previous division is 179. The estimate of the first digit of
the quotient is too high. A similar problem occurs in the following problem:

19276 273.

÷

Note that the leading digit of the divisor cannot go into the leading digit of the dividend
at all, and we must therefore attempt to take the divisor into the first two digits of the divi-
dend. One way to avoid spending too much time estimating is to allow the quotient to have
mixed positive and negative digits. Consider again

19276 ÷ 273.