ALGORITHMS FROM CLASSICAL ALGEBRA* |
0. Definition
If a, b are integers, we say that a divides b, and write this symbolically as a|b, if there exists an integer q, such that b=qa.
If a, b are integers, where a>0, then there exists unique integers q and r such that,
b=qa+r where 0≤ r < a
Program: Write a function with the header,
void Division (int a, int b, int &q, int &r)
that accepts an divisor, a and dividend, b. The function determines the quotient, q, and the remainder, r. Write a main program that exercises the function for a number of well-chosen integer pairs.
The greatest common divisor of two integers a and b, GCD(a,b), not both of which are zero, is the largest positive integer that divides both a and b. The Euclidean algorithm for finding this greatest common denominator of a and b is as follows:
Divide a and b to obtain the integer quotient q and the remainder r, so that a=qr+b (if b=0, GCD(a,b)=a). Then GCD(a,b)=GCD(b,r). Replace a and b with b and r and repeat this procedure.
Because the remainders are decreasing, eventually a remainder of 0 will result. The last nonzero remainder is GCD(a,b). For example,
1260 = 198×6+72 GCD(1260,198) = GCD(198,72) 198 = 72×2+54 = GCD(72,54) 72 = 54×1+18 = GCD(54,18) 54 = 18×3+0 = 18(Note: If either a or b is negative, replace them with their absolute values in this algorithm.)
Program: Write a recursive common divisor function and a main program that exercises it for a number of well-chosen integer pairs.
There is no known efficient procedure for finding prime numbers. A classical, but tedious, method attributed to Eratosthenes (276 - 196 BC), can be described as follows. First, write down a list of integers, paired with true values,
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 T T T T T T T T T T T T T T T T T T T
Then mark all multiples of 2 by switching its true to false,
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 T T F T F T F T F T F T F T F T T T F
Move to the next unmarked number, which in this case is 3, then mark all its multiples:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 T T F T F T F F F T F T F F F T F T F
Continue in this fashion, marking all multiples of the next unmarked number until there are no new unmarked numbers. The numbers which survive this marking process (the Sieve of Eratosthenses) are primes.
Task. Write the class, Sieve, that will implement the Sieve of Eratosthenes and determine the prime numbers from 2 to n-1, where the integer n is determined by the user.
Your program will create an array of length n, initializing all cells to true. Starting with array index 2, (ignore index 0 and index 1), every time an array element is found to be true, loop through the remainder of the array and set to false every element whose index is a multiple of the starting index.
At the end of the implementation, array elements that remain true have an index which is a prime number. Display the prime numbers to the console.
ax+by=c
has a solution if and only if GCD(a,b)|c.
x= x0+(b/d)n, y=y0-(a/d)n for all integers, n.
The algorithm to determine the one particular solution, (x0,y0), of the Diophantine equation defined above is easily implemented. Consider the equation from part II above,
1260x+198y = 18
START: Write down the first two rows in the table at left below.
|
|
First step: Divide a by b using the Division algorithm, so that a=q1b+r1 where 0≤r1<b. Take the top row and subtract q1 times the next row from it.
GENERAL STEP: Continue through the Euclidean Algorithm, making use of the Division Algorithm.
STOP: Stop when rn+1=0.
Conclusions:
x=sn+sn+1n, y=tn+tn+1n, for all integer, n.
Program: Implement the Extended Euclidean Algorithm and test it with triples entered by the user from the keyboard. For example,
Input:
1260,198,18
Output:
One solution for 1260x+198y=18 is x=3 and y=-19.
Input:
28,35,60
Output:
28x+35y=60 has no solution since GCD(28,35) does not divide 60.
Input:
21,15,9
Output:
One solution for 21x+15y=9 is x=-6 and y=9.
Your program should terminate when a=0.
An early user of cryptography was Julius Cæsar. Messages sent to his troops were encrypted in a manner similar to the following. Each letter in the original message was replaced with a letter n places to the right (or left). For example, if the original message was ATTACK, and n=3, its encryption is, DWWDFN. This technique is commonly referred to as a Cæsar cipher and is very easily broken.
Program:
Write functions, void Encrypt(apstring &s, int n)
and void Decrypt(apstring &s,
int n)
that make use of the modulo operator, %, to demonstrate the Cæsar
cipher. Write a main program to exercise your functions.