Use the smallest-divisor procedure to find the smallest divisor of each of the following numbers:
199, 1999, 19999.

scheme@(guile-user)> (smallest-divisor 199)
199
scheme@(guile-user)> (smallest-divisor 1999)
1999
scheme@(guile-user)> (smallest-divisor 19999)
7

Most Lisp implementations include a primitive called runtime that returns an integer that specifies
the amount of time the system has been running (measured, for example, in microseconds). The
following timed-prime-test procedure, when called with an integer n, prints n and checks to see if n
is prime. If n is prime, the procedure prints three asterisks followed by the amount of time used in
performing the test.

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

Using this procedure, write a procedure search-for-primes that checks the primality of consecutive
odd integers in a specified range. Use your procedure to find the three smallest primes larger than
1000; larger than 10,000; larger than 100,000; larger than 1,000,000. Note the time needed to test
each prime. Since the testing algorithm has order of growth of [theta]([sqrt](n)), you should expect
that testing for primes around 10,000 should take about [sqrt](10) times as long as testing for
primes around 1000. Do your timing data bear this out? How well do the data for 100,000 and
1,000,000 support the [sqrt](n) prediction? Is your result compatible with the notion that programs
on your machine run in time proportional to the number of steps required for the computation?

guile 中没有 runtime 函数，我用了其自带的(srfi srfi-19)模块中的 current-time 函数来获取时间，用 time-difference 来计算时间差。

我的程序：
(use-modules (srfi srfi-19))

(define (square x)
  (* x x))

(define (divides? a b)
  (= (remainder b a) 0))

(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 (smallest-divisor n)
  (find-divisor n 2))

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

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

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (time-difference (current-time) start-time))))

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (current-time)))

(define (search-for-primes start count)
  (cond ((= count 0)
         (newline)
         (display "end")
         (newline))
        ((even? start)
         (search-for-primes (+ start 1) count))
        ((prime? start)
         (timed-prime-test start)
         (search-for-primes (+ start 2) (- count 1)))
        (else
         (search-for-primes (+ start 2) count))))

我运行的结果：

scheme@(guile-user)> (search-for-primes 1000 3)

1009***#<time type: time-duration nanosecond: 2032000 second: 0>
1013***#<time type: time-duration nanosecond: 139000 second: 0>
1019***#<time type: time-duration nanosecond: 139000 second: 0>
end
scheme@(guile-user)> (search-for-primes 10000 3)

10007***#<time type: time-duration nanosecond: 521000 second: 0>
10009***#<time type: time-duration nanosecond: 234000 second: 0>
10037***#<time type: time-duration nanosecond: 256000 second: 0>
end
scheme@(guile-user)> (search-for-primes 100000 3)

100003***#<time type: time-duration nanosecond: 600000 second: 0>
100019***#<time type: time-duration nanosecond: 666000 second: 0>
100043***#<time type: time-duration nanosecond: 662000 second: 0>
end
scheme@(guile-user)> (search-for-primes 1000000 3)

1000003***#<time type: time-duration nanosecond: 1784000 second: 0>
1000033***#<time type: time-duration nanosecond: 3893000 second: 0>
1000037***#<time type: time-duration nanosecond: 13945000 second: 0>
end

The smallest-divisor procedure shown at the start of this section does lots of needless testing:
After it checks to see if the number is divisible by 2 there is no point in checking to see if it is
divisible by any larger even numbers. This suggests that the values used for test-divisor should not
be 2, 3, 4, 5, 6, ..., but rather 2, 3, 5, 7, 9, .... To implement this change, define a procedure
next that returns 3 if its input is equal to 2 and otherwise returns its input plus 2. Modify the
smallest-divisor procedure to use (next test-divisor) instead of (+ test-divisor 1). With
timed-prime-test incorporating this modified version of smallest-divisor, run the test for each of
the 12 primes found in Exercise 1-22. Since this modification halves the number of test steps, you
should expect it to run about twice as fast. Is this expectation confirmed? If not, what is the
observed ratio of the speeds of the two algorithms, and how do you explain the fact that it is
different from 2?

使用 next 过程的 find-divisor 版本：

(define (find-divisor n test-divisor)
  (define (next n)
    (if (= n 2)
        3
        (+ n 2)))
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))

运行结果：

scheme@(guile-user)> (search-for-primes 1000 3)

1009***#<time type: time-duration nanosecond: 463000 second: 0>
1013***#<time type: time-duration nanosecond: 59000 second: 0>
1019***#<time type: time-duration nanosecond: 97000 second: 0>
end
scheme@(guile-user)> (search-for-primes 10000 3)

10007***#<time type: time-duration nanosecond: 126000 second: 0>
10009***#<time type: time-duration nanosecond: 135000 second: 0>
10037***#<time type: time-duration nanosecond: 102000 second: 0>
end
scheme@(guile-user)> (search-for-primes 100000 3)

100003***#<time type: time-duration nanosecond: 471000 second: 0>
100019***#<time type: time-duration nanosecond: 453000 second: 0>
100043***#<time type: time-duration nanosecond: 450000 second: 0>
end
scheme@(guile-user)> (search-for-primes 1000000 3)

1000003***#<time type: time-duration nanosecond: 617000 second: 0>
1000033***#<time type: time-duration nanosecond: 630000 second: 0>
1000037***#<time type: time-duration nanosecond: 661000 second: 0>
end

Modify the timed-prime-test procedure of Exercise 1-22 to use fast-prime? (the Fermat method), and
test each of the 12 primes you found in that exercise. Since the Fermat test has [theta](log n)
growth, how would you expect the time to test primes near 1,000,000 to compare with the time needed
to test primes near 1000? Do your data bear this out? Can you explain any discrepancy you find?

scheme@(guile-user)> (search-for-primes 1000 3)

1009***#<time type: time-duration nanosecond: 3307000 second: 0>
1013***#<time type: time-duration nanosecond: 6898000 second: 0>
1019***#<time type: time-duration nanosecond: 3568000 second: 0>
end
scheme@(guile-user)> (search-for-primes 10000 3)

10007***#<time type: time-duration nanosecond: 11112000 second: 0>
10009***#<time type: time-duration nanosecond: 2056000 second: 0>
10037***#<time type: time-duration nanosecond: 6211000 second: 0>
end
scheme@(guile-user)> (search-for-primes 100000 3)

100003***#<time type: time-duration nanosecond: 28493000 second: 0>
100019***#<time type: time-duration nanosecond: 23917000 second: 0>
100043***#<time type: time-duration nanosecond: 7900000 second: 0>
end
scheme@(guile-user)> (search-for-primes 1000000 3)

1000003***#<time type: time-duration nanosecond: 16848000 second: 0>
1000033***#<time type: time-duration nanosecond: 6181000 second: 0>
1000037***#<time type: time-duration nanosecond: 19970000 second: 0>
end

Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod. After all, she
says, since we already know how to compute exponentials, we could have simply written

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

Is she correct? Would this procedure serve as well for our fast prime tester? Explain.

The modified version of expmod computes huge intermediate results.

Scheme is able to handle arbitrary-precision arithmetic, but arithmetic with arbitrarily long
numbers is computationally expensive. This means that we get the same (correct) results, but it
takes considerably longer.

Louis Reasoner is having great difficulty doing Exercise 1-24. His fast-prime? test seems to run
more slowly than his prime? test. Louis calls his friend Eva Lu Ator over to help. When they examine
Louis's code, they find that he has rewritten the expmod procedure to use an explicit
multiplication, rather than calling square:

(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))))

“I don't see what difference that could make,” says Louis. “I do.” says Eva. “By writing the
procedure like that, you have transformed the [theta](log n) process into a [theta](n) process.”
Explain.

Instead of a linear recursion, the rewritten expmod generates a tree recursion, whose execution time
grows exponentially with the depth of the tree, which is the logarithm of N. Therefore, the
execution time is linear with N.

Demonstrate that the Carmichael numbers listed in Footnote 1-47 really do fool the Fermat test. That
is, write a procedure that takes an integer n and tests whether a^n is congruent to a modulo n for
every a<n, and try your procedure on the given Carmichael numbers.

(define (carmichael? n)
  (define (try a)
    (= (expmod a n n) a))
  (define (iter bool count)
    (if (= count 0)
        bool
        (iter (and bool (try count)) (- count 1))))
  (iter #t (- n 1)))

One variant of the Fermat test that cannot be fooled is called the Miller-Rabin test (Miller 1976;
Rabin 1980). This starts from an alternate form of Fermat's Little Theorem, which states that if n
is a prime number and a is any positive integer less than n, then a raised to the (n - 1)st power is
congruent to 1 modulo n. To test the primality of a number n by the Miller-Rabin test, we pick a
random number a<n and raise a to the (n - 1)st power modulo n using the expmod procedure. However,
whenever we perform the squaring step in expmod, we check to see if we have discovered a “nontrivial
square root of 1 modulo n,” that is, a number not equal to 1 or n - 1 whose square is equal to 1
modulo n. It is possible to prove that if such a nontrivial square root of 1 exists, then n is not
prime. It is also possible to prove that if n is an odd number that is not prime, then, for at least
half the numbers a<n, computing a^(n-1) in this way will reveal a nontrivial square root of 1 modulo
n. (This is why the Miller-Rabin test cannot be fooled.) Modify the expmod procedure to signal if it
discovers a nontrivial square root of 1, and use this to implement the Miller-Rabin test with a
procedure analogous to fermat-test. Check your procedure by testing various known primes and
non-primes. Hint: One convenient way to make expmod signal is to have it return 0.

(define (square x) (* x x))

(define (miller-rabin-expmod base exp m)
  (define (squaremod-with-check x)
    (define (check-nontrivial-sqrt1 x square)
      (if (and (= square 1)
               (not (= x 1))
               (not (= x (- m 1))))
          0
          square))
    (check-nontrivial-sqrt1 x (remainder (square x) m)))
  (cond ((= exp 0) 1)
        ((even? exp) (squaremod-with-check
                      (miller-rabin-expmod base (/ exp 2) m)))
        (else
         (remainder (* base (miller-rabin-expmod base (- exp 1) m))
                    m))))

(define (miller-rabin-test n)
  (define (try-it a)
    (define (check-it x)
      (and (not (= x 0)) (= x 1)))
    (check-it (miller-rabin-expmod a (- n 1) n)))
  (try-it (+ 1 (random (- n 1)))))

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

(define (prime? n)
  (fast-prime? n 100))