sicp-exercise-1.21-1.28

Exercise 1.21

199 and 1999 are prime numbers, and 19999 has smallest divisor of 7.

Exercise 1.22 - 1.24

FIXME
Now on my machine the test always returns zero :( So I have to postpone 1.22-1.24 afterward. (runtime) seems not using microseconds, and even not seconds.

Exercise 1.25

Ms. Hacker is not correct exactly. My first attempt is just like hers, calculating exponentiation and using it to evaluate a^n % m. But this approach fails to get a result in a reasonably short time for input around just ten thousand.

The expmod in the text is based on the fact that,

(a*b) % m = ((a%m) * (b%m)) % m
     = ((a%m) * b) % m
     = (a * (b%m) % m
(a^2) % m = ((a%m)^2) % m

The above equations can be easily seen once you write a,b as
a = km + r1
b = nm + r2

Exercise 1.27

expmod, smallest-divisor and prime? from the text are used.

(define (check a n)
  (cond ((= a n) true)
        ((= (expmod a n n) a) (check (+ a 1) n))
        (else false)))

(define (test-fermat n)
  (display "\n")
  (display n)
  (display "\n")
  (if (prime? n)
    (display "\tis prime\n")
    (display "\tis not prime.\n"))
  (if (check 2 n)
    (display "\tpass fermat test.\n")
    (display "\tfail fermat test.\n")))

Exercise 1.28

I use the special form 'let', since I need a local variable here.
I suppose I can't write defines in cond, although "the part of each cond clause may be a sequence of expressions" (footnote #19), like:

(define (f x)
  (cond ((> x 1)
         (define bar ())
         (define (foo a) ())
         (foo bar))
        ()))

Can I? The error reads: Can't bind name in null syntactic environment. Seems that it's a temporary environment.

(define (nontrivial-sqrt? x n)
  (if (and (= (remainder (square x) n) 1)
           (not (= x 1))
           (not (= x (- n 1))))
    true
    false))

(define (new-expmod base expo mod)
  (cond ((= expo 0) 1)
        ((even? expo) (let ((temp (new-expmod base (/ expo 2) mod)))
                        (if (nontrivial-sqrt? temp mod)
                          0
                          (remainder (square temp) mod))))
        (else (remainder (* base (new-expmod base (- expo 1) mod))
                                 mod))))

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

(define (check-prime n checktimes)
  (cond ((= checktimes 0) true)
        ((miller-rabin-test n) (is-prime? n (- checktimes 1)))
        (else false)))

(define (prime? n)
  (check-prime n 1))