Hint: here's a commonly used pattern for writing equals methods...
class T {
public boolean equals(Object o) {
// filter out references that don't point to instances of C...
if (! (o instanceof T)) return false;
// o refers to an instance of T, so cast it down...
T t = (T) o;
...compare t to this...
}
}
[In other words, the first few lines dispense with the annoying special cases
that stem from the fact that t is a reference of type
Object instead of type T. In the rest of the method,
you are free to think about just the "natural" case of comparing a
T object with another T object.]
Also, when reading the code above, it might help to recall the following Java fact:
(null instanceof T) is always false---that expression
does not throw a NullPointerException.
Hint: a MyNumber can be displayed by calling
System.out.println...
MyNumber n = new MyInteger(1004); System.out.println(n); // prints "1004"
(Recall that this works because println calls
n's toString method
to get the string representation of n, and,
as specified in MyNumber, n.toString()
returns the decimal representation of n---namely,
the string "1004".)
(Actually, System.out.println(o) should work for any
object / reference o. Authors of classes are responsible for making
sure that toString, which is inherited from Object,
always has a reasonable implementation.)
Hint: a MyNumber can be copied using clone.
For example,
MyNumber n0 = new MyInteger(3); MyNumber n1 = (MyNumber) n0.clone(); System.out.println(n0); // prints "3" System.out.println(n1); // prints "3" System.out.println(n0.equals(n1)); // prints "true" n0.plus(n0.createCompatible(1)); System.out.println(n0); // prints "4" System.out.println(n1); // prints "3" System.out.println(n0.equals(n1)); // prints "false"
Warning: beware of aliases when you manipulate MyNumber
objects! For example,
MyNumber n0 = new MyInteger(3);
MyNumber n1 = n0; // ...n1 and n0 refer to the _same_ object!
// ...does _not_ copy the object referenced by n0!
System.out.println(n0); // prints "3"
System.out.println(n1); // prints "3"
System.out.println(n0.equals(n1)); // prints "true"
n0.plus(n0.createCompatible(1));
System.out.println(n0); // prints "4"
System.out.println(n1); // prints "4" (!)
System.out.println(n0.equals(n1)); // prints "true" (!)
See Weiss section 3.6.1 for another example of aliasing.
[In general, aliasing-related bugs can be extremely difficult to track down, so it's usually best to program "defensively," keeping the alias issue in mind as you design and write the code.]
Whenever you find yourself writing...
MyNumber n1 = n0;
...you should ask yourself whether you really mean...
MyNumber n1 = (MyNumber) n0.clone();
Hint: you can test whether two compatible MyNumber objects
are equal (i.e., whether they currently store the same integer)
by using the equals method. For example,
MyNumber n0 = new MyInteger(3); MyNumber n1 = new MyInteger(3); MyNumber n2 = new MyInteger(4); System.out.println(n0.equals(n0)); // prints "true" System.out.println(n0.equals(n1)); // prints "true" System.out.println(n0.equals(n2)); // prints "false"
Warning: the == operator is almost never the right
choice for comparing MyNumber objects!
MyNumber n0 = new MyInteger(3); MyNumber n1 = new MyInteger(3); System.out.println(n0 == n0); // prints "true" System.out.println(n0 == n1); // prints "false" (!)
The test n0.equals(n1) is almost always what
people mean when they colloquially say "n0 equals
n1."
(You've probably already encountered this "== or
equals" issue once before, in the context of
String objects.)
Whenever you find yourself writing...
n1 == n0
...you should ask yourself whether you really mean...
n1.equals(n0)
Hint: you can use createCompatible to construct
small constants. If you have a MyNumber n
and you find yourself wanting to write...
n.plus(1); // ...increment n
// ...illegal, since plus takes a MyNumber, not an int.
...you can just write...
n.plus(n.createCompatible(1)); // ...increment n
// ...legal, since createCompatible returns a compatible MyNumber.
...instead.
Hint: you might want to use an array of digits in your implementation of
MyBigInteger, along the lines of...
// digit storage for the number 123456789101112131415
byte[] digits = { 5, 1, 4, 1, 3, 1, 2, 1, 1, 1, 0, 1, 9,
8, 7, 6, 5, 4, 3, 2, 1 };
// ...note that the array is "backwards," in a sense---digits[0] is
// the lowest-order digit (the "ones" digit, with multiplier
// 10^0), digits[1] is the next-lowest-order digit (the "tens"
// digit, with multiplier 10^1), etc.
[Sophisticated implementations will tend to use a base other than 10, e.g., base 128 or base 100, but for our purposes it's ok to simply store decimal digits (one decimal digit per array element).]
The (naïve) pseudocode for determining the number that's
stored in digits is...
constant BASE = 10
n = 0
for i = 0 to digits.length - 1
n += BASE^i * digits[i]
return n
[Nit: actually, n is just the magnitude of the number---the sign needs to be
stored elsewhere.]
Hint: you'll probably find that it's more convenient to store a MyBigInteger's sign
in an integral datatype (e.g., int or byte)...
private byte sign; // -1 if negative, 0 if zero, +1 if positive
...than to use a boolean flag...
private boolean isNegative; // ...less convenient, usually
[Recall that Java bytes are signed quantities capable of storing values
ranging from -128 to +127. For more
information on the ranges
of Java's primitive datatypes, see Weiss section 1.3.1.]
Hint: when implementing plus, times, etc.,
it's recommended that you simply use the arithmetic algorithms that you
learned in grade school. To refresh your memory, it would probably help to do a few large-ish
examples by hand.
After that, it might
be useful to look at how things go with "abstract" digits; e.g., try
adding the 5-digit number x4 x3 x2 x1 x0
to the 5-digit number y4 y3 y2 y1 y0:
x4 x3 x2 x1 x0
+ y4 y3 y2 y1 y0
------------------
r5 r4 r3 r2 r1 r0
Write down the algebraic formulas for the digits r0,
r1, etc. [For example, r0 =
(x0 + y0) % BASE.] Don't overlook
the carry digits :).
Hint: it's recommended that you implement (and rely heavily on) the following four methods:
// gets digit i, where digit 0 is the lowest-order digit.
// if i > getHighestOrderNonzero(), simply returns 0.
byte getDigit(int i);
// sets digit i to d.
// digit storage expands as necessary.
void setDigit(int i, byte d);
// ...calls expandToAccomodate, when appropriate.
// returns the index of the highest-order nonzero digit.
// [-1 if all digits are zero.]
int getHighestOrderNonzero();
// expands internal digit storage so that there's at least enough room
// to store digit i.
void expandToAccomodate(int i);
// ...typically, this involves allocating a new digits
// array and then copying the contents of the old array
// into the new one. (new digits are initialized to 0.)
// ...you might want to refer to Weiss's dynamic array expansion
// example in section 2.4.2.
The above methods allow you to behave as if your
array of digits were infinite (!), with all digits beyond
getHighestOrderNonzero() implicitly taken to be 0.
[Ideally, you would write an "infinite array of digits" abstraction,
with most of the above as public methods...
class InfiniteDigitArray {
public byte getDigit(int i);
public void setDigit(int i, byte d);
public int getHighestOrderNonzero();
protected void expandToAccomodate(int i);
private byte[] digits;
private int highestOrderNonzero;
}
...and then extend that core abstraction into a complete big-integer datatype...
class MyBigInteger extends InfiniteDigitArray implements MyIntegralNumber {
private byte sign; // -1 if negative, 0 if zero, +1 if positive
}
...this code structure isolates the gory storage-manipulation details
from the rest of the MyBigInteger implementation. it allows
you to test your storage management code separately, and it makes your
arithmetic methods easier to write and understand, etc.]
Warning: please make sure that your code is "alias-aware"; for example, operations like...
MyNumber n = new MyBigInteger(3); n.plus(n);
...must be handled correctly!