### Solution for

Programming Exercise 9.2

THIS PAGE DISCUSSES ONE POSSIBLE SOLUTION to
the following exercise from this on-line
Java textbook.

**Exercise 9.2:**
As discussed in Section 1, values of type
`int` are limited to 32 bits. Integers that are too large
to be represented in 32 bits cannot be stored in an `int`
variable. Java has a standard class, `java.math.BigInteger`,
that addresses this problem. An object of type `BigInteger`
is an integer that can be arbitrarily large. (The maximum size is
limited only by the amount of memory on your computer.) Since
`BigIntegers` are objects, they must be manipulated using
instance methods from the `BigInteger` class. For example,
you can't add two `BigIntegers` with the `+` operator.
Instead, if `N` and `M` are variables that refer
to `BigIntegers`, you can compute the sum of `N`
and `M` with the function call `N.add(M)`. The value
returned by this function is a new `BigInteger` object that
is equal to the sum of `N` and `M`.

The `BigInteger` class has a constructor
`new BigInteger(str)`,
where `str` is a string. The string must represent an
integer, such as "3" or "39849823783783283733". If the string
does not represent a legal integer, then the constructor
throws a `NumberFormatException`.

There are many instance methods in the `BigInteger` class.
Here are a few that you will find useful for this exercise. Assume
that `N` and `M` are variables of type `BigInteger`.

`N.add(M)` -- a function that
returns a `BigInteger` representing the sum of `N` and `M`.

`N.multiply(M)` -- a function that
returns a `BigInteger` representing the result of multiplying
`N` times `M`.

`N.divide(M)` -- a function that
returns a `BigInteger` representing the result of dividing `N`
by `M`.

`N.signum()` -- a function that
returns an ordinary `int`. The returned value represents the
sign of the integer `N`. The returned value is 1 if `N`
is greater than zero. It is -1 if `N` is less than zero.
And it is 0 if `N` is zero.

`N.equals(M)` -- a function that
returns a `boolean` value that is `true` if `N`
and `M` have the same integer value.

`N.toString()` -- a function that
returns a `String` representing the value of `N`.

`N.testBit(k)` -- a function
that returns a `boolean` value. The parameter `k` is an
integer. The return value is `true` if the `k`-th
bit in `N` is 1, and it is `false` if the `k`-th
bit is 0. Bits are numbered from right to left, starting with 0.
Testing "`if (N.testBit(0))`" is an easy way to
check whether `N` is even or odd. `N.testBit(0)`
is `true` if and only if `N` is an odd number.

For this exercise, you should write a program that prints
`3N+1` sequences with starting values specified by the user.
In this version of the program, you should use `BigIntegers`
to represent the terms in the sequence. You can read the user's
input into a `String` with the `TextIO.getln()` function.
Use the input value to create the `BigInteger` object that
represents the starting point of the `3N+1` sequence.
Don't forget to catch and handle the `NumberFormatException`
that will occur if the user's input is not a legal integer! You should
also check that the input number is greater than zero.

If the user's input is legal, print out the `3N+1` sequence.
Count the number of terms in the sequence, and print the count at the
end of the sequence. Exit the program when the user inputs
an empty line.

**Discussion**

My solution uses a subroutine, `printThreeNSequence(N)`, to
print out the `3N+1` sequence starting from the `BigInteger`,
`N`.
The subroutine assumes that `N` is not `null` and that it
represents a value that is greater than one. (These conditions are
ensured by the main program which calls the subroutine.) Given these
assumptions, the subroutine cannot generate any errors. The only
interesting aspect of the subroutine is that all operations on
`N` must be performed using instance methods from the
`BigInteger` class. For example, to multiply `N` by
2, I use a statement "`N = N.multiply(TWO);`",
where `TWO` is a `BigInteger` that represents the
integer 2. My program defines `TWO` as a constant,
along with several other `BigIntegers` that represent
values that I need:

static final BigInteger THREE = new BigInteger("3");
static final BigInteger ONE = new BigInteger("1");
static final BigInteger TWO = new BigInteger("2");

With these constants, the code for computing the next term
in a `3N+1` sequence becomes:

if (N.testBit(0) == false) {
// N is even. Divide N by 2.
N = N.divide(TWO);
}
else {
// N is odd. Multiply N by 3, then add 1.
N = N.multiply(THREE);
N = N.add(ONE);
}

You can find the complete subroutine in the solution that is given
below.

In the `main()` routine, the user's input is read into a
variable, `line`, of type `String`. The input is used
to construct a `BigInteger` with the statement
"`N = new BigInteger(line);`". Since this statement can
produce a `NumberFormatException`, it is placed in a `try`
statement that can catch and handle the error. The test
"`if (N.signum() == 1)`" is used to make sure that `N >= 1`.
The value of `N.signum()` is 1 if and only if `N` is a
positive integer. Here is the loop form the `main()` routine
that processes the users input:

while (true) {
TextIO.putln();
TextIO.putln("Enter the starting value, or press return to end.");
TextIO.put("? ");
line = TextIO.getln().trim();
if (line.length() == 0)
break;
try {
N = new BigInteger(line);
if (N.signum() == 1)
printThreeNSequence(N);
else
TextIO.putln("Error: The starting value cannot be less than or equal to zero.");
}
catch (NumberFormatException e) {
TextIO.putln("Error: \"" + line + "\" is not a legal integer.");
}
}

**The Solution**

/*
This program prints out 3N+1 sequences for starting values of N that
are entered by the user. Since integers are represented as objects of
type BigInteger, it will work for arbitrarily large integers. The
starting value specified by the user must be greater than zero. The
program continues to read input from the user and print 3N+1 sequences
until the user inputs an empty line. If the user's input is illegal,
the program will print an error message and continue.
*/
import java.math.BigInteger;
public class BigThreeN {
static final BigInteger THREE = new BigInteger("3");
static final BigInteger ONE = new BigInteger("1");
static final BigInteger TWO = new BigInteger("2");
public static void main(String[] args) {
String line; // A line of input from the user.
BigInteger N; // The starting point for the 3N+1 sequence,
// as specified by the user.
TextIO.putln("This program will print 3N+1 sequences for positive starting values");
TextIO.putln("that you enter. There is no pre-set limit on the number of");
TextIO.putln("digits in the numbers that you enter. The program will end when");
TextIO.putln("you enter an empty line.");
while (true) {
TextIO.putln();
TextIO.putln("Enter the starting value, or press return to end.");
TextIO.put("? ");
line = TextIO.getln().trim();
if (line.length() == 0)
break;
try {
N = new BigInteger(line);
if (N.signum() == 1)
printThreeNSequence(N);
else
TextIO.putln("Error: The starting value cannot be less than or equal to zero.");
}
catch (NumberFormatException e) {
TextIO.putln("Error: \"" + line + "\" is not a legal integer.");
}
}
TextIO.putln();
TextIO.putln("OK. Bye for now!");
} // end main()
static void printThreeNSequence(BigInteger N) {
// Print the 3N+1 sequence starting from N, and count the number
// of terms in the sequence. It is assumed that N is not null and
// that it is greater than zero.
int count; // The number of terms in the sequence.
TextIO.putln();
TextIO.putln("The 3N+1 sequence starting with " + N + " is:");
TextIO.putln();
TextIO.putln(N.toString()); // Print N as the first term of the sequence
count = 1;
while ( ! N.equals(ONE) ){ // Compute and print the next term
if (N.testBit(0) == false) {
// N is even. Divide N by 2.
N = N.divide(TWO);
}
else {
// N is odd. Multiply N by 3, then add 1.
N = N.multiply(THREE);
N = N.add(ONE);
}
TextIO.putln(N.toString());
count++;
}
TextIO.putln();
TextIO.putln("There were " + count + " terms in the sequence.");
} // end printThreeNSequence
} // end BigThreeN

[ Exercises
| Chapter Index
| Main Index
]