A class for fractions of integers
The goal of the exercise of this week is to implement a class of fractions of integers supporting some basic operations like addition and multiplication. You can use the following interface for the class as a starting point and modify it at will:
class fraction {
private:
// Internal representation of a fraction as two integers
int numerator;
int denominator;
public:
// Class constructor
fraction(int n, int d);
// Methods to update the fraction
void add(fraction f);
void mult(fraction f);
void div(fraction f);
// Display method
void display(void);
};
The main idea above is that a fraction ab is represented by two integers (the numerator a and the denominator b) and several methods are provided to support arithmetic operations on fractions. For example:
fraction(int n, int m) constructs the fraction mn ;
void add(fraction f) updates a fraction by adding fraction f to it.
void mult(fraction f) updates a fraction by multiplying it by fraction f. void div(fraction f) updates a fraction by dividing it by fraction f.
Your program should read sequences of simple expressions from cin of the form: a/b+c/d,a/b*c/dora/bdivc/dandprovidethe result as a simplified fraction. For example, if the input is
1/4+1/2
your program should provide the following output to cout
3/4
which results from 1·2+1·4 = 6 which after simplification is 3 . 4·2 8 4
Challenge The suggested internal representation poses some limits on the ac-
tual domain of integral numbers that the fraction class can cover. For example,
the largest number would be INT MAX and the smallest positive fraction would be 1
1 . A possible remedy to mitigate this would be to exploit the fact that every INT MAX
integer can be represented by a product of prime numbers (see e.g. https:// en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic). This was indeed what we exploited in assignment 2. For example
137200 = 2 · 2 · 2 · 2 · 5 · 5 · 7 · 7 · 7
To avoid repeating the same prime number many times, we could equivalently
represent 137200 with exponentiation of prime numbers: 137200 = 24 ·52 ·73
We could thus represent all the exponents in an array of exponents, where the i-th element of the array represents how many times the i-th prime number occurs.1 So the representation of 137200 would be
arrayindex
array
corresponding prime number
01234 5 … 40230 0 … 2 3 5 7 11 13 . . .
Arithmetic operations can also exploit such representation. For instance, the multiplication of two numbers in such representation can be obtained by adding the corresponding exponents. For instance, multiplying the factorizations of 12 and 10 would be done as follows
primes 2 3 5
12 210
10 101 Adding exponents gives: 120 311
Division can be obtained in a similar manner, by substracting the exponents. Addition may be more involved.
The challenge is to implement the class of fractions with this representation technique.
1Formally, the factorization of a natural number n > 0 consists of the (uniquely determined) exponentsk1,k2,…suchthatn=pk1 ·pk2 ·…wherep1,p2,…aretheprimenumbers.
12
2
