Parts of this assignment require you to understand big-Oh notation (which will be covered in class on Wed 2/4).
Goals of this homework:
Numeric
) can have different implementations.
Collaboration policy for this homework:
You must follow the CS
Department Academic Integrity Code, except that for this
homework, you may optionally work with one other student in the
class. If you do so, you must say who your partner was at the top of
your Readme
file, and both of you will receive the same grade
for the assignment.
Readme
file.
What to hand in (all packaged up in a zip or tar file):
RussianDoll.java
. The completed version you
hand in must implement the Numeric
interface;
we'll use that interface to test your code. Our tests will
also assume that you have implemented public static
methods valueOf
and newWork
, and a
public instance method multiplySlow
.
NumericTest.java
, as modified by you, showing
that you did an adequate job of testing. (You could also
put most of your test code in RussianDoll.java
if you prefer.)
Numeric.java
. This is given to you and you
don't need to change it.
doc
subdirectory containing HTML documentation
that you have generated with the command
javadoc -private -linksource -d doc *.java
.
The graders will look at this documentation, so you should
provide javadoc comments for all of your methods, including
private ones.
Again, please follow the style guidelines in section 1.9.2 of the textbook.
Readme
file that contains your answers to
miscellaneous questions on the homework (i.e., answers that don't
go in any other file). Usually these are English paragraphs
or small fragments of code.
We have already begin discussing in class how an abstract data type can be implemented in multiple ways. For example, stacks can be implemented using either arrays or linked lists.
Similarly, there are multiple ways to implement the natural numbers
(0, 1, 2, 3, ...). Modern computers typically use a binary
representation. (Of course, Java's built-in integer type doesn't
really implement the natural numbers -- with 32 bits it can only
represent numbers up to 2147483647. But the java.math.BigInteger
class basically uses an array of bits; for larger numbers it just uses
more bits.)
The Russian dolls that we developed in class can also be made to represent natural numbers, essentially in unary notation. This representation is much simpler but also much less efficient, so you can guess that it was invented by a mathematician (Giuseppe Peano in 1889) rather than an engineer. His main point (published in Latin, just for kicks) was that if God had not seen fit to give us integers, we could have built them out of something else.
In this assignment, you will do just that and build integers out of Russian dolls - complete with addition, subtraction, multiplication, and division. You'll find out just how inefficient this implementation is, both by using big-Oh notation and by actually measuring it. Finally, you'll make it a bit more efficient.
Your job in this assignment is to finish the partly written RussianDoll
class. By
the time you are done, it will be an implementation of this supplied Numeric
interface. (Other
implementations of that interface include java.math.BigInteger
.)
To test that you are correctly implementing the interface, you can
write a test class that manipulates Russian dolls through that
interface; we have supplied a small NumericTest
to get you
started.
Copy the above three files from this source directory. Start by reading the source code files and their documentation. (If you like, you could also look at the successive versions we developed in class.)
All the methods that do arithmetic on Russian dolls should only use
Russian dolls. But first, add two methods to the
RussianDoll
class that convert between Russian dolls
and longs:
public long longValue() { ... } public static RussianDoll valueOf(long val) { ... } |
You should implement one of them using recursion and the other
using iteration - either way around, as you prefer. The
add
or toString
method illustrates how to
use recursion.
The expected behavior of these methods is documented in the Numeric
interface (including
the comments at the top). Make sure that they throw
ClassCastException
if the conversion can't be
accomplished, e.g., valueOf(-2)
, or
rd.longValue()
where the appropriate return value exceeds
Long.MAX_VALUE
. (Note: ClassCastException
,
like the other
subclasses of RuntimeException
, is an unchecked
exception, meaning that you don't have to include "throws
ClassCastException
" in the method signature.)
You should not use these methods to implement any of the other methods below, although they will be useful to help you test those methods. The other methods must be implemented entirely with Russian dolls without using any of Java's built-in numeric types (byte, short, integer, long, float, double, BigInteger, etc.) in any way, not even as array indices.
Readme
file:
add
method by
studying the source code. Specifically, if two numbers a and b are
represented as Russian dolls, does a.add(b)
take time
O(a), O(b), O(a+b), O(ab), or something else? Explain.
add
method by
studying the source code. Specifically, if two numbers a and b are
represented as Russian dolls, does a.add(b)
use space
O(a), O(b), O(a+b), O(ab), or something else? Explain.
Now you will actually check your answers by instrumenting the
source code. This means making the code keep track of what it is
doing. Implement the following methods in RussianDoll
:
/** Returns the total amount of work done by this class since * the last time this method was invoked. The amount of * work is measured by the total number of calls to the * bigger and smaller methods, no matter who called them */ public static long newWork() { ... } /** Returns the total amount of space allocated by this class * since the last time this method was invoked. The amount of space * is measured by the total number of calls to constructors (not * including the call that created ZERO). Possibly some of the * space was released along the way. */ public static long newSpace() { ... } |
Hint: Start by defining a private static field that is
incremented on each call to bigger
or
smaller
... Reset that field to 0 sometimes ...
Readme
:
a.add(b)
for various values of a
and
b
. Use newWork
to report the amount of
work done in each case (not counting the work to create
a
and b
!). Use these results to guess an
exact formula (without big-Oh notation) for the return value of
newWork
in terms of a
and b
.
Did your big-Oh answer in question 1 correctly describe this
formula?
newSpace
. Did your big-Oh answer in
question 2 correctly describe this formula?
Tip of the day: In answering the above questions, did you
find yourself cutting-and-pasting code? Rather than write new code
for every pair of numbers that you want to try adding, it is easier to
write a new method that you can call as something like
addTest(30,40)
, and which prints the work and space
needed for that addition. Then it's easier to read the code, easier
to add new tests, and it's easier to change the way the test works or
prints its results.
Add equals
and compareTo
methods to
RussianDoll
. Again, the desired behavior is documented
in the Numeric
interface
(although for now, you may assume that the argument is a
RussianDoll
, not an arbitrary Object
). You
may use either iteration or recursion, but recursion is more
elegant.
Remember that you are not allowed to use Java's built-in numeric
types (except for the return value of compareTo
). As
always, if you find yourself writing duplicate code, reorganize things
to avoid this!
Readme
:
equals
? You may wish to check this using
newWork
.
Implement the subtract
, multiply
, and
divideAndRemainder
methods with the behavior documented
in the Numeric
interface.
For now, assume that they take a RussianDoll
argument and
return a RussianDoll
. Either recursion or iteration is
okay; I think recursion is easier for subtract
and
multiply
, whereas iteration is easier for divideAndRemainder
.
Test the methods to your satisfaction.
subtract
can be implemented in a manner similar to
compareTo
.
multiply
can use repeated addition, exactly as
add
used repeated increments.
divideAndRemainder
can use repeated subtraction.
addTest
method that you could call from
main
. You may also want to write
subtractTest
, multiplyTest
, etc.
As much as possible, avoid duplicating code among these
test functions.
Because the RussianDoll
class can't represent
negative numbers, we have to decide what a.subtract(b)
does when a < b. Your implementation should return ZERO
in this case. This decision is consistent with our earlier decision that
ZERO.smaller() == ZERO
.
Remember from earlier in this homework that add
has
asymmetric time and space requirements. That is,
a.add(b)
might be less efficient than
b.add(a)
, even though both give the same answer. Since
multiply
is implemented by repeated addition, it matters
whether multiply
calls add
efficiently or
inefficiently.
To see how much this matters, create a second version of
multiply
, where instead of x.add(y)
you do
y.add(x)
(for whatever objects x
and
y
you are adding). Call the fast version
multiply
and call the slow version
multiplySlow
. (Warning: Make sure that
multiplySlow
recurses by calling
multiplySlow
, not multiply
.)
a.multiply(b)
in terms of a
and
b
? Explain why this is true theoretically (based on
what the code has to do), and also support your answer with several
results from newWork
.
a.multiplySlow(b)
. This is the most interesting
question on the assignment!
Numeric
interfaceNow the RussianDoll
class almost implements the
Numeric
interface. Augment the first line of
RussianDoll.java
to make this intention explicit:
public class RussianDoll implements Numeric { |
Now fix RussianDoll.java
so that it compiles again.
That means the compiler agrees that RussianDoll
is a
valid implementation of Numeric
. Some things you may
have to do:
Numeric.add
(for example) is an abstract method
that can be called with any Numeric
argument:
public Numeric add(Numeric val);If
RussianDoll
implements Numeric
, then we
must be able to call RussianDoll.add
with any
Numeric
argument. So the signature we gave you,
public RussianDoll add(RussianDoll val)is not enough; you actually need to change it to
public RussianDoll add(Numeric val)
The method should simply cast val
to a
RussianDoll
before working with it. If
val
is some other kind of Numeric, like a
BigInteger
, trying to cast it to
RussianDoll
may throw a ClassCastException
-- which the Numeric
interface says is an appropriate response if
someone tries to add
two Numeric
objects
from different subclasses.
It gets worse. For some brain-dead reason, since
Numeric.add
returns a Numeric
,
public Numeric add(Numeric val);Java thinks that the
RussianDoll.add
method that implements it must have
exactly the same signature, and explicitly return a
Numeric
. I am completely baffled by this -- it should
be enough to return RussianDoll
, since after all that
is a kind of Numeric
. But this obvious feature (called
"covariant return types") isn't coming until Java 1.5; there are
many complaints
on the web.
So unfortunately, the compiler will only compile your RussianDoll
class as an implementation of Numeric
if you further change
public RussianDoll add(Numeric val)to
public Numeric add(Numeric val) // can still return a RussianDollin your
RussianDoll
class. Similarly for several other
methods.
This requires a few other
changes in RussianDoll.java
, since now the result
of a.add(b)
is a Numeric
, and cannot
be assigned to a RussianDoll
variable without an
explicit cast.
Just as RussianDoll.add
must be able to apply
to any Numeric
argument, the
RussianDoll.compareTo
method must be able to apply to
any Object
argument. Again, it should simply try to
cast this argument to RussianDoll
, at the risk of
throwing a ClassCastException
if this fails.
Remember that RussianDoll.subtract
behaves in a
non-obvious way that could not be predicted from the documentation
of Numeric.subtract
. So make sure to document this
behavior at RussianDoll.subtract
. (Why would it be
a bad idea to document it at Numeric.subtract
?)
RussianDoll
compiles again, try the
NumericTest
class to make sure that
RussianDoll
objects
can be treated as Numeric
and act as expected.
Extend NumericTest
to test the code
until you are sure everything is working.
Answer in your Readme
:
This assignment has said several times that
java.math.BigInteger
also implements Numeric
.
However, Java doesn't know that! For example, we can't store
a BigInteger
in a Numeric
variable.
Since we didn't write the BigInteger
class, we can't
just add implements Numeric
to its first line (the way we
did for RussianDoll
). So how can we easily create a
kind of BigInteger
class that does implement Numeric?
(You might want to try your answer out!)
Let's close with a neat trick.
In general, we should try to avoid calling new
: it's
relatively slow and it uses up memory. For example,
bigger
is more wasteful than smaller
because
it calls new
. But our RussianDoll
class
seems to call new
more often than it has to. Consider
the following code:
/* This code should be put at the top of main. */ RussianDoll rd1 = RussianDoll.valueOf(500); // a representation of 500 Numeric rd2 = RussianDoll.valueOf(25).multiply(RussianDoll.valueOf(20)); // builds a completely separate representation of 500 RussianDoll rd3 = RussianDoll.valueOf(501); // doesn't contain either rd1 or rd2 RussianDoll rd4 = RussianDoll.valueOf(499); // not contained in either rd1 or rd2 System.out.println("Work: " + newWork() + " Space: " + newSpace()); |
We'd really prefer the four values above to share space in memory. Then we'd only need to call new about 500 times, not about 2000 times. In general, there should be a unique doll representing 499, which is nested inside the unique doll representing 500, etc.
How might we achieve this? A first thought is for the
RussianDoll
class to maintain a static array that maps
499 to the unique 499 doll, etc. However, then we'd have to do Java
integer arithmetic to compute the array indices, whereas we are trying to
build our own integers.
The right solution is for each RussianDoll
instance
rd
to have an outer
field as well as an
inner
field. If rd
is the unique doll
representing the number n, then rd.outer
should store the
unique doll representing n+1, or null
if that doll hasn't
been created yet.
This is an example of a key strategy for data structures: store
now what you will need again later! This is sometimes called
"trading space for time." If the original RussianDoll
class resembled a singly linked list, the modified one resembles a
doubly linked list. Both doubly linked lists and our improved Russian
dolls store the reverse pointers in order to save time later on.
Modify the RussianDoll
class in this way, so that
there is at most one doll representing each number. You should still
count bigger
as doing work, but you should only count it
as using space if it calls new
. Try running the code
above both before and after your modification.
Readme
:
newWork
and newSpace
return for the above code, both before and
after the modification? Explain why you got exactly the numbers you
got.
rd.outer
is faster than creating a new doll with
new RussianDoll(rd)
. But will it actually improve the
asymptotic complexity (big-Oh formula) for any of the arithmetic
methods? Defend your answer.
==
. If equals
is changed to take full
advantage of this fact, what is the asymptotic (big-Oh) runtime of
a.equals(b)
? Compare to your answer to question 5.
We have noted that add
has asymmetric runtime. So if
you know which of a
and b
is bigger,
then you know whether a.add(b)
or b.add(a)
is faster. But in general, you probably won't know this ahead of
time.
For extra credit, can you modify the implementation of
add
to solve this asymmetry? Your implementation should
be fast whenever either a
or b
is small,
even if the other addend is incredibly large.
add
as part
of your RussianDoll.java
, you should answer the following
in your Readme
:
add
.
add
is sometimes slower than the old one? If so,
what is the motivation for using the new add
?
jason@cs.jhu.edu
- $Date: 2004/02/02 19:33:41 $