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