開発環境
- OS X Mavericks - Apple(OS)
- Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
- Scheme (プログラミング言語)
- Gauche (処理系)
計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.6(例: 素数性のテスト)、問題 1.22.を解いてみる。
その他参考書籍
- Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
- プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)
問題 1.22.
コード(BBEdit, Emacs)
sample.scm
#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-
;; let-valuesを使うため
(use srfi-11)
(define (search-for-primes a b)
(if (even? a)
(iter (+ a 1) b)
(iter a b)))
(define (iter a b)
(if (> a b)
(begin (newline) 'done)
(begin (timed-prime-test a)
(iter (+ a 2) b))))
(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))
;;
(define (square x) (* x x))
(define (smallest-divisor n)
(find-divisor n 2))
(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 (divides? a b)
(= (remainder b a) 0))
(define (prime? n)
(= n (smallest-divisor n)))
(define (runtime)
(let-values (((a b) (sys-gettimeofday)))
(+ (* 1000000 a) b)))
(define (even? n)
(= (remainder n 2) 0))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
$ gosh gosh> (load "./sample") #t gosh> (search-for-primes 10000000000 10000000100) 10000000001 10000000003 10000000005 10000000007 10000000009 10000000011 10000000013 10000000015 10000000017 10000000019 *** 27414 10000000021 10000000023 10000000025 10000000027 10000000029 10000000031 10000000033 *** 30205 10000000035 10000000037 10000000039 10000000041 10000000043 10000000045 10000000047 10000000049 10000000051 10000000053 10000000055 10000000057 10000000059 10000000061 *** 27488 10000000063 10000000065 10000000067 10000000069 *** 27454 10000000071 10000000073 10000000075 10000000077 10000000079 10000000081 10000000083 10000000085 10000000087 10000000089 10000000091 10000000093 10000000095 10000000097 *** 27748 10000000099 done gosh> (search-for-primes 100000000000 100000000100) 100000000001 100000000003 *** 93219 100000000005 100000000007 100000000009 100000000011 100000000013 100000000015 100000000017 100000000019 *** 89957 100000000021 100000000023 100000000025 100000000027 100000000029 100000000031 100000000033 100000000035 100000000037 100000000039 100000000041 100000000043 100000000045 100000000047 100000000049 100000000051 100000000053 100000000055 100000000057 *** 87753 100000000059 100000000061 100000000063 *** 90402 100000000065 100000000067 100000000069 *** 91199 100000000071 100000000073 *** 88713 100000000075 100000000077 100000000079 100000000081 100000000083 100000000085 100000000087 100000000089 100000000091 *** 90142 100000000093 100000000095 100000000097 100000000099 done gosh> (search-for-primes 1000000000000 1000000000100) 1000000000001 1000000000003 1000000000005 1000000000007 1000000000009 1000000000011 1000000000013 1000000000015 1000000000017 1000000000019 1000000000021 1000000000023 1000000000025 1000000000027 1000000000029 1000000000031 1000000000033 1000000000035 1000000000037 1000000000039 *** 293729 1000000000041 1000000000043 1000000000045 1000000000047 1000000000049 1000000000051 1000000000053 1000000000055 1000000000057 1000000000059 1000000000061 *** 283460 1000000000063 *** 285646 1000000000065 1000000000067 1000000000069 1000000000071 1000000000073 1000000000075 1000000000077 1000000000079 1000000000081 1000000000083 1000000000085 1000000000087 1000000000089 1000000000091 *** 284780 1000000000093 1000000000095 1000000000097 1000000000099 done gosh> (search-for-primes 10000000000000 10000000000100) 10000000000001 10000000000003 10000000000005 10000000000007 10000000000009 10000000000011 10000000000013 10000000000015 10000000000017 10000000000019 10000000000021 10000000000023 10000000000025 10000000000027 10000000000029 10000000000031 10000000000033 10000000000035 10000000000037 *** 904050 10000000000039 10000000000041 10000000000043 10000000000045 10000000000047 10000000000049 10000000000051 *** 893985 10000000000053 10000000000055 10000000000057 10000000000059 10000000000061 10000000000063 10000000000065 10000000000067 10000000000069 10000000000071 10000000000073 10000000000075 10000000000077 10000000000079 10000000000081 10000000000083 10000000000085 10000000000087 10000000000089 10000000000091 10000000000093 10000000000095 10000000000097 10000000000099 *** 887987 done gosh> (search-for-primes 100000000000000 100000000000100) 100000000000001 100000000000003 100000000000005 100000000000007 100000000000009 100000000000011 100000000000013 100000000000015 100000000000017 100000000000019 100000000000021 100000000000023 100000000000025 100000000000027 100000000000029 100000000000031 *** 2856818 100000000000033 100000000000035 100000000000037 100000000000039 100000000000041 100000000000043 100000000000045 100000000000047 100000000000049 100000000000051 100000000000053 100000000000055 100000000000057 100000000000059 100000000000061 100000000000063 100000000000065 100000000000067 *** 2840096 100000000000069 100000000000071 100000000000073 100000000000075 100000000000077 100000000000079 100000000000081 100000000000083 100000000000085 100000000000087 100000000000089 100000000000091 100000000000093 100000000000095 100000000000097 *** 3103413 100000000000099 *** 2837101 done gosh> (define (avg a b c) (/ (+ a b c) 3.0)) avg gosh> (avg 27414 30205 27488) 28369.0 gosh> (avg 93219 89957 87753) 90309.66666666667 gosh> (avg 293729 283460 285646) 287611.6666666667 gosh> (avg 904050 893985 887987) 895340.6666666666 gosh> (avg 2856818 2840096 3103413) 2933442.3333333335 gosh> (/ 90309.66666666667 28369.0) 3.1833926704031397 gosh> (/ 287611.6666666667 90309.66666666667) 3.184727363995733 gosh> (/ 895340.6666666666 287611.6666666667) 3.1130192910579657 gosh> (/ 2933442.3333333335 895340.6666666666) 3.276342114844927 gosh> (sqrt 10) 3.1622776601683795 gosh> (exit) $
結果から、プログラムが計算に必要なステップ数に比例した時間(今の場合は√10倍の時間)で走るという考えに合っている。
0 コメント:
コメントを投稿