Handed out: 9/17/07
This assignment has two parts, involving two separate programs. The first part is an exercise in getting user input and in procedures. The second part involves loops.
The Towers of Hanoi puzzle has three posts and some number n of disks. Each disk has a hole in the middle, so that it can be put on a post, and the disks are of different sizes.
Initially, the disks are all stacked on the leftmost post, with larger disks closer to the bottom and smaller disks closer to the top. For example, if there are three disks, the puzzle starts out looking like this.
The object is move all of the disks from the leftmost post to the rightmost post. So when the puzzle is solved, it looks like this.
But there are some rules that must be followed.
Only one disk can be held in your hand at a time. The other disks must be on posts.
A disk can only be put down by placing it on one of the posts. For example, you can't put a disk on the table beside the puzzle.
No disk can ever be put on top of a smaller disk.
It is convenient to refer to the posts by names, such as A, B and C. Instructions to move three disks from A to C are as follows. (You always move the disk that is on the top of the stack.)
Move a disk from A to C. Move a disk from A to B. Move a disk from C to B. Move a disk from A to C. Move a disk from B to A. Move a disk from B to C. Move a disk from A to C.
Write a Cinnameg program that prints instructions for solving the Towers of Hanoi puzzle. It should allow the user to decide how many disks there are, and what to call the three posts. So your program should read four things from the user:
1. Move disk 1 from L to R. 2. Move disk 2 from L to M. 3. Move disk 1 from R to M. 4. Move disk 3 from L to R. 5. Move disk 1 from M to L. 6. Move disk 2 from M to R. 7. Move disk 1 from L to R.
The following defines a procedure, Hanoi, that prints a solution without numbering the moves or the disks. (It uses a semicolon to cascade several displays together, to reduce the number of lines.) Modify it so that it numbers the moves and the disks. Also be sure to modify the contract, so that it will be correct for the modified version of the function.
%%==================================================================
%% Hanoi(n, source, dest, other) prints instructions for moving
%% n disks from post source to post dest, using post other for
%% storage, according to the rules for the Towers of Hanoi puzzle.
%%==================================================================
Define Hanoi(n: Integer, source: Char, dest: Char, other: Char). =
If n > 0 then
Hanoi(n-1, source, other, dest).
Display "Move a disk from "; source; " to "; dest; ".".
Displayln.
Hanoi(n-1, other, dest, source).
%If
%Define
To number the disks, notice that the Displayln line in the middle is moving the bottom disk, which is disk n.
To number the moves, it is convenient to use an elementary kind of object called a box. A box is like a variable, but it is a thing that you can pass to a procedure. Line
Let b = sharedBox(1).creates a new box that initially holds 1, and calls it b. Line
Make b := 2.removes the 1 from box b and replaces it by 2. Expression !b yields the current value held in box b. So, for example,
Make b := !b + 1.makes b hold one larger than it held before.
To number the moves, add another parameter to Hanoi that is a box. When Hanoi starts, that box will hold the number to use for the first move. When Hanio ends, that box should have been changed to hold the number just after the last move that Hanoi printed. For example, if box b currently holds 12, then statement
Hanoi(3, 'L', 'R', 'M', b)should print
12. Move disk 1 from L to R. 13. Move disk 2 from L to M. 14. Move disk 1 from R to M. 15. Move disk 3 from L to R. 16. Move disk 1 from M to L. 17. Move disk 2 from M to R. 18. Move disk 1 from L to R.and end with box b holding 19. All you need to do is be sure to add 1 to what is in the box every time you print an instruction.
To read an integer, use readInteger(). To read a character, use readNonblankChar(). (It will skip over blanks.) Import "collect/string" to use those.
Write this program using successive refinement.
Start by writing a program that reads the number of disks and the disk names, and then prints the moves without numbering either the moves or the disks. Test it. Do not move on until this works.
Modify the program so that it numbers the disks. Test it.
Modify the program so that it numbers the moves. Test it. If there are mistakes, fix them.
An algorithm is a clearly spelled out way of solving a problem. For example, Euclid's algorithm, which we discussed in class, is one way to find the greatest common divisor of two integers. Some algorithms are relatively simple and clear, while some others (such as Euclid's) are more subtle. Some algorithms are so clever that their discoverers write about them in papers, and they become part of a tool box of known algorithms. This part describes a very clever algorithm that was discovered in the 1970s.
A positive integer n is prime if n > 1 and the only divisors of n are 1 and n. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19.
For cryptographic applications, such as sending secure email over the internet, some programs need to have very large prime numbers. For security, a program should never get a prime number from a table or any other public source. It needs to find its own. Typically, prime numbers with 100 or more decimal digits are used.
An obvious way to tell whether a number n is prime is to try all numbers from 2 to n-1, to see whether any of them are factors of n. But that can be very expensive if n is a really large number. For a 100 digit number, that algorithm will not finish within the lifetime of the computer. You can improve the algorithm by realizing that, if n has a factor, then at least one of those factors is no larger than the square root of n. So you only need to look at 2, 3, ..., s, where s is the square root of n, before you can conclude that n is prime. Unfortunately, if n is a 100 digit number, that still takes more time than the lifetime of the computer!
Some algorithms work by trying to find witnesses to facts. A witness is some information that can be used to justify a fact. For example, you can show that a number is not prime by finding a factor of it. Since 3 is a factor of 15, you could say that 3 is a witness, in this sense, that 15 is not prime. Similarly, 11 is a witness that 143 is not prime, since 11 is a factor of 143.
A witness testifies to a fact, by providing evidence for it. The way it testifies is by passing some kind of test, or cross examination. There are different kinds of witnesses, depending on the kind of test that they have to pass. For example, you can say that an integer k is a factor-witness that n is not prime provided the test
k > 1 and k < n and k is a factor of nis true. So 11 is a factor-witness to the fact that 143 is not prime because
11 > 1 and 11 < 143 and 11 is a factor of 143
Finding just one factor-witness is enough to convince you that a number is not prime. The obvious algorithm outlined above works by trying to find a factor-witness. It looks at 2, 3, 4, 5, ..., n-1, checking each one to see whether it is a factor-witness. Think of the algorithm as similar to a policeman searching door-to-door trying to find a witness to a crime.
Unfortunately, factors are a difficult kind of witness to find because there are so many candidates that might be witnesses, but so few of them are actually witnesses. For an efficient algorithm, we need a more abundant kind of witness, one so abundant that it no longer necessary to search door-to-door, but instead we can do something more like an opinion poll, were we just look at a small sample of the candidates. It turns out that abundant witnesses do exist, but you need to use a different way of having a witness testify. A witness is no longer a factor.
| Definition of a Fermat-witness |
|---|
|
Suppose that n is an integer where n > 1.
Say that a positive integer w is a
Fermat-witness to the fact that
n is not
prime if (0 < w < n) and
(wn-1 mod n =/= 1).
For example, 3 is a Fermat-witness that 4 is not prime since 33 mod 4 = 27 mod 4 = 3 (not 1). Similarly, 2 is a Fermat-witness that 9 is not prime, since 28 mod 9 = 256 mod 9 = 4 (not 1). (Pierre Fermat (1601-1665) was a French lawyer and government official whose hobby was the mathematics of integers. He proved a key result that is the basis for why Fermat-witnesses work. Fermat is is pronounced fair-mah. See Colbert, S.) |
Here are some useful facts about Fermat-witnesses.
If p is a prime number, then there do not exist any Fermat-witnesses that show p is not prime. That is, wp-1 mod p = 1 for all w where 0 < w < p. So Fermat-witnesses cannot lie. This is the fact that Pierre Fermat proved.
If n is not prime, and n is not one of a collection of rare numbers called Carmichael numbers, then at least half of the numbers w between 1 and n-1 are Fermat-witnesses that n is not prime. So Fermat-witnesses are abundant. This fact was noticed in the 1970s.
So, to tell whether n is prime, the idea is to guess a random number w between 1 and n-1, and to check whether w is a Fermat-witness that n is not prime. If it is, then you know for sure that n is not prime, since Fermat-witnesses cannot lie, so you can give an answer immediately.
If your random number w is not a Fermat-witness, then you can try another random number, and see whether that is a Fermat-witness. You keep trying to find a Fermat-witness until you have tried about 20 candidates. Since Fermat-witnesses are abundant, if you try 20 random numbers and none are Fermat-witnesses, it is very likely that no Fermat-witnesses exist. In that case, you claim that n is (probably) prime.
Your program should read an integer n from the user, and it should print the smallest prime integer that is greater than or equal to n. That is, it should start at n and count up until it reaches a prime integer, printing that prime integer. It should work for very large integers. You are required to write the fast algorithm yourself. Do not use the library function prime? for this.
You can use the following functions. Just copy them, with their contracts, into the program. Important. Do not try to compute np mod m using expression n^p `mod` m. If you do, your program will not finish within the lifetime of the computer. Use powermod, which gives the same answer, but is much more efficient.
%%=============================================
%% powermod(n,p,m) yields np mod m.
%% Requirements: n, p and m are integers where
%% n =/= 0,
%% p >= 0,
%% m >= 0.
%%=============================================
Define
case powermod(?, 0, ?) = 1
case powermod(n, p, m) = n*powermod(n, p-1, m) `mod` m when odd?(p)
= powermod(n, p `div` 2, m)^2 `mod` m %% otherwise
%Define
Example powermod(4, 5, 100) = 24.
%%==================================================================
%% randomCandidate(n) yields a randomly chosen number from 1 to n-1.
%%==================================================================
Import "misc/random".
Define randomCandidate(n) = random(n-1) + 1.
Write the following functions. (You are required to write these, even if you would prefer not to write function definitions.)
isFermatWitness(w, n) should yield a result of type Boolean: true if w is a Fermat-witness that n is not prime, false if w is not a Fermat-witness for n. Use the powermod method.
isProbablyPrime(n) should yield true if n is (probably) prime, and false if n is (surely) not prime. This method is required to use the clever algorithm outlined above, using Fermat-witnesses. It should select up to 20 candidates, and test each to see whether it is a witness.
Use a loop to go through the candidates.
Write a function nextPrime(n) that returns the smallest prime number that is greater than or equal to n. Use either a loop or recursion.
Write an execute block that reads an integer n from the user and prints the next (probably) prime number.
Be sure to test your program. Do not just presume that it works. (The next prime number starting at 1234567890123 is 1234567890133.)
Print both of your programs and turn them in. Be sure that your name is at the top of each, as a comment in the program. Label them Part 1 and Part 2.
The algorithm that you have implemented is very close to the one that is used in cryptographic applications for finding large prime numbers. The actual algorithm for testing whether a number is prime contains a patch that detects Carmichael numbers. Those numbers are so rare, however, that the patch is almost never needed in practice.
An integer is not prime if there exists a factor for it (other than itself and 1). So you might expect that any algorithm that tells you that a number is not prime should do so by finding a factor of that number. But the algorithm that you have implemented can determine that a number is not prime without finding a factor. Somehow, it knows that a factor must exist without being able to find one.
It is generally believed that the problem of finding a factor of a number is much more difficult than just deciding whether a factor exists. Some things leave telltale signs, so you know they are there, but they are difficult to track down.
There are lots of interesting and surprising algorithms waiting to be discovered. Just a few years ago a new algorithm was discovered for testing whether a number is prime without using any random numbers. The most surprising thing to most researchers was not that such an algorithm existed, but how short and simple it turned out to be. It can be written in about half a page.