程序代写代做代考 scheme Example: Testing Primality

Example: Testing Primality

Recall that a (whole, positive) number n is composite if it has a divisor other than 1 and n. Otherwise, it is prime.*
What is a natural way to determine if a number p is composite? Test to see if it has a divisor d, 1 < d < n. Note: It’s not obvious how to define (composite p) in terms of (composite k) for smaller k: we will need to introduce some other functions to help structure Thus, n is composite if: Some number between 2 and n-1 divides it evenly. ✤ ✤ Idea: Let’s say that a number is k-smooth if it has a divisor d so that 1 < d ≤ k. Thus, n is composite if: It is (n-1)-smooth. 103 A recursive expansion of... being smooth Note that n is k-smooth if k divides n or it is (k-1)-smooth. Why? (define (divides a b) (= (modulo b a) 0)) (define (smooth n k) (and (>= k 2)
(or (divides k n)
(smooth n (- k 1)))))
(define (composite n) (smooth n (- n 1)))
Note: This uses short-circuited evaluation of AND and OR. How?

Thus:

104

Without short-circuit ?
(define (divides a b) (= (modulo b a) 0))
(define (smooth n k)
(if (< k 2) #f (if (divides k n) #t (smooth n (- k 1))))) (define (composite n) (smooth n (- n 1))) 105 You can optimize this... With one possible exception, divisors come in pairs. If n has a divisor d for which 1 < d < n, then it has one that is no more than n/2. that is no more than sqrt(n). ✤ ✤ ✤ Why? Suppose that d * d’ = n. If both d and d’ were larger than sqrt(n), their product would be larger than n! ✤ Thus: rounds down ✤ (define (composite n) (smooth n (floor (sqrt n))) 106 Example: Testing primality As a number is prime when it is not composite, (define (divides a b) (= (modulo b a) 0)) (define (smooth n k) (and (>= k 2)
(or (divides k n)
(smooth? n (- k 1)))))
(define (prime p)
(not (smooth p (floor (sqrt p)))))


Note: (smooth k) returns #t if there is a divisor of n between 2 and k.

We can hide the definitions of divides and smooth…
107

Nesting the environments…
As divides and smooth are only used inside prime:
(define (prime n)
(define (divides a b) (= (modulo b a) 0))
(define (smooth k)
(and (>= k 2)
(or (divides k n)
(smooth (- k 1)))))
(not (smooth (floor (sqrt n)))))


INTERESTING SIMPLIFICATION: (smooth k) no longer needs to be passed n, it exists in the defining environment!

Let’s trace the environments…
108

The inner environment during a call to (prime 6)
If we make the invocation:
(prime 6)
the body is evaluated in an environment where n: 6.
(define (divides a b) (= (modulo b a) 0))
(define (smooth k)
(and (>= k 2)
(or (divides k n)
(smooth (- k 1)))))
(not (smooth (floor (sqrt n)))))
Thus, smooth is defined in an environment where n = 6.
Notice that divides is always called with b = n. Further simplification…109

One further simplification of the primality tester
(define (prime n)
(define (divisor a) (= (modulo n a) 0))
(define (smooth k)
(and (>= k 2)
(or (divisor k)
(smooth (- k 1)))))
(not (smooth (floor (sqrt n)))))
divides was always called with b = n.
110

Reading
With some adaptations and omissions, the previous slides cover material from Section 1.2 of SICP.
✤ You might find it interesting to look over the Revised5 Report on Scheme, a definition of the language. (Posted on the website.)

111

In SCHEME, functions are first class objects.
Functions can be passed as arguments: Consider the following

definition:
A function A positive integer
(define (sum f n)
(if (= n 0)
(f 0)
(+ (f n) (sum f (- n 1)))))
This computes the sum: f(0) + f(1) + … + f(n) Both f and n are passed as arguments.
112

Then…
To compute the sum of the first n squares:02 +12 +22 +32 +42 +52
> (define (square x) (* x x))
> (sum square 5)
55


To compute the sum of the first n cubes: 03 + 13 + 23 + 33 + 43 + 53
> (define (third x) (* x x x))
> (sum third 5)
225
113

Unnamed functions
SCHEME has a mechanism for defining functions without names:


 
 
 


argument body
(lambda (x) (* x x))
is the function that returns the square of its argument.
If you wish to sum the values of the first n squares, instead of
defining square first, you can directly pass the function:
> (sum (lambda (x) (* x x)) 10)
385

114

Define revisited
If we enlarge our notion of value to include function values, we can simplify the definition of define as an operator that always binds a name to a value.
(define (square x) (* x x))
is the same as…
(define square (lambda (x) (* x x)))

115

Let revisited
We can express let using lambda and the standard application rule!
(let ((x1 ) …
(xk exprk>)) )
…is the same as…
((lambda (x1 … xk) ) )

116