SICP: Exercise 1.24

問題 1.24

問題 1.22 の timed-prime-test 手続きを fast-prime?（Fermat 法参照）を使うように変え、その問題で見つけた 12 個の素数をテストせよ。Fermat テストは $ \Theta(\log n) $ の増加なので、1,000,000 近くの素数をテストする時間を 1,000 近くの素数をテストする時間と比べ、どの位と予想するか。データはその予想を支持するか。違いがあれば説明出来るか。

「計算機プログラムの構造と解釈第二版 1.2.6 例：素数性のテスト」より

下準備

Gauche で random を使えるようにするために、srfi-27 モジュールを利用する。以下、本文の手続きも含めてまとめて定義する。

(use srfi-27)

(define (random n) (random-integer n))
(random-source-randomize! default-random-source)

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

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod 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) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #t)))

(load "./ex-1-22.scm")

解答

とりあえず 10 回 Fermat テストを行うように書いた。

(define (start-prime-test n start-time)
  (if (fast-prime? n 10)
    (report-prime n (- (runtime) start-time))))

1,000,000 近くの素数をテストする時間と 1,000 近くの素数をテストする時間の比は、段階数が $ \Theta(\log n) $ なので

$$ \frac{\log 1000000}{\log 1000} = \frac{\log (10^6)}{\log (10^3)} = \frac{6 \log 10}{3 \log 10} = 2 $$

と予想した。

結果

問題 1.23 と同様に 12 個の素数について、素数テストに要する時間を測った。

<a href="http://ochaochaocha3.hateblo.jp/entry/2015/04/12/sicp-ex-1-23">SICP: Exercise 1.23 - ochalog</a>ochaochaocha3.hateblo.jp

結果を以下に示す。

素数：$ p $	問題 1.23：$ t_\mathrm{A}/\mathrm{\mu s} $	問題 1.24：$ t_\mathrm{B}/\mathrm{\mu s} $	$ t_\mathrm{A} / t_\mathrm{B} $
1,009	7	47	0.1
1,013	4	39	0.1
1,019	5	42	0.1
10,007	13	48	0.3
10,009	13	46	0.3
10,037	13	47	0.3
100,003	38	54	0.7
100,019	39	55	0.7
100,043	39	55	0.7
1,000,003	122	60	2.0
1,000,033	122	62	2.0
1,000,037	122	62	2.0

毎回 10 回ずつ Fermat テストを行っているためか $ p $ が小さいうちは遅いけれど、$ p \approx 1,000,000 $ ではかなり速くなっている。

追加でもう一桁大きいときの時間を計測。

素数：$ p $	問題 1.23：$ t_\mathrm{A}/\mathrm{\mu s} $	問題 1.24：$ t_\mathrm{B}/\mathrm{\mu s} $	$ t_\mathrm{A} / t_\mathrm{B} $
10,000,019	395	74	5.3
10,000,079	395	75	5.3
10,000,103	394	74	5.3

さらに差が広がった。桁数が大きくなるにつれて $ \Theta(\sqrt{n}) $ と $ \Theta(\log n) $ の差は大きくなっていくのだろう。

1,000,000 近くの素数をテストする時間と 1,000 近くの素数をテストする時間の比は、平均をとって計算してみると

$$ \frac{61.3}{42.7} \approx 1.44 $$

おや、思ったより大きくない。改めて fermat-test を見てみる。

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

expmod は $ \Theta(\log n) $ だがその寄与が大きくないということは、random で時間がかかっているということだろう。

そこで、p を大きくして expmod に要する時間を長くしてみる。

(search-for-primes 100000000 100000100)
; 100000007 *** 92
; 100000037 *** 86
; 100000039 *** 88
; 平均 88.7

(search-for-primes 100000000000 100000000100)
; 100000000003 *** 180
; 100000000019 *** 176
; 100000000057 *** 173
; 平均 176.3

$$ \frac{176.3}{88.7} \approx 1.99 $$

このようにすると 1,000 倍したときとの時間の比が 2 に近づいた。したがって、$ p $ が十分に大きければ予想の通りになると考えられる。