Literate Programming
Yüklə 257,24 Kb. Pdf görüntüsü
|
LITERATE PROGRAMMING 15.
The repeat loop in the previous section intro- duces a boolean variable j prime , so that it will not be necessary to resort to a goto statement. (We are following Dijkstra, 2 not Knuth. 3 ) Variables of the program 4 +≡ j prime : boolean ; { is j a prime number? } 16. In order to make the odd-even trick work, we must of course initialize the variables j, k, and p[1] as follows.
Initialize the data structures 16 ≡ j ← 1; k ← 1; p[1] ← 2; See also section 18. This code is used in section 11. 17.
Now we can apply more number theory in order to obtain further economies. If j is not prime, its smallest prime factor p n will be
√ j or less. Thus if we know a number ord such that p[ord ]
2 > j,
and if j is odd, we need only test for divisors in the set {p[2], . . . , p[ord − 1]}. This is much faster than testing divisibility by {p[2], . . . , p[k]}, since ord tends to be much smaller than k. (Indeed, when k is large, the celebrated “prime number theorem” implies that the value of ord will be approximately 2 k/ln k.) Let us therefore introduce ord into the data struc- ture. A moment’s thought makes it clear that ord changes in a simple way when j increases, and that an- other variable square facilitates the updating process. Variables of the program 4 +≡ ord : 2 . . ord max ; { the smallest index ≥ 2 such that p 2 ord
> j } square : integer ; { square = p 2 ord
} 18.
Initialize the data structures 16 +≡ ord ← 2; square ← 9; 19.
The value of ord will never get larger than a cer- tain value ord max , which must be chosen sufficiently large. It turns out that ord never exceeds 30 when m = 1000. Other constants of the program 5 +≡ ord max = 30; { p 2 ord max must exceed p m } 20. When j has been increased by 2, we must increase ord by unity when j = p 2 ord , i.e., when j = square . Update variables that depend on j 20 ≡
begin ord ← ord + 1; Update variables that depend on ord 21 ;
This code is used in section 14. 21.
At this point in the program, ord has just been increased by unity, and we want to set square := p 2 ord
. A surprisingly subtle point arises here: How do we know that p ord
has already been computed, i.e., that ord ≤ k? If there were a gap in the sequence of prime numbers, such that p k+1
> p 2 k for some k, then this part of the program would refer to the yet-uncomputed value p[k + 1] unless some special test were made. Fortunately, there are no such gaps. But no sim- ple proof of this fact is known. For example, Euclid’s famous demonstration that there are infinitely many prime numbers is strong enough to prove only that p k+1 <= p 1 . . . p k + 1. Advanced books on number theory come to our rescue by showing that much more is true; for example, “Bertrand’s postulate” states that p k+1
< 2p k for all k. Update variables that depend on ord 21 ≡ square ← p[ord ] ∗ p[ord ]; { at this point ord ≤ k } See also section 25. This code is used in section 20. 22.
The inner loop. Our remaining task is to de- termine whether or not a given integer j is prime. The general outline of this part of the program is quite sim- ple, using the value of ord as described above. Give to j prime the meaning: j is a prime number 22
n ← 2; j prime ← true ; while (n < ord ) ∧ j prime do begin If p[n] is a factor of j, set j prime ← false 26 ;
end This code is used in section 14. 23. Variables of the program 4 +≡ n: 2 . . ord max ; { runs from 2 to ord when testing divisibility } 24.
Let’s suppose that division is very slow or nonex- istent on our machine. We want to detect nonprime odd numbers, which are odd multiples of the set of primes {p 2 , . . . , p ord
}. Since ord max is small, it is reasonable to maintain an auxiliary table of the smallest odd multiples that haven’t already been used to show that some j is non- prime. In other words, our goal is to “knock out” all of the odd multiples of each p n in the set {p 2 , . . . , p ord },
that serves as a control structure for a set of knock-out procedures that are being simulated in parallel. (The so-called “sieve of Eratosthenes” generates primes by a similar method, but it knocks out the multiples of each prime serially.) The auxiliary table suggested by these considerations is a mult array that satisfies the following invariant condition: For 2 ≤ n < ord , mult [n] is an odd multiple of p n
n . Variables of the program 4 +≡ mult : array [2 . . ord max ] of integer ; { runs through multiples of primes } 25.
When ord has been increased, we need to ini- tialize a new element of the mult array. At this point j = p[ord − 1] 2 , so there is no need for an elaborate computation. Update variables that depend on ord 21 +≡
26. The remaining task is straightforward, given the data structures already prepared. Let us recapitulate the current situation: The goal is to test whether or not j is divisible by p n , without actually performing a division. We know that j is odd, and that mult [n] submitted to THE COMPUTER JOURNAL 5 Yüklə 257,24 Kb. Dostları ilə paylaş:
|