C++ For Mathematicians (2006) [eng]

166	C++ for Mathematicians

is too simplistic; it fails to handle improper values for m such as zero or negative integers.)

The better solution is to declare these methods as static methods; see lines 63–75 of Mod.h, Program 9.1.

static void set_default_modulus(long m) { if (m <= 0) {

default_modulus = INITIAL_DEFAULT_MODULUS;

}

else { default_modulus = m;

}

}

static long get_default_modulus() { if (default_modulus <= 0)

set_default_modulus(INITIAL_DEFAULT_MODULUS); return default_modulus;

The modifier static for a method means that this method is not associated with an object of the given class, but with the class as a whole. So, for example, it would not make sense for either of these procedures to access the member variables val or mod because they are object specific.

Use of these methods requires a special syntax. Remember that these methods are members of the Mod class, but are not tied to any particular object. If we want to use these methods inside another Mod method, we can just use their name (either get_default_modulus or set_default_modulus). However, in a procedure such as main() another syntax is required. To use a static method from the class Mod in a procedure, we need to prepend Mod:: to the name of the procedure. Here is an example:

Mod::set_default_modulus(10);

cout << "The default modulus is now "

<< Mod::get_default_modulus() << endl;

We have seen three usages of the keyword static. Its meaning depends on the context in which it is used.

•A procedure’s variable may be declared static. This means that the value held in the variable is preserved between invocations of the procedure.

•A variable in a class declaration may be declared static. This means that this variable is common to all objects of that type.

•A class method may be declared static. This means that this method is not to be associated with any particular object of the class, but with the class as a whole. Consequently, it cannot access any nonstatic member variables of the class.

Modular Arithmetic

167

9.4Constructors and get/set methods

The Mod class has three constructors. A default constructor that takes no arguments, a one-argument constructor that uses the default modulus, and a twoargument constructor that specifies both value and modulus. The code for three constructors is written inline on lines 19–40 of Mod.h (Program 9.1).

The constructors must ensure that the modulus is positive (or else the resulting object is invalid). When the modulus is provided by the default modulus, we can be assured that the modulus is nonnegative. However, in the two-argument case, we need to check that the modulus specified is positive. If not, we create an invalid Mod object.

The constructors also need to ensure that the value is in the proper range. For example, the user may call Mod(-1,10). In this case, we should create 9 Z10. This need to adjust the value so that it lies in the proper range is a recurring issue, so we create a private method to adjust val so that it lies between 0 and mod-1. The adjust_val() method is given inline on lines 13–15 of Mod.h (Program 9.1).

Because the val and mod member variables are private, we need methods to inspect and to modify these. To that end, we specify the inline methods get_val, set_val, get_mod, and set_mod on lines 42–61 of Mod.h (Program 9.1). The get methods are flagged as const because they do not modify the Mod object. The set methods are designed to modify objects. These are designed so that the modulus is nonnegative and the value lies in the proper range.

We allow mod to equal zero to signal an invalid Mod object. We provide a handy is_invalid method (line 77) to check if this is the case.

9.5Comparison operators

Given Mod objects x and y, we want to be able to check whether they are equal, and to sort them with <. We define the following relational operators:

x == y

x != y

x < y

The == operator is defined inline on lines 79–80 and the != operator on lines 91–93 of Mod.h (Program 9.1).

The < operator sorts Mod objects first on the basis of the modulus, and then on the basis of the value. See lines 95–100 of Mod.h.

In addition to comparing Mod objects to other Mod objects, it is convenient to be able to compare a Mod object to a long integer. For example, consider this code:

168	C++ for Mathematicians

Mod x(9,10);

if (x == -1) cout << "It worked!" << endl;

In this case, we want the −1 interpreted as an element of Z10 and then the comparison ought to evaluate to true.

In C++, we need to define the operators Mod == long and long == Mod separately. The first of these is given on lines 83–85; we repeat that code here.

bool operator==(long that) const { return (*this) == Mod(that,mod);

}

The method is type bool because it returns a true/false result. The single argument is of type long because it is the right-hand argument; the left-hand argument is the Mod object. That is, in the statement x == -1 (where x is a Mod), the left argument is (implicitly) x and the right argument (that) equals −1.

The procedure works by converting that into a Mod object with the same modulus as the invoking object: Mod(that,mod). Then it uses the already defined Mod==Mod operator to compare. In order for an object to use itself we use *this. Therefore, when we encounter x == -1, the expression

(*this) == Mod(that,mod)

compares x (embodied by *this) with Mod(that,mod) where mod is the modulus of x.

Now we need to write a procedure for expressions of the form long == Mod. This cannot be written as a method inside the Mod class because the left-hand argument is not of type Mod. We therefore need to define this as a procedure outside the curly braces enclosing the Mod class declaration.

The code for long == Mod is on lines 178–180 of Mod.h (Program 9.1) and we repeat that code here.

inline bool operator==(long x, const Mod& y) { return (y==x);

}

The keyword inline is mandatory here (it is optional for inline methods inside the class declaration). Again, the procedure is of type bool as it returns a true/false value. This version of operator== has two arguments; because this is not a method belonging to a class, but rather a free-standing procedure, we need to specify the left and right arguments of == explicitly. The left argument is of type long and the right is of type Mod. The easiest way to see if x==y is true (where x is a long and y is a Mod) is to take advantage of the fact that we already have Mod==long defined; we just invoke y==x.

All three manifestations of != (Mod!=Mod, Mod!=long, and long!=Mod) are defined in the same manner.

Modular Arithmetic

169

9.6Arithmetic operators

Now we implement the various arithmetic operations for Zn: addition, subtraction, multiplication, division, and exponentiation.

We begin with addition. Of course, we want to define the + operator when both arguments are type Mod. To do that, we create an operator+ method in the Mod class. In addition, it is useful to define Mod+long and long+Mod operations. We also want the add/assign operation x += y where x is a Mod and y is either Mod or long.

All of these various forms of addition require the same basic underlying operations, we define an add method first and all the various + operations can use that to do the work. The add method of the Mod class is declared on line 102 of Mod.h (Program 9.1) as follows: Mod add(Mod that) const;. The actual code is found on lines 16–20 of Mod.cc (Program 9.2):

Mod Mod::add(Mod that) const {

if (is_invalid() || that.is_invalid()) return Mod(0,0); if (mod != that.mod) return Mod(0,0);

return Mod(val + that.val, mod);

}

Notice that we first check if either the invoking Mod object or the argument that is invalid; if so, we return an invalid Mod object. Also, if the moduli of the two addends are different, we return an invalid Mod object. Finally, we add the values of the two objects and return a new Mod object containing the sum.

With the add method in place, we define the various + operators. The Mod+Mod method is on line 104 of Mod.cc and the Mod+long is on line 106. The long+Mod procedure cannot be a member of the Mod class (because the Mod is not on the left), so it is defined as a procedure on lines 186–188 of Mod.h. In each case, the Mod object passed is declared const Mod& because addition does not modify the addends (hence const) and call by reference is required for operators.

Next we define the += operators. The Mod+=Mod operator’s definition (lines 108– 111 of Mod.h) is repeated here:

Mod operator+=(const Mod& x) { *this = add(x);

return *this;

}

Recall that the effect of the statement a+=x; is tantamount to a=a+x;. C++ allows us to program the += operator to do anything we want, but it makes most sense to adhere to the intended meaning.

The statement a=a+x; has the effect of replacing the value held in a with the result of the computation a+x. The result of a+=x; is the new value of a. Thus, a compound statement of the form z=a+=x; is interpreted as z = (a+=x) and is equivalent to a=a+x; z=a;. The procedure we write for Mod+=Mod should adhere to this behavior.

170	C++ for Mathematicians

Thus, the operator+= method returns a Mod value. The argument, x, is declared as const Mod& x because (a) the code does not modify x’s value and (b) pass by reference is required for operator+=.

To add x to the invoking object we appeal to the add method already defined. The statement *this = add(x); does the required work. The invoking object calculates the sum of its own value and that of x, and then assigns that value to itself.

Finally, we need to return the value in the invoking object as the result of this method. This is accomplished with the statement return *this;.

Next we examine the subtraction methods. Because a−b is equivalent to a+(−b), we begin by defining the unary minus (i.e., negate) operator. The unary operator -a is a zero-argument method in the class Mod. The reason we do not need any arguments is because the operator applies to the invoking object. The full definition of unary minus is given inline in Mod.h on line 118 (Program 9.1) and repeated here:

Mod operator-() const { return Mod(-val,mod); }

Now the binary minus can be built using unary minus and addition. The Mod-Mod and Mod-long operations are implemented as methods within the class Mod (see lines 120–126). The long-Mod operator cannot be a member of the Mod class (because the left-hand argument is not a Mod), and so it needs to be a stand-alone procedure outside the class definition. See lines 190–192 of Mod.h. Finally, the Mod-=Mod and Mod-=long methods are given on lines 128–136.

The multiplication operators are created in a manner similar to that of addition. We declare a multiply method on line 138 of Mod.h and then give the code in Mod.cc on lines 22–26. The Mod*Mod, Mod*long, Mod*=Mod, and Mod*=long operators are inline members of the Mod class (lines 140–152 of Mod.h, and long*Mod is an ordinary inline procedure outside the class definition (lines 194–196).

We reduce division a ÷b to multiplication by a reciprocal; that is, a ×b−1. Therefore, we begin by building an inverse method for the Mod class. This method is declared on line 154 of Mod.h as follows: Mod inverse() const;. Invoking b.inverse() should return the multiplicative inverse of b (in the appropriate Zn) if possible; otherwise (i.e., b is not invertible) we return an invalid result. This is implemented in Mod.cc on lines 28–36; we repeat the code here:

Mod Mod::inverse() const { long d,a,b;

if (is_invalid()) return Mod(0,0);

d = gcd(val, mod, a, b);

if (d>1) return Mod(0,0); // no reciprocal if gcd(v,x)!= 1 return Mod(a,mod);

}

The code first checks if the invoking Mod object is valid; if not, no inverse is possible and we return an invalid result. We then invoke the extended gcd procedure to find

Modular Arithmetic

171

integers a and b so that a*val+b*mod equals d=gcd(val,mod). If d equals 1, then a holds the value of the inverse.

With the inverse method established, we use it to define Mod/Mod, Mod/long, long/Mod, Mod/=Mod, and Mod/=long.

There are a large number of arithmetic operators, but they all trace their actions back to four methods: add, multiply, unary minus, and inverse. There is an interesting benefit to this approach. Suppose we think of a better way to perform these operations; rather than needing to rewrite myriad operator methods, we just need to update these few to implement the new methods. For example, on a computer for which a long is four bytes, the largest integer value is around two billion. If we are working in a modulus near that limit and we multiply two Mod objects, the intermediate result may overflow the long data type. See line 25 of Mod.cc in which we calculate val * that.val. If val and that.val are both greater than, say, 105, then the multiply procedure gives an incorrect result. To fix this problem, we could rewrite the procedure to save val and that.val in long long variables, and then perform the multiplication. We would then reduce modulo mod which brings the values back to within the proper range.

The final operation we implement is exponentiation. Given a Zn and k Z, we want to calculate ak. If k is negative, we raise a−1 to a positive power. Rather than multiply a by itself repeatedly, it is more efficient to use repeated squaring. Note that

ak =	ak(k2	1)/2		2		if k is even, and
	/		2
				·
					a	if k is odd.
	a −

So, calculating ak by this strategy uses O(log2 k) multiplications and not the far greater k −1 required by the naive method.

We call the method pow and it is declared on line 172 of Mod.h and the code is on lines 38–61 of Mod.cc.

We elected not to define any operator symbol to represent exponentiation. Two natural operator symbols would make sense: ** and ˆ. Unfortunately, there are problems with both. The first is simply illegal. Because C++ does not have a ** operator for its fundamental types, we are not permitted to use ** as an operator symbol for any other types.

The latter, ˆ, is permissible because ˆ is a valid C++ operator (exclusive or). Within the Mod class we may define this operator such as this:

Mod operatorˆ(long k) { return pow(k); }

Then, in a procedure (such as main) we could have statements such as a = bˆ5; in lieu of a = b.pow(5);.

The problem is C++’s order of operation rules. C++ knows that multiplication takes priority over addition. An expression such as a*b+c*d is parsed as expected: (a*b)+(c*d). However, in the C++ hierarchy of operations, ˆ has lower priority

172	C++ for Mathematicians

than addition. Thus a statement of the form a+bˆ2 would be parsed as (a+b)ˆ2. If we defined ˆ for the Mod class, we would need to be careful to add unnatural parentheses in our expressions. Fortunately, the . in a.pow(k) has priority over addition and multiplication. So the expressions a+b*c.pow(k) and a+c.pow(k) have the desired behavior. There is no way to change C++’s order of operation rules, so we elect not to use operatorˆ for exponentiation.

9.7Writing Mod objects to output streams

One last task awaits us: writing Mod objects to an output stream such as cout. The technique for doing this is the same as for Point and PTriple objects. In Mod.h (line 176) we declare operator<< as a two-argument procedure:

ostream& operator<<(ostream& os, const Mod& M);

Then, in Mod.cc (lines 6–14) we give the code. If the Mod object is invalid, we write the characters INVALID. Otherwise, we write a Mod object in a form such as this:

Mod(31,100).

9.8A main to demonstrate the Mod class

We end this chapter with a simple main to demonstrate the use of the Mod class.

Program 9.3: A program to illustrate the use of the Mod class.

1#include "Mod.h"

2

3/// A main to test the Mod class

4

5 int main() {

6Mod x,y,z;

7

8x.set_default_modulus(11);

9

10x = Mod(17,10);

11y = Mod(24);

12z = -3;

13

14cout << "x = " << x << endl;

15cout << "y = " << y << endl;

16cout << "z = " << z << endl << endl;

17

18cout << "y+z = " << y+z << endl;

19cout << "y-z = " << y-z << endl;

Modular Arithmetic

173

20cout << "y*z = " << y*z << endl;

21cout << "y/z = " << y/z << endl << endl;

22

23cout << "x+3 = " << x+3 << endl;

24cout << "x-3 = " << x-3 << endl;

25cout << "x*3 = " << x*3 << endl;

26cout << "x/3 = " << x/3 << endl << endl;

27

28cout << "4+x = " << 4+x << endl;

29cout << "4-x = " << 4-x << endl;

30cout << "4*x = " << 4*x << endl;

31cout << "4/x = " << 4/x << endl << endl;

32

33 cout << "-x = " << -x << endl << endl;

34

35cout << "xˆ9 = " << x.pow(9) << endl;

36cout << "xˆ(-9) = " << x.pow(-9) << endl;

37

38cout << "-1+yˆ10 = " << -1+y.pow(10) << endl;

39cout << "yˆ2 = " << y.pow(2) << endl;

40cout << "yˆ(-2)+1 = " << y.pow(-2)+1 << endl << endl;

41

42cout << "x == 17\t" << (x == 17) << endl;

43cout << "x != 17\t" << (x != 17) << endl;

44

45cout << "17 == x\t" << (17 == x) << endl;

46cout << "17 != x\t" << (17 != x) << endl << endl;

47
48	return 0;
49	}

Here is the output of this program.
	x = Mod(7,10)
	y = Mod(2,11)
	z = Mod(8,11)
	y+z = Mod(10,11)
	y-z = Mod(5,11)
	y*z = Mod(5,11)
	y/z = Mod(3,11)
	x+3	= Mod(0,10)
	x-3 = Mod(4,10)
	x*3 = Mod(1,10)
	x/3 = Mod(9,10)
	4+x = Mod(1,10)
	4-x = Mod(7,10)
	4*x = Mod(8,10)
	4/x = Mod(2,10)
	-x = Mod(3,10)
	xˆ9 = Mod(7,10)
	xˆ(-9) = Mod(3,10)

174						C++ for Mathematicians
		-1+yˆ10			= Mod(0,11)
		yˆ2		= Mod(4,11)
		yˆ(-2)+1 = Mod(4,11)
		x ==		17	1
		x !=		17	0
	17		== x		1
	17		!= x		0

9.9Exercises

9.1Write a procedure to solve a pair of congruences of the form x ≡ a (mod m)

x ≡ b (mod n)

where m and n are relatively prime. The existence and uniqueness (in Zmn) of the solution to such a problem is guaranteed by the Chinese Remainder Theorem. Therefore, call your procedure crt. It should take two Mod objects as arguments and produce a Mod value in return. Your procedure should be declared like this:

Mod crt(const Mod a, const Mod b);

Of course, you may use the procedure you developed in Exercise 5.4.

9.2Create a class to represent the time of day. Call your class Time and give it the following attributes.

•The data should be held in three private variables representing the hour, minute, and second.

•The default (no-argument) constructor should create a value equal to midnight and a three-argument constructor should create the time specified (using hours from 0 to 23).

•Define addition of a Time object and a (long) integer. If T is type Time and n is type long, then T+n and n+T should be the time n seconds after T. (Of course, n might be negative.)

•Define subtraction, but only in the form T-n but not n-T.

•Define ++ and --; these should increase (decrease) T by one second, respectively.

•Define get_hour(), get_minute(), and get_second() methods.

Modular Arithmetic

175

•Define ampm() and military() methods to control how the time is printed (see the next bullet). These methods should affect how all Time objects are printed.

Also provide a is_ampm() method that returns true if the current output style is to use AM/PM and false if the current style is military (24 hour).

•Define << for printing Time objects to the screen. The style of the output should either be 5:03:24 pm or 17:03:24 as specified by the user with the methods ampm() and military(), respectively.

Note the zero in front of the 3 but not in front of the 5. Midnight should be reported either as 12:00:00 am or 0:00:00 and noon as

12:00:00 pm or 12:00:00, as appropriate.

If you are feeling especially brave, you can create a procedure called now that returns the current time of day. You can use time(0); this returns the number of seconds since midnight on a specific date but not necessarily in your time zone (unless your local clock is GMT).

9.3Create a class named EuclideanVector to represent vectors in a Euclidean space Rn, and give it the following attributes.

•There should be a default dimension (as a static class variable). Give static methods for inspecting and adjusting this default dimension.

•There should be a zero-argument constructor that gives the zero vector in

the default dimension. There should also be a single-argument constructor EuclideanVector(int n) that creates the zero vector in Rn.

•There should be methods to get and set the individual coordinates of the vector.

•There should be a method to learn the dimension of the vector.

•There should be an operator+ for adding vectors. Decide what the behavior should be in case the two vectors are of different dimension.

•There should be an operator* method for scalar multiplication. Be sure to allow both scalar–vector and vector–scalar multiplication.

•There should be an operator== and an operator!= for comparing vectors for equality.

•There should be an operator<< for writing vectors to the computer screen.

9.4Let S denote the set {√n : n Z,n ≥ 0}. Define an operation on S by x y =

p

x2 + y2. Create a C++ class to represent elements of the set S that includes an operator* that implements S’s operation.

Include methods to get the value n, to convert an element of S into a decimal approximation, and an operator<< to write elements of S to the screen.