# COMP 5421/1 BB Assignment 2 solution

\$40.00

Original Work ?
Category:

## Objectives

1. Experience creating an abstract data type (ADT)1

3. Learn about function objects and how to define them 2

## Assignment Background

A data type represents a set of data values sharing common properties. An abstract data type (ADT) specifies a set of operations on a data type, independent of how the data values are actually modeled or how the operations are implemented.

Classic ADTs such as rational number and complex number ADTs support many arithmetic, relational and other operations, making them ideal data types for operator overloading.

However, a search for “class rational c++” reveals many turnkey C++ classes, forcing assignments designed to provide practice with operator overloading to get a bit creative with their choice of data types; ideally, a data type that is not as ubiquitous as rational and complex number ADTs but lends itself to operator overloading just as good.

Quad is an abstract data type, representing a set of values of the form x1 x2 + x3 x4 √ 2, with x1, x2, x3, x4 all integers and x2 6= 0, x4 6= 0 (1) and providing a typical set of operations on those values. In this assignment, we will refer to such values as quad numbers.

The integers x1 and x2 represent the real part, and the integers x3 and x4 represent the quad part, of a quad number.

## 3.1 Notation

To facilitate presentation of operations on quad numbers, we abstract quad numbers into a sequence of four ordered integers x1, x2, x3, and x4, corresponding to the same integers in (1).

We use the notations x1, x2, x3, x4 and     x1 x2 x3 x4     to represent the same quad number, whichever is more convenient for expressing an operation. 1ADT ≡ Values + Operations − Implementation details of both 1

Quad x x1, x2, x3, x4 , x2 6= 0 and x4 6= 0 x Normalized    [−x1, −x2, x3, x4] if x2 < 0 [x1, x2, −x3, −x4] if x4 < 0 [−x1, −x2, −x3, −x4] if x2 < 0 and x4 < 0 x Reduced  x1 gcd(x1, x2) , x2 gcd(x1, x2) , x3 gcd(x3, x4) , x4 gcd(x3, x4)  x Standardized Both

Reduced and Normalized x Conjugated x1, x2, −x3, x4 , x2 6= 0 and x4 6= 0 Zero 0, z2, 0, z4 , z2 6= 0 and z4 6= 0 Standard zero 0, 1, 0, 1 Identity 1, 1, 0, i4 , i4 6= 0 Standard identity 1, 1, 0, 1 An integer k as a Quad the quad number k, 1, 0, 1 where gcd(a, b), called the greatest common divisor of the nonzero integers a and b, represents a positive integer d such that (1) d is a divisor of both a and b, and (2) any divisor of both x and y is also a divisor of d. For example, gcd(63, 14) = 7, and gcd(30, 45) = 15; thus, the reduced form of the quad number 63, 14, 30, 45 is 9, 2, 2, 3 .

The basic operations on quad values are listed below, using as operands the quad numbers x = x1, x2, x3, x4 and y = y1, y2, y3, y4 . Operation Definition Negation − x1, x2, x3, x4 = −x1, x2, −x3, x4 Addition Subtraction     x1 x2 x3 x4     ±     y1 y2 y3 y4     =     x1y2 ± x2y1 x2y2 x3y4 ± x4y3 x4y4     2 Multiplication     x1 x2 x3 x4     ∗     y1 y2 y3 y4     =     x1y1x4y4 + 2x3y3x2y2 x2y2x4y4 x1y3y2x4 + y1x3x2y4 x2y2x4y4     Scalar Multiplication k ∗ x =     kx1 x2 kx3 x4     = x ∗ k Scalar Addition Scalar Subtraction x ± k =     x1 x2 x3 x4     ±     k 1 0 1     =     x1 ± kx2 x2 x3 x4     and k ± x = ±(x ± k) Inversion x −1 =   x1x3x 2 4 α −x2x 2 3×4 α   provided that α = x 2 1x 2 4 − 2x 2 2x 2 3 6= 0 Division x  y = x ∗ y −1 Scalar

Division x  k = x ∗  1 k  =     x1 x2 x3 x4     ∗     1 k 0 1     =     x1 kx2 x3 kx4     k 6= 0, x2 6= 0, x4 6= 0 Scalar Division k  x = k ∗ x −1 Equal? x = y if x1 = y1, x2 = y2, x3 = y3, and x4 = y4 Similar? x is similar to y if x1y2 = y1x2 and x3y4 = y3x4 Norm of x x1 x2 2 + x3 x4 2 , a floating-point number measuring x Absolute value of x √ Norm of x, a floating-point number Less than? x < y is true if Norm of x < Norm of y; false, otherwise.

Implement the Quad ADT described above. Your Quad class should have the following members: 1. A container of type std::array to store a quad number 2. A constructor taking four parameters of type long long int, all four with default values. The zero quad number 0, 1, 0, 1 provides the default values. 3. Defaulted copy constructor, defaulted assignment operator, defaulted virtual destructor

## 4. Compound assignment operators.

Typically, all are implemented as member functions. quad op quad x += y, x –= y, x *= y, x /= y, quad op integer x += k, x –= k, x *= k, x /= k

## 5. Basic arithmetic operators.

Not all can be implemented as members. None modifies it operands. For consistency, all are typically implemented as free functions. quad op quad x + y , x – y, x * y, x / y, quad op integer x + k , x – k, x * k, x / k, integer op quad k + x, k – x, k * x, k / x

## 6. Relational operators.

Not all can be implemented as members. None modifies it operands. For consistency, all are typically implemented as free functions. quad op quad x < y, x <= y, x > y, x >= y, x == y, x != y quad op integer x < k, x <= k, x > k, x >= k, x == k, x != k integer op quad k < x, k <= x, k > x, k >= x, k == x, k != x

7. An overloaded XOR operator^ such that x^k returns the quad resulting from raising x to the power k (an integer). Does not modify x.

8. Unary operators ++x, x++, – –x, x– –, +x, and –x. All implemented as members.

9. Subscript operators [ ], both const and non-const versions. If subscript is invalid, must throw: invalid argument(”index out of bounds”)

10. Function call operator ( ) overload that takes no arguments and returns the absolute value, a double, of the quad number. This will effectively turn Quad objects like x into functions–hence the name “function objects.”

13. isSimilar(), inverse(), absoluteValue(), norm(), normalize(), reduce(), conjugate(), standardize(). Since these members are not as common and well known as arithmetic and relational operations, we choose to implement them as named member functions, using meaningful names that reflect their functionality, as opposed to implement them using an unintuitive and weird looking name that begins

with the word “operator” and ends with a C++ operator symbol. 4 (a) x.isSimilar(y) returns true if x is similar to y; false, otherwise (b) x.isSimilar(k) returns true if x is similar to Quad(k); false, otherwise (c) x.inverse() returns the inverse of x (d) x.absoluteValue() returns the absolute value of x, a double value (e) x.norm() returns the norm of x, a double value (f) x.normalize() normalizes x; returns void (g) x.reduce() reduces x; returns void (h) x.standardize() both reduces and normalizes x; returns void (i) x.conjugate() returns the conjugate of x

## 5 Requirements

1. Quad numbers such as x = x1, x2, x3, x4 must be normalized so that x2 and x4 are positive.

2. Quad operations can produce a quad number whose integer components are huge in magnitude, resulting in integer overflow. Therefore, to reduce possibility of integer overflow, operations that create or modify quad numbers must reduce the resulting quad numbers. 6 Basic guidelines Use the following guidelines2 to choose to either implement operators as a member function or a non-member function: Operator Recommended Implementation =, ( ), [ ], − > must be member All unary operators member Compound assignment operators member All other binary operators non-member 7 Deliverables 1. Header files: Quad.h

### 2. Implementation files:

Quad.cpp, quad test driver.cpp 3. A README.txt text file (as described in the course outline). 2Rob Murray, C++ Strategies & Tactics, Addison-Wesley, 1993, page 47. 5 8 Sample Test Driver 1 # include 2 # include 3 # include 4 # include 5 # include 6 # include ” Quad .h” 7 using std :: cout ; 8 using std :: endl ; 9 10 /* 11 Tests class Quad . Specifically , tests constructors , compound assignment 12 operator overloads , basic arithmetic operator overloads , unary + , unary -, 13 pre/post – increment / decrement , subscripts , function objects , 14 input / output operators , isSimilar , absValue , and equality relational operators .

15 16 @return 0 to indicate success . 17 */ 18 void print ( const std :: string item , const Quad & q) 19 { 20 cout << std :: left << std :: setw (20) << item << q << endl ; 21 } 22 int main () 23 { 24 // cout << ” sizeof ( long long int ) = ” << sizeof ( long long int ) << ’\n ’; 25 // cout << ” Minimum value for long long int : ” 26 // << std :: numeric_limits < long long int >:: min () << ’\n ’; 27 // cout << ” Maximum value for long long int : ” 28 // << std :: numeric_limits < long long int >:: max () << ’\n ’; 29 // Minimum value for 8-byte long long

defaluts to [2,3,0,1] 52 print (” Quad q2(2,3)”, q2); 53 assert (q2 == Quad (2, 3, 0, 1)); 54 55 Quad q3(2, 3, 4); // defaluts to [2,3,4,1] 56 print (” Quad q3(2,3,4)”, q3); 57 assert (q3 == Quad (2, 3, 4, 1)); 58 59 Quad q4(2, 3, 4, 5); // [2,3,4,5] 60 print (” Quad q4(2, 3, 4, 5)”, q4); 61 assert (q4 == Quad (2, 3, 4, 5)); 62 63 assert (q0 + one == one ); 64 assert (q0 * one == zero ); 65 assert ( one * one == one ); 66 assert ( one + one ==

assert (q22 – q11 == q23 – q22 + one ); 82 83 // additions and subtractions 84 Quad q01234 = q0 + q1 + q2 + q3 + q4; 85 print (“q01234”, q01234); 86 Quad qs01234 = -q0 – q1 – q2 – q3 – q4; 87 print (“qs01234”, qs01234); 88 assert (q01234 == -qs01234); 89 Quad m01234 = 5LL * q0 + 4LL*q1 + 3LL*q2 + 2LL * q3 + 1LL * q4; 90 print (“m01234”, m01234); 91 Quad n01234 = q0 * 5LL + q1 * 4LL + q2 * 3LL + q3 * 2LL + q4 * 1LL; 92 print (“n01234”, n01234); 93 assert (m01234 == n01234); 94 95 // mutiplications , division 96 Quad

qm1234 = q1 * q2 * q3 * q4; 97 print (“qm1234”, qm1234); 98 Quad qmr1234 = q4 * q3 * q2 * q1; 99 print (“qmr1234”, qmr1234); 100 assert (qm1234 / q4 / q1 == (q3/3LL + q3 / 3LL + q3 / 3LL) * (q2/ 2LL + q2 / 2LL)); 7 101 102 cout << setw (20) << “q4. norm () = ” << q4. norm () << endl ; 103 double size_of_q 4 = q4; // quad to double ( not double to quad ! ) 104 cout << setw (20) << ” size of q4 = ” << size_of_q 4 << endl ; 105 cout << setw (20) << ” conjugate of q4 = ” << q4. conjugate () << endl ; 106 Quad q5{ qmr 1234 }; // 107 print (” Quad q5{ qmr1234 }”, q5); 108 109 // inverse 110 Quad q5 _inverse { q5. inverse () }; 111 print (” Quad q5 _inverse “, q5 _inverse ); 112 assert (q5 _inverse * q5 == one ); 113 assert (q5 == one / q5 _inverse ); 114 assert (q5 _inverse == one / q5); 115 116 // operator [] 117 Quad q6{}; 118 q6 = 10; 119 q6 = -20; 120 q6 = 0; 121 q6 = 40; 122 print (“q6”, q6); 123 q6. normalize (); 124 print (“q6

normalized “, q6); 125 q6. reduce (); 126 print (“q6 reduced “, q6); 127 128 // operator ++ , –, both versions 129 ++q6; 130 print (“++q6”, q6); 131 q6 += half ; 132 print (“q6 += half “, q6); 133 assert (q6 == one); 134 q6++; 135 print (“q6++”, q6); 136 assert (q6 == one + one ); 137 q6 – -; 138 print (“q6 –“, q6); 139 assert (q6 == one); 140 –q6; 141 print (” –q6″, q6); 142 assert (q6 == zero ); 143 144 // operator ^ to raise a

quad to a positive integer power 145 Quad q7{ half }; 146 print (“q7”, q7); 147 q7 = half ^ 1; 148 print (“q7 = half ^ 1”, q7); 149 q7 = half ^ 2; 150 print (“q7 = half ^ 2”, q7); 151 q7 = half ^ 3; 152 print (“q7 = half ^ 3”, q7); 8 153 q7 = half ^ 4; 154 print (“q7 = half ^ 4”, q7); 155 q7 = half ^ 5; 156 print (“q7 = half ^ 5″, q7); 157 158 // operator >> 159 Quad input_quad {}; 160 cin >> input_quad ; 161 print (” input_quad “,