5 minute read

Section 1.2.5 - Greatest Common Divisors

Exercise 1.20

The difference between applicative and normal order is that applicative first evaluates the arguments and then applies the procedure. In contrast, normal order first expands the procedure and then reduces it. Also note that if is a special form, where which (and whether) procedure is evaluated depends on the predicate.

Let’s first see the applicative order:

(gcd 206 40) ;; apply if, second branch produces
(gcd 40 (remainder 206 40)) ;; remember, we evaluate arguments first
(gcd 40 6)
(gcd 40 (remainder 40 6)) ;; 2nd time we need remainder
(gcd 6 4)
(gcd 4 (remainder 4 6)) ;; 3rd time
(gcd 4 2)
(gcd 2 (remainder 4 2)) ;; 4th time
(gcd 2 0) ;; the predicate is true
2

In the normal order, we first expand and then apply only as needed. So:

(gcd 206 40) ;; apply if, second branch produces
(gcd 40 (remainder 206 40)) ;; the if will be as follows
;; apply gcd
(if (= (remainder 206 40) 0) ;; this gets evaluated, so 1 call
    40
    (gcd (remainder 206 40)
         (remainder 40 (remainder 206 40))))
;; apply gcd
(if (= (remainder 40 (remainder 206 40)) 0) ;; 2 calls
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
         (remainder
           (remainder 206 40
             (remainder 40 (remainder 206 40))))))
;; apply gcd
(if (= (rem (rem 206 40) (rem 40 (rem 206 40))) 0) ;; 4 calls
    (rem 40 (rem 206 40))
    (gcd (rem (rem 206 40) (rem 40 (rem 206 40)))
         (rem
           (rem 40 (rem 206 40))
           (rem (rem 206 40) (rem 40 (rem 206 40))))))
;; apply gcd
;; this time the predicate will be b from the previous
;; iteration which contains 7 calls to remainder but
;; evaluates to 0 so we evaluate a from the previous
;; iteration (4 calls to remainder) and we are done.

So in summary, the normal order will need: \(1 + 2 + 4 + 7 + 4 = 18\) calls to remainder.

Section 1.2.6 - Example: Testing for Primality

Exercise 1.21

> (smallest-divisor 199)
199
> (smallest-divisor 1999)
1999
> (smallest-divisor 19999)
7

So while \(199\) and \(1999\) are primes, \(19999\) is not.

Exercise 1.22

\(\sqrt{10} = 3.17\). This means that we expect time to roughly triple between orders of magnitude. Our results are:

;; Greater than 1,000
;; 1009 *** 3
;; 1013 *** 2
;; 1019 *** 2
;; Greater than 10,000
;; 10007 *** 6
;; 10009 *** 6
;; 10037 *** 6
;; Greater than 100,000
;; 100003 *** 17
;; 100019 *** 18
;; 100043 *** 18
;; Greater than 1,000,000
;; 1000003 *** 59
;; 1000033 *** 59
;; 1000037 *** 59

The results roughly confirm our calculations. We wouldn’t expect exact results since the actual timing depends on a lot of things.

Exercise 1.23

(define (next n)
  (if (= n 2)
      3
      (+ n 2)))
;; 1009 *** 6
;; 1013 *** 6
;; 1019 *** 6
;; 10007 *** 9
;; 10009 *** 8
;; 10037 *** 8
;; 100003 *** 16
;; 100019 *** 15
;; 100043 *** 16
;; 1000003 *** 41
;; 1000033 *** 40
;; 1000037 *** 40

Essentially the steps taken by the algorithm will now be limited by $\sqrt{n}/2$. This means that $\sqrt{n}$ will still dominate the algorithm, but given a large-enough input the time will be roughly halved.

Exercise 1.24

;; 1009 *** 13
;; 1013 *** 13
;; 1019 *** 13
;; 10007 *** 15
;; 10009 *** 14
;; 10037 *** 14
;; 100003 *** 21
;; 100019 *** 16
;; 100043 *** 16
;; 1000003 *** 17
;; 1000033 *** 18
;; 1000037 *** 19

We would expect the time to test primes near $1,000,000$ to be roughly the triple of the time to test primes near $1,000$. We do not obseve even that kind of change, probably due to fast hardware, but we do observe that the runtime grows very slowly.

Exercise 1.25

While conceptually Alyssa is correct, in practice the call to fast-expt will result in dealing with big numbers, and trying to find their remainder. Our expmod method will always find the remainder of small numbers, multiply them together, find their remainder, etc. See footnote 46. Bear in mind also that primality checks are usually done for very large numbers.

The results are pretty grave in practice:

;; 1009 *** 92
;; 1013 *** 102
;; 1019 *** 83
;; 10007 *** 3071
;; 10009 *** 3192
;; 10037 *** 2880

Exercise 1.26

By rewriting the expmod procedure to use explicit multiplication, Louis has changed it into a tree recursive process from a linear one. This means that in each steps two subtrees will be created, and the amount of calls grow exponentially. So \(2^{\log n} = n\).

Exercise 1.27

We create a procedure congruent? as such:

(define (congruent? n)
  (congruent-iter n 0))

(define (congruent-iter n a)
  (cond ((= a n) true)
        ((= (expmod a n n) a) (congruent-iter n (+ a 1)))
        (else false)))

Calling the procedure for the Carmichael numbers of footnote 47 (561, 1105, 1729, 2465, 2821 and 6601) we always get #t. The fast-prime? procedure would be fooled. However, we can use the prime? procedure to confirm that these numbers are not primes.

Exercise 1.28

First we create the function that performs the check and short-circuits the computation:

(define (miller-rabin-check a m)
  (if (and (not (= a 1))
           (not (= a (- m 1)))
           (= (remainder (square a) m) 1))
      0
      a))

We want to use the above before squaring the result of each iteration. Since we cannot store variables yet, what we can do is wrap the expmod call to itself inside a miller-rabin-check call. miller-rabin-check will get the result of the previous iteration as input, and check whether it is a non-trivial square root of 1. If it is, it will return 0, essentially short-circuting the result. If it is not, it will return the result, thus letting expmod continue as usual.

(define (miller-rabin-expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder
          (square
           (miller-rabin-check
            (miller-rabin-expmod base (/ exp 2) m) m)) m))
        (else
         (remainder (* base
          (miller-rabin-expmod base (- exp 1) m))
          m))))

Finally, we can run the check for half the size of the input to make sure we produce the correct answer:

(define (miller-rabin-test n)
  (define (try-it a)
    (= (miller-rabin-expmod a (- n 1) n) 1))
  (try-it (+ 1 (random (- n 1)))))

(define (miller-rabin-prime? n)
  (define (test-prime times)
    (cond ((<= times 0) true)
          ((miller-rabin-test n) (test-prime (- times 1)))
          (else false)))
  (test-prime (/ n 2)))

We can use both the prime numbers we found and the Carmichael numbers to confirm that our new procedure always produces the correct result and is not fooled.

Updated: