2016年9月4日日曜日

開発環境

  • OS X El Capitan - Apple (OS)
  • Emacs(Text Editor)
  • Scheme (プログラミング言語)
  • kscheme (ksi)(github) (処理系)

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原著: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の第1章(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.6(例: 素数性のテスト)、問題1.24.を取り組んでみる。

その他参考書籍

問題1.24.

コード(Emacs)

(begin
  (newline)
  (load "procedures.scm")

  (define nums '(1000 1000000))
  (define count 0)
  
  (define (expmod base exp m)
    (if (= exp 0)
         1
         (if (even? exp)
             (remainder (square (expmod base (/ exp 2) m)) m)
             (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)
    (if (= times 0)
        #t
        (if (fermat-test n)
            (fast-prime? n (- times 1))
            #f)))
    
  (define (timed-prime-test n)
    (newline)
    (display n)
    (start-prime-test n (current-second)))

  (define (start-prime-test n start-time)
    (if (fast-prime? n 10)
        ((lambda ()
           (set! count (+ count 1))
           (report-prime (- (current-second) start-time))))))

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

  (define (iter n)
    (if (not (= count 3))
        ((lambda ()
           (timed-prime-test n)
           (iter (+ n 1))))))

  ;; log 1000000 / log 1000 = 2 で 2倍くらいと予想。
  ;; 確率的方法だから、試行回数を変えると結果も違ってきそう
  (for-each (lambda (n)
              (set! count 0)
              (iter n))
            nums)
  (newline)
  'done)

入出力結果(Terminal(kscheme), REPL(Read, Eval, Print, Loop))

$ ksi < sample24.scm
ksi> 

1000
1001
1002
1003
1004
1005
1006
1007
1008
1009 *** 0.7354819774627686
1010
1011
1012
1013 *** 0.794813871383667
1014
1015
1016
1017
1018
1019 *** 1.073212146759033
1000000
1000001
1000002
1000003 *** 1.887098073959351
1000004
1000005
1000006
1000007
1000008
1000009
1000010
1000011
1000012
1000013
1000014
1000015
1000016
1000017
1000018
1000019
1000020
1000021
1000022
1000023
1000024
1000025
1000026
1000027
1000028
1000029
1000030
1000031
1000032
1000033 *** 1.422859907150269
1000034
1000035
1000036
1000037 *** 1.306676864624023
=> done
ksi> $ 

0 コメント:

コメントを投稿

Comments on Google+: