Discussion 6: Immutable Classes

Download Handout download

Arithmetic operations with floating-point numbers (doubles and floats) are not perfectly precise. This is because we are constrained to a fixed number of bits with which to represent these numbers. The designers of the IEEE 754 standard for floating point representation chose a representation that mitigates this imprecision to the maximum extent possible; however, some floating-point arithmetic error is inevitable. In mathematical software such as Computer Algebra Systems (e.g., WolframAlpha), we’d like to maintain perfect precision when working with rational numbers (i.e., fractions), as these systems serve as important research tools in areas like number theory. To do this, we need to step away from primitive floating point numbers and develop our own type that can ensure this perfect precision.

In today’s discussion, you’ll develop an immutable type to represent a rational number. When possible, we prefer for our types to be immutable, since this lessens the burden of maintaining the class invariant; once the invariant is established by the constructor, it can never be violated since the state of an immutable object does not change. During the discussion, we’ll also explore some Object methods and an interface that we can use to add richer behaviors to a type.

Learning Outcomes

Reminder: Discussion Guidelines

The work that you complete in discussion serves as a formative assessment tool, meaning it offers the opportunity to assess your understanding of the material and for our course staff to get a “pulse” on how things are going so we can make adjustments in future classes. Your grade in discussion is based entirely on attendance and participation; if you show up and you are actively engaged with the activity (working on the activity on your computer, discussing the activity with your group, asking and answering questions, etc.) for the entire 50-minute section period, you will earn full credit. If you complete the activity early, helping other students is a great way to further your own understanding. You do not need to submit any of the work that you complete during discussion.

Since discussion activities are not graded for correctness, we do not place any restrictions on resources that you may use to complete them, which include notes, books, unrestricted conversations with other students, internet searches, and the use of large language models or other generative AI. We advise you to be pragmatic about your use of these resources and think critically about whether they are enhancing your learning. Discussion activities are intended to serve as “strength training” for programming tasks we will expect on assignments and exams (and that you will encounter in future courses and careers), and their main benefit comes from critically thinking to “puzzle” them out.

Working together in small groups is encouraged during discussion!

The Rational Class

In this discussion, you’ll develop a Rational class to represent rational numbers. We say that a number \(x\) is rational if it can be represented as a quotient of two integers \(x = \frac{p}{q}\) where \(q \ne 0\). Since one rational number can be represented as many different quotients, \( -0.6 = \frac{-3}{5} = \frac{6}{-10} = \frac{-72}{120}\), we typically impose the additional conditions that \(p\) and \(q\) are relatively prime, \(\textrm{gcd}(|p|,|q|) = 1\) (so the fraction is in lowest terms) and that \(q > 0\). We call this the simplified form of the rational number.

We’ll represent the state of this class (including its public accessor methods) as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
 * Models a rational number, represented as the quotient of two `int`s in 
 * simplified form. To keep things simple for this discussion, we ignore the 
 * possibility of overflow by assuming that the numerators and denominators of 
 * these fractions are sufficiently small.
 */
public class Rational {

    /**
     * The numerator of the simplified representation of this rational number. 
     * Must have gcd(num,denom) = 1.
     */
    private final int num;

    /**
     * The denominator of the simplified representation of this rational number. 
     * Must have gcd(num,denom) = 1 and denom > 0.
     */
    private final int denom;

    /**
     * Returns the numerator of the simplified representation of this rational number.
     */
    public int numerator() {
        return num;
    }

    /**
     * Returns the denominator of the simplified representation of this rational number.
     */
    public int denominator() {
        return denom;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
 * Models a rational number, represented as the quotient of two `int`s in 
 * simplified form. To keep things simple for this discussion, we ignore the 
 * possibility of overflow by assuming that the numerators and denominators of 
 * these fractions are sufficiently small.
 */
public class Rational {

    /**
     * The numerator of the simplified representation of this rational number. 
     * Must have gcd(num,denom) = 1.
     */
    private final int num;

    /**
     * The denominator of the simplified representation of this rational number. 
     * Must have gcd(num,denom) = 1 and denom > 0.
     */
    private final int denom;

    /**
     * Returns the numerator of the simplified representation of this rational number.
     */
    public int numerator() {
        return num;
    }

    /**
     * Returns the denominator of the simplified representation of this rational number.
     */
    public int denominator() {
        return denom;
    }
}

Use the provided test cases throughout the development of the Rational class to help verify the correctness of your implementation.

The Rational Constructor

Add a constructor to the Rational class. This constructor takes in any integers num and denom as its arguments, with only the precondition that denom != 0, and uses these to initialize the Rational fields in a way that satisfies the class invariant. It may be helpful to use the gcd code (with slight modification) that you wrote in Discussion 1 as a helper method for this constructor.

The toString() Method

Override the toString() method from the Object class (Rational’s default superclass) to print out the simplified fraction representation of the rational number.

The equals() Method

Override the equals() method from the Object class so that it returns true when other is a Rational object representing the same number as this Rational object. Follow the equals() template in the lecture notes.

Arithmetic Operations

Next, you’ll add methods to compute the sum(), difference(), and product() of two Rational number objects. Since Rational is an immutable class (similar to String), these methods all construct and return a new Rational object whose value results from carrying out this operation. Each of our definitions is a single line of code (this is not a requirement, though) and follows from the rules for arithmetic on fractions.

Egyptian Fractions

In the Egyptian numeral system, there was a hieroglyph that was used to decorate the glyph of a whole number \(n\) to represent its reciprocal \(\frac{1}{n}\). With a few exceptions, this meant that Egyptian math involving fractions was based around unit fractions, fractions whose numerator is 1. Perhaps surprisingly, this isn’t a limiting constraint, since we can represent any positive rational number as a sum of distinct unit fractions. For example, we can write

\[ \frac{5}{7} = \frac{1}{2} + \frac{1}{5} + \frac{1}{70}. \]

We call such a sum an Egyptian fraction representation of \(\frac{5}{7}\). One can always use the following “greedy” procedure to generate an Egyptian fraction representation of a positive rational number (although this procedure doesn’t guarantee to produce the smallest representation with the fewest number of fractions… this is a very difficult mathematical problem):

Given a rational number, \(r\), initialize a variable \(d = 1\) to represent the next denominator to consider. If \( \frac{1}{d} \leq r \), then append \(\frac{1}{d}\) to the Egyptian fraction representation, and subtract \(\frac{1}{d}\) from \(r\). Increment \(d\) and repeat this process until \(r = 0\).

The class EgyptianFraction.java contains a small application that prompts the user for a positive number and prints its Egyptian fraction representation. You have been given a complete definition of the main() method, which processes the user input; now that we have learned about exceptions, take a minute to look at the exception handling code within this main() method.

Complete the printEgyptianFractionRepresentation() method, which accepts a Rational number as its argument and computes/prints the “greedy” Egyptian fraction representation of this number. Many of the methods that you wrote in the Rational class should be helpful for this task. Be sure to carefully read the specifications of this method to understand how it expects you to format your print output.