/** [ Math 220 main page ] This is a data type for multi-precision integers of arbitrary sign. Its important data are (1) an array of digits a and (2) a sign s. Also, for convenience the size n of the sub-array of significant digits is maintained.
Here is a very simple sample program
which multiplies its two arguments.
*/
public class MPInt {
public int a[];
public int n;
public int sign;
// --- constructors ----------------------------------------
/** Constructs an integer from a string of decimal digits. */
public MPInt(String s) throws NumberFormatException {
s.trim();
int ell;
if (s.length() == 0) {
throw new NumberFormatException();
}
int i=0;
int N = s.length();
if (s.charAt(i) == '-') {
sign = -1;
i++;
ell = N-1;
} else {
ell = N;
sign = 1;
}
a = new int[ell];
while (i < N) {
char c = s.charAt(i++);
a[ell-1] = decimalValue(c);
ell--;
}
n = Decimal.trueLength(a);
if (n == 0) sign = 1;
}
/** Constructs a multi-precision integer from
a standard Java int. */
public MPInt(int n) {
if (n < 0) {
n = -n;
sign = -1;
}
else sign = 1;
a = Decimal.toArray(n);
this.n = Decimal.trueLength(a);
}
/** Constructs a non-negative multi-precision integer from
an array of digits. */
public MPInt(int[] a) {
this.a = a;
n = Decimal.trueLength(a);
sign = 1;
}
/** Allows a sign as well. */
public MPInt(int[] a, int s) {
this.a = a;
n = Decimal.trueLength(a);
sign = s;
}
// --- operations ----------------------------------------
/** This is one of the usual arithmetic operations. They all
can be combined as
the ordinary symbolic operations. They associate to the left.
Thus a.plus(b).times(c) is (a+b)*c, while a.plus(b.times(c)) is (a+(b*c)). */
public MPInt plus(MPInt y) {
if (sign == y.sign) {
int c[] = Decimal.sum(a, n, y.a, y.n);
return(new MPInt(c, sign));
} else if (sign < 0) {
// y >= 0: return y - this
if (Decimal.greaterThan(y.a, a)) {
int c[] = Decimal.sub(y.a, y.n, a, n);
return(new MPInt(c, 1));
} else {
int c[] = Decimal.sub(a, n, y.a, y.n);
return(new MPInt(c, -1));
}
} else {
// sign > 0, y < 0; return this - y
if (Decimal.greaterThan(y.a, a)) {
int c[] = Decimal.sub(y.a, y.n, a, n);
return(new MPInt(c, -1));
} else {
int c[] = Decimal.sub(a, n, y.a, y.n);
return(new MPInt(c, 1));
}
}
}
public MPInt minus(MPInt y) {
if (sign != y.sign) {
// if sign < 0, neg - pos = neg, else pos - neg = pos
int c[] = Decimal.sum(a, n, y.a, y.n);
return(new MPInt(c, sign));
} else if (sign == y.sign) {
// sign > 0: pos - pos
if (Decimal.greaterThan(a, y.a)) {
int c[] = Decimal.sub(a, n, y.a, y.n);
return(new MPInt(c, sign));
} else {
int c[] = Decimal.sub(y.a, y.n, a, n);
return(new MPInt(c, -sign));
}
} else {
// sign > 0, y < 0; return this - y
if (Decimal.greaterThan(a, y.a)) {
int c[] = Decimal.sub(a, n, y.a, y.n);
return(new MPInt(c, -sign));
} else {
int c[] = Decimal.sub(y.a, y.n, a, n);
return(new MPInt(c, sign));
}
}
}
public MPInt times(MPInt y) {
int[] c = Decimal.mul(a, n, y.a, y.n);
return(new MPInt(c, sign*y.sign));
}
public MPInt dividedBy(MPInt y) throws ArithmeticException {
if (y.n == 0) {
throw new ArithmeticException("Division by zero!");
}
int[] A = Decimal.copy(a);
int[] c = Decimal.divideInto(y.a, y.n, A, n);
return(new MPInt(c, sign*y.sign));
}
// returns smallest non-negative multiple of y
public MPInt modulo(MPInt y) throws ArithmeticException {
if (y.n == 0) {
throw new ArithmeticException("Division by zero!");
}
int[] A = Decimal.copy(a);
int[] c = Decimal.divideInto(y.a, y.n, A, n);
if (sign < 0) {
// true answer = -A, should be -A + y
A = Decimal.sub(y.a, A);
}
return(new MPInt(A, 1));
}
/** This function is called implicitly when you print a variable of type MPInt. For
example if a is an MPInt then System.out.println(a)
will print out this string. */
public String toString() {
StringBuffer s = new StringBuffer();
// s.append("[" + n + "]");
if (sign == -1) s.append('-');
s.append(Decimal.toString(a));
return(s.toString());
}
public static MPInt factorial(int n) throws ArithmeticException {
if (n < 0) throw new ArithmeticException();
int[] f = {1};
for (int i=0;i