sicp-126

Posted on 2015-02-13 19:50:38 +0900 in SICP Lisp

1.21

(define (square x) (* x x))
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b) (= (remainder b a) 0))

199 and 1999 are primes, 19999’s smallest divisor is 7

1.22

(define (square x) (* x x))
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b) (= (remainder b a) 0))
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder
           (square (expomod base (/ exp 2) m))
           m))
        (else
          (remainder
            (* base (expmod base (- exp 1) m))
            m))))
(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))

(define (timed-prime-test n)
   (newline)
   (display n)
   (start-prime-test n (runtime))

(define (start-prime-test n start-time)
   (cond ((prime? n)
          (report-prime (- (runtime) start-time)))))

(define (report-prime elapsed-time)
   (display " *** ")
   (display elapsed-time))

(define (prime? n)
   (= n (smallest-divisor n)))

(define (search-for-primes start end)
  (if (even? start) (search-for-primes (+ start 1) end)
    (cond ((<= start end)
           (timed-prime-test start) (search-for-primes (+ start 2) end)))))

The tricky part is how to run evaluate expressions sequencely. According to cond expressio, the then-bodys are evaluated in order and the results of the last then body provide the result for the whole cond form.

1.26

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

The time complexity of this code is $\sum_{i=0}^{log_n} 2^n = O(n)$

1.27

(define (fixed-fermat-test n a)
  (= (expmod a n n) a))

(define (fermat-full n)
  (define (iter a)
    (cond ((= a 1) #t)
          ((not (fixed-fermat-test n a)) #f)
          (else (iter (- a 1)))))
  (iter (- n 1)))

1.28

(define (MR-expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (let* ([part (expmod base (/ exp 2) m)]
                [ans (remainder (square part) m)])
           (if (and (not (or (= part 1) (= part (- m 1))))
                    (= ans 1))
             0
             ans)))
        (else
          (remainder
            (* base (expmod base (- exp 1) m))
            m))))

(define (MR-test n)
  (define (try-it a)
    (= (MR-expmod a (- n 1) n) 1))
  (try-it (+ 2 (random (- n 2)))))

Used let* to deal with the local variable.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------

« sicp-1.31 | sicp-124-125 »