COM S 211 / ENGRD 211

Computers and Programming
Fall 2000

HW2-accel

Watch this space for updates!

At the end of last week's accelerated exercise, we were pondering the following question:

  What are the ways your program can be modified to handle larger
  numbers -
  say, of 100 to 1000 digits ?

In this week's exercise, we will look into two salient aspects of handling big integers. First, how might we go about storing a number that has thousands of digits? Second, how would we want to manipulate such a number; what sorts of operations would we want our big-integer type MyBigInteger to support? If we're going to have two different mutable-integer data types, MyInteger and MyBigInteger, will we be doomed to write two different implementations of every algorithm that works on integers? In particular, must we write a getFactor(MyBigInteger) method, duplicating the work we previously did on getFactor(MyInteger)?

<source files: MyBigInteger.java MyInteger.java>

We'll see how one might deal with these two aspects of large numbers as the exercise progresses. [Please note, however, that the approach that you're asked to follow below is only one of many possibilities---as you proceed through the exercise, you are strongly encouraged to ask yourself what the alternatives and the trade-offs are.]

  1. Take a look at the MyNumber and MyIntegralNumber interfaces, which are intended to abstract the signature of MyInteger.

    < source files: MyNumber.java  MyIntegralNumber.java >

    What are the advantages of making MyIntegralNumber an interface instead of an abstract class? What are the disadvantages? (You may want to revisit this question after you complete the rest of the exercise...)

  2. Once you're familiar with those two interfaces, bring your MyInteger code from HW #1 under their umbrella, by modifying MyInteger so that it correctly implements the MyIntegralNumber interface.

    [You may use the HW #1 sample solution's MyInteger code instead of your own MyInteger code, if you prefer to do so.]

  3. Complete the MyNumbers class, as a quick warm-up exercise in dealing with numbers via an interface.

    < stub file: MyNumbers.java >

  4. Widen the applicability of your Factorize code from HW #1, by modifying getFactor so that it takes a MyIntegralNumber instead of a MyInteger.

    class Factorize {
  public static void getFactor(MyIntegralNumber ival) {
    ...
  }
}

    (Of course, there's a bit more to this step than simply changing the method header.)

    [You may use the HW #1 sample solution's Factorize code instead of your own Factorize code, if you prefer to do so.]

    <source file: Factorize.java>

    What are some of the advantages of using MyIntegralNumber instead of the more concrete type MyInteger? What are some of the disadvantages? Please take a moment to consider how the concepts of abstraction, polymorphism, and modularity might be at work in this case.

  5. Try out your refurbished factorization code by encapsulating the numbers 169, 899, 401, 769, and 68983 in MyInteger objects and passing them to getFactor.

  6. Implement the MyBigInteger class.

    [Your big-integer code should all be written "from scratch"; you may not rely on java.math.BigInteger, java.math.BigDecimal, or any other "big number" code that you do not write yourself. (You may, however, use utility classes such as java.util.Vector and java.util.List, if you wish.) The idea is for you to learn the details of how big-integer data structures work, by implementing the internals of (a simplified) one yourself.]

    < stub file: MyBigInteger.java >

  7. Try out your MyBigInteger code by encapsulating the numbers 169, 899, 401, 769, and 68983 in MyBigInteger objects and passing them to getFactor.

    Once you've convinced yourself that things are working smoothly, try finding a non-trivial factor of the "slightly larger" integer 100132; written explicitly (in decimal) this number is... 

    1032500996162285568402413441490620685601924366584503199521929020299321666762393411964960496032001

    (Your code should be able to find a non-trivial factor of the above integer, in a reasonable amount of time.)

    Why keep MyInteger around? Isn't it redundant, now that we have MyBigInteger?

    Realistically, how many digits can your implementation of getFactor handle? Would factoring a 1000-digit number be feasible? Are some 1000-digit numbers easier to factor than others?

  8. If you're confident in the efficiency of your code, you might be interested in trying more challenging input, such as...

    (These five test-cases are optional.)

  9. Try out any other big-integer examples that pique your interest, and have fun!

What to hand in

You'll need to submit the following items:

Please recall that, in general, your electronic submission must include all of the source files required to compile your program(s) but that your hardcopy submission should, in contrast, only include the source files that you wrote (or modified).

Looking for hints? Please see the new hints page.

Miscellaneous Notes and Clarifications

Note 1:

You needn't worry too much about efficiency in this exercise. At this point in the course, we're more interested in correctness, structure, style, and design.

Please feel free to use straightforward / naïve algorithms, as long as the test factorizations specified above (and similar cases) take less than an hour or two to run.
Note 2:

You do not need to hand in answers to the questions posed above. We just want you to get into the habit of thinking critically about design decisions (yours as well as other peoples').

For this exercise, you only need to hand in Java code and test-run output.
Note 3:

MyBigInteger must implement MyIntegralNumber.

MyBigInteger must comply with the comments given in the MyBigInteger.java stub file.

MyBigInteger must implement (at least) the public constructor that's specified in the MyBigInteger.java stub file.
Note 4:

In general, your implementations must comply with the comments and documentation given in the supplied stub files (*.java) as well as the supplied javadoc-generated files (*.html).

MyInteger must comply with the documentation given in the javadoc-generated file MyInteger.html.

MyNumbers must comply with the documentation given in the javadoc-generated file MyNumbers.html.

Factorize must comply with the documentation given in the javadoc-generated file Factorize.html.

You may add members, fields, superclasses, etc. to MyInteger, MyNumbers, Factorize, and MyBigInteger; you just can't remove (or weaken) the given method specifications, constructor specifications, and implements clauses in those four classes.

You may define as many additional classes and interfaces as you see fit.
Note 5:

You must not modify the definitions of the two mutable-number interfaces, MyNumber and MyIntegralNumber---you absolutely must use the definitions & specifications that we've given in MyNumber.java and MyIntegralNumber.java.

(In particular, you may not add methods or extends clauses to either of those interfaces.)

The idea is to work within the constraints imposed by those two interfaces (and to learn something about the costs and benefits of abstraction as you go).
Note 6:

"A non-trivial factor of N" just means "a positive integer that divides N, excluding 1 and N itself."

So, the non-trivial factors of 12 are 2, 3, 4, and 6; 1 and 12 are the trivial factors.