/*
* an implementation of simple math operations for arbitrary-precision numbers
* @author Biagioni, Edoardo
* @assignment lecture 6
* @date January 30, 2008
*/
import java.lang.ArithmeticException;
public class ArbitraryPrecision implements ArbitraryPrecisionInterface {
/* the number is represented as an array of digits, each digit in 0..9
* so for example the number 45892 is represented by an array of
* five integers, with values 4, 5, 8, 9, 2, and numDigits = 5
*/
int[] value; // is null for zero
int numDigits; // how many digits this number has
// invariant: if value != null, numDigits == value.length,
// otherwise if value == null, numDigits == 0
/* a private method make sure the invariants hold for this object */
private static void checkInvariants(ArbitraryPrecision test) {
if (test.numDigits == 0) {
assert (test.value == null) :
"value should be null if numDigits is 0";
} else {
assert (test.numDigits > 0) : "numDigits should not be negative";
assert (test.value != null) :
"value should not be null if numDigits > 0";
assert (test.value.length == test.numDigits) :
"value.length == numDigits";
}
if (test.value == null) {
assert (test.numDigits == 0) :
"numDigits should be 0 if value is null";
} else {
assert (test.value.length == test.numDigits) :
"value.length == numDigits";
assert (test.value.length > 0) : "array length should be > 0";
assert (test.value[0] > 0) : "first digit should be > 0";
}
}
/* check this number for invariants */
private void checkInvariants() {
checkInvariants(this);
}
/* the default constructor always returns zero. */
public ArbitraryPrecision() {
value = null; // zero has a null array
numDigits = 0;
checkInvariants(); // make sure the invariants hold after the call
}
/* constructor to build a number from a string.
* @param input -- the string holding the number to parse
*/
public ArbitraryPrecision(String input) {
value = fromString(input);
numDigits = 0;
if (value != null) {
numDigits = value.length;
}
checkInvariants(); // make sure the invariants hold after the call
}
/* recursive methods for the preceding constructor. */
/* fill an array with digits from a string.
* @param input the string to parse, should begin with a number,
* optionally preceded by the + sign
* @return the filled array of digits, or null if input is zero
*/
private int[] fromString (String input) {
if (input == null) { // null string
return null;
}
int position = 0;
// skip over an initial + sign
if ((input.length() > 0) && (input.charAt(0) == '+')) {
position++;
}
// skip over any initial zeros
while ((input.length() > position) &&
(input.charAt(position) == '0')) {
position++;
}
// see if there is anything left
if (input.length() <= position) {
return null; // no digits in the string
}
int numDigits = computeNumDigits(input, position);
if (numDigits > 0) {
value = new int[numDigits];
assignDigits(input, position, value, 0);
} else { // assign zero
value = null;
}
return value;
}
/* compute the number of digits at the beginning of the string
* @param input the string to parse
* @param startPos the first character to look at
* @return the number of valid digits beginning at startPos
*/
private int computeNumDigits(String input, int startPos) {
if (startPos >= input.length()) { // end of string
return 0;
}
char next = input.charAt(startPos);
if (Character.getType(next) == Character.DECIMAL_DIGIT_NUMBER) {
return 1 + computeNumDigits(input, startPos + 1);
} else {
return 0; // no valid digits
}
}
/* assign digits from the string to the array
* @param input the string to parse
* @param startPos the first character to look at
* @param result the array to fill with digits
* @param resultPos the first position to fill in the result array
*/
private void assignDigits(String input, int startPos,
int[] result, int resultPos) {
while (resultPos < result.length) {
assert (startPos < input.length()):"parsing beyond end of string";
result[resultPos] = Character.digit(input.charAt(startPos), 10);
resultPos++;
startPos++;
}
}
/* constructor to build a number from an ArbitraryPositionInterface object.
* @param input -- the number to use
*
* convert the number to a string, then parse the string -- almost
* the same as the previous constructor
*/
public ArbitraryPrecision(ArbitraryPrecisionInterface input) {
value = fromString(input.toString());
numDigits = 0;
if (value != null) {
numDigits = value.length;
}
checkInvariants(); // make sure the invariants hold after the call
}
/* make the number printable */
public String toString() {
checkInvariants(); // verify that the invariants hold
if (numDigits == 0) {
return new String("0");
}
String result = "";
for (int i = 0; i < numDigits; i++) {
// value[i] is implicitly converted to a string
result = result + value[i];
}
return result;
}
/* are two numbers the same? */
public boolean equals(ArbitraryPrecisionInterface n) {
checkInvariants(); // verify that the invariants hold
// first convert to our representation
ArbitraryPrecision other = new ArbitraryPrecision(n);
// now compare
if ((other.numDigits == 0) && (numDigits == 0)) {
return true;
}
if (other.numDigits != numDigits) {
return false;
}
/* are all the digits the same? */
for (int i = 0; i < numDigits; i++) {
if (value[i] != other.value[i]) {
return false;
}
}
/* all matches */
return true;
}
/* true if this number < n */
public boolean isLessThan(ArbitraryPrecisionInterface n) {
checkInvariants(); // verify that the invariants hold
// first convert to our representation
ArbitraryPrecision other = new ArbitraryPrecision(n);
// now compare
if ((numDigits == 0) && (other.numDigits == 0)) {
return false;
}
if (numDigits < other.numDigits) {
return true;
}
if (numDigits > other.numDigits) {
return false;
} // num digits is the same -- are all the digits the same?
for (int i = 0; i < numDigits; i++) {
if (value[i] != other.value[i]) {
return (value[i] < other.value[i]);
}
}
/* the numbers are the same, so this number is not less */
return false;
}
// other basic tests
public boolean isZero() {
checkInvariants(); // verify that the invariants hold
return (numDigits == 0);
}
public boolean isOdd() {
checkInvariants(); // verify that the invariants hold
if (numDigits > 0) { // is the last digit odd?
return ((value[numDigits - 1] % 2) != 0);
} else { // zero is not odd
return false;
}
}
/* methods to perform simple arithmetic operations: +1, -1, *2, /2 */
/* return a new number that is one more than this number */
public ArbitraryPrecision oneMore() {
checkInvariants(); // verify that the invariants hold
if (isZero()) { // simple case
return new ArbitraryPrecision("1");
} // not zero, add one to the number
ArbitraryPrecision result = new ArbitraryPrecision();
result.value = addOne(value, numDigits); // use auxiliary method
result.numDigits = result.value.length;
checkInvariants(result); //make sure the invariants hold after the call
return result;
}
/* auxiliary method that adds one to an array of digits */
private int[] addOne(int[] value, int numDigits) {
boolean carry = true; // add one initially, then as needed for carry
int[] result = new int[numDigits];
for (int i = numDigits - 1; i >= 0; i--) { // start with least signif.
result[i] = value[i];
if (carry) {
if (result[i] == 9) { // carry to the next digit
result[i] = 0;
carry = true;
} else {
result[i] = result[i] + 1;
carry = false;
}
}
}
if (carry) { // add another digit at the front of the number
int[] newResult = new int[numDigits + 1];
System.arraycopy(result, 0, newResult, 1, numDigits);
newResult[0] = 1; // the new digit is always a one
result = newResult;
}
return result;
}
/* return a new number that is one less than this number */
public ArbitraryPrecision oneLess() throws ArithmeticException {
checkInvariants(); // verify that the invariants hold
if (isZero()) {
throw new ArithmeticException("one from zero would be negative");
}
ArbitraryPrecision result = new ArbitraryPrecision(); // zero
if (equals(new ArbitraryPrecision("1"))) { // other special case
return result;
}
result.value = subOne(value, numDigits); // use auxiliary method
// result should be > 0
result.numDigits = result.value.length;
checkInvariants(result); //make sure the invariants hold after the call
return result;
}
/* auxiliary method that adds one from an array of digits > 1 */
private int[] subOne(int[] value, int numDigits) {
boolean borrow = true; // subtract one from the least significant
// digit, and from other digits as needed
int[] result = new int[numDigits];
// start with the least significant digit, at position numDigits - 1
for (int i = numDigits - 1; i >= 0; i--) {
result[i] = value[i];
if (borrow) { // subtract one from this digit
borrow = false;
if (result[i] == 0) { // and from the next digit as well
result[i] = 9;
borrow = true;
} else {
result[i] = result[i] - 1;
}
}
}
if (result[0] == 0) { // remove the most significant digit
// since the input value > 1, we have that this numDigits > 1
assert (numDigits > 1):"input to subOne must be greater than one";
int[] newResult = new int[numDigits - 1];
System.arraycopy(result, 1, newResult, 0, numDigits - 1);
result = newResult;
}
return result;
}
public ArbitraryPrecision twice() {
checkInvariants(); // verify that the invariants hold
ArbitraryPrecision result = new ArbitraryPrecision(); // zero
if (numDigits == 0) {
return result;
}
int resultDigits = numDigits;
int resultOffset = 0; // will be 1 if result takes one more digit
assert (value != null):"value should not be null here";
assert (numDigits > 0):"numDigits should not be negative or zero here";
if (value[0] >= 5) { // if the first digit >= 5, need new digit
resultDigits++;
resultOffset = 1;
}
result.numDigits = resultDigits;
result.value = new int[resultDigits];
boolean carry = false; // no carry in to the least significant digit
/* begin with least significant digits */
for (int i = resultDigits - 1; i >= resultOffset; i--) {
result.value[i] = 2 * value[i - resultOffset];
if (carry) {
result.value[i]++;
}
carry = false;
if (result.value[i] > 9) {
result.value[i] -= 10;
carry = true;
}
}
assert (carry == (resultOffset == 1)) :
"carry should be set exactly if resultOffset is 1";
if (carry) {
result.value[0]++;
}
checkInvariants(result); //make sure the invariants hold after the call
return result;
}
public ArbitraryPrecision half() {
checkInvariants(); // verify that the invariants hold
ArbitraryPrecision result = new ArbitraryPrecision(); // zero
if ((numDigits == 0) || (equals(new ArbitraryPrecision("1")))) {
return result; // zero.half() = zero, and one.half() = zero
}
int resultDigits = numDigits;
int resultOffset = 0; // is 1 if result is one less digit
boolean carry = false; // do not add 5 to the most significant digit
// the first digit should never be zero, but here we use that,
// so we actually check it. The other assertions are from the
// check above that the number be larger than one
assert (value[0] != 0):"normalized number should not have MS digit 0";
assert (value != null):"value should not be null here";
assert (numDigits > 0):"numDigits should not be negative or zero here";
if (value[0] == 1) { // will have one less digit in the result
resultDigits--;
resultOffset = 1;
carry = true; // so add five to the most significant digit
}
assert (resultDigits > 0):"resultDigits should be > 0";
result.numDigits = resultDigits;
result.value = new int[resultDigits];
/* divide by two starting with most significant digit */
for (int i = 0; i < resultDigits; i++) {
result.value[i] = value[i + resultOffset] / 2;
if (carry) { // carry from the previous digit
result.value[i] += 5;
}
// add 5 to the next digit down?
carry = ((value[i + resultOffset] % 2) == 1);
}
checkInvariants(result); //make sure the invariants hold after the call
return result;
}
/* methods to perform the basic arithmetic operations. */
/* add this number and a parameter and return the sum
* @param a number to be added to this number
* @return a third number, the sum of the parameter and this number
*
* very slow implementation, adds one to the parameter a number
* of times equal to this number.
*/
public ArbitraryPrecision add(ArbitraryPrecisionInterface n) {
checkInvariants(); // verify that the invariants hold
ArbitraryPrecision result = new ArbitraryPrecision(n);
// result is now the same as n
ArbitraryPrecision counter = new ArbitraryPrecision(); // zero
while (! equals(counter)) {
result = result.oneMore();
counter = counter.oneMore();
}
return result;
}
/* @param a number to be subtracted from this number
* @return the difference between this number and the parameter
* @throws ArithmeticException if the result is negative
*
* very slow implementation, subtracts one from this number
* a number of times equal to the parameter.
*/
public ArbitraryPrecision subtract(ArbitraryPrecisionInterface n)
throws ArithmeticException {
checkInvariants(); // verify that the invariants hold
if (this.isLessThan(n)) {
throw new ArithmeticException("negative result for subtract");
}
ArbitraryPrecision result = new ArbitraryPrecision(this);
ArbitraryPrecision parameter = new ArbitraryPrecision(n);
ArbitraryPrecision counter = new ArbitraryPrecision(); // zero
while (! parameter.equals(counter)) { // while counter != n
result = result.oneLess();
counter = counter.oneMore();
}
return result;
}
/* @param a number to be multiplied to this number
* @return the product of this number and the parameter
*
* very slow implementation, adds the parameter to the result
* a number of times equal to this number.
*/
public ArbitraryPrecision multiply(ArbitraryPrecisionInterface n) {
checkInvariants(); // verify that the invariants hold
ArbitraryPrecision parameter = new ArbitraryPrecision(n);
ArbitraryPrecision result = new ArbitraryPrecision(); // zero
if (isZero() || parameter.isZero()) {
return result; // return zero
}
ArbitraryPrecision counter = new ArbitraryPrecision(); // zero
while (! equals(counter)) {
result = result.add(parameter);
counter = counter.oneMore();
}
return result;
}
/* @param the divisor
* @return a third number, this number divided by the divisor
* @throws ArithmeticException if the divisor is zero
*
* very slow implementation, subtracts the divisor from the result
* a number of times until the result is less than this number
*/
public ArbitraryPrecision divide(ArbitraryPrecisionInterface d)
throws ArithmeticException {
checkInvariants(); // verify that the invariants hold
ArbitraryPrecision divisor = new ArbitraryPrecision(d);
if (divisor.isZero()) {
throw new ArithmeticException("division by zero");
}
ArbitraryPrecision dividend = new ArbitraryPrecision(this);
ArbitraryPrecision counter = new ArbitraryPrecision(); // zero
while (! dividend.isLessThan(divisor)) {
dividend = dividend.subtract(divisor);
counter = counter.oneMore();
}
return counter;
}
/* @param the divisor
* @return a third number, this remainder when dividing by the divisor
* @throws ArithmeticException if the divisor is zero
*/
public ArbitraryPrecision modulo(ArbitraryPrecisionInterface divisor)
throws ArithmeticException {
checkInvariants(); // verify that the invariants hold
ArbitraryPrecision quotient = divide(divisor);
ArbitraryPrecision remainder = subtract(quotient.multiply(divisor));
return remainder;
}
/* corresponding mutator methods for add, subtract, muliply, divide */
public void addTo(ArbitraryPrecisionInterface n) {
checkInvariants(); // verify that the invariants hold
ArbitraryPrecision result = add(n);
value = result.value;
numDigits = result.numDigits;
}
public void subtractFromTo(ArbitraryPrecisionInterface n) {
checkInvariants(); // verify that the invariants hold
ArbitraryPrecision result = subtract(n);
value = result.value;
numDigits = result.numDigits;
}
public void multiplyBy(ArbitraryPrecisionInterface n) {
checkInvariants(); // verify that the invariants hold
ArbitraryPrecision result = multiply(n);
value = result.value;
numDigits = result.numDigits;
}
public void divideBy(ArbitraryPrecisionInterface n)
throws ArithmeticException {
checkInvariants(); // verify that the invariants hold
ArbitraryPrecision result = divide(n);
value = result.value;
numDigits = result.numDigits;
}
/* simple unit test code
* @param if arguments are given, executes the simple expression shown
* @return nothing
* @throws ArithmeticException when dividing by zero
*/
public static void main(String[] parameters) {
if (parameters.length == 3) {
ArbitraryPrecision x = new ArbitraryPrecision (parameters[0]);
ArbitraryPrecision y = new ArbitraryPrecision (parameters[2]);
ArbitraryPrecision result = new ArbitraryPrecision (); // zero
if (parameters[1].equals("+")) {
if (parameters[2].equals("1")) {
result = x.oneMore();
} else {
result = x.add(y);
}
} else if (parameters[1].equals("-")) {
if (parameters[2].equals("1")) {
result = x.oneLess();
} else {
result = x.subtract(y);
}
} else if (parameters[1].equals("*")) {
if (parameters[2].equals("2")) {
result = x.twice();
} else {
result = x.multiply(y);
}
} else if (parameters[1].equals("/")) {
if (parameters[2].equals("2")) {
result = x.half();
} else {
result = x.divide(y);
}
} else if (parameters[1].equals("%")) {
result = x.modulo(y);
} else {
System.out.println("unknown operator " + parameters[1]);
}
System.out.println(parameters[0] + " " +
parameters[1] + " " +
parameters[2] + " = " +
result);
} else {
System.out.println("three arguments expected");
}
}
}