> ### Solution for
> Programming Exercise 9.2

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

> 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 the `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 ]