ochalog

RubyとMediaWikiとIRCが好き。

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 例:素数性のテスト」より

下準備

Gaucherandom を使えるようにするために、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 個の素数について、素数テストに要する時間を測った。

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 \) が十分に大きければ予想の通りになると考えられる。