sicpm1.21〜m1.26?(3)

時間計測のところで時間を食った。
でも、そのおかげでループ処理が書けるようになった。
今日やったこと。

(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 (square x) (* x x))
;;m1.21
(smallest-divisor 199) ;=>199
(smallest-divisor 1999) ;=>1999
(smallest-divisor 19999) ;=>7
;;素数か調べる↓
(define (prime? n)
  (= n (smallest-divisor n)))
  ;;条件式だけを書けば#t or #fの結果を出力できる

;;Fermat-test logN-search-prime
;(modn a)=(modn b) ;;nでわったときのあまりが等しい
(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) true)
	((fermat-test n) (fast-prime? n (- times 1)))
	(else false)))

;;runtime=システムが走った時間を示す整数を返す。
  ;;runtimeの代わりにsys-timeを使った。
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (sys-time)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (sys-time) start-time))
      '#f))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time)
  '#t)
;;displayで表示

(define (search-for-prime start-value counter)
  (cond ((= counter 0) "done")
        (else (if (timed-prime-test start-value)
                  (search-for-prime (+ start-value 1) (- counter 1))
                  (search-for-prime (+ start-value 1) counter)))))
;;runtimeの()を外したら動いた。
　　;;返す値を真偽値にする方法が分かった。

;;m1.22は後で考える「unbound variable runtime]という表示がでます＞＜
  ;;ここ↓から、runtimeをもらってきました。
　;;http://www.csus4.net/hiki/SICPReading/?FujimotoHisaChapter1
;; gauche用runtime (microsecを返す)
;;上手く動かない
;(define runtime
;  (use srfi-11)
;  (let-values (((a b) (sys-gettimeofday)))
;    (+ (* a 1000000) b)))
     ;;*** ERROR: invalid application: (119044251300000)
;;続、m1.22
;;一応できた。(時間が計測できないケド…）
   ;;1000-> 1009, 1013, 1019
   ;;10000-> 10007, 10009, 10037
   ;;100000-> 100003, 100019, 100043
   ;;1000000-> 1000003, 1000033, 1000037
;;以降の問題は計測不可能＞＜（runtimeの代替案が見つかりません＞＜）
;;m1.23
(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 (next test-divisor)))))
(define (divides? a b)
  (= (remainder b a) 0))
(define (square x) (* x x))
(define (next test-divisor)
  (if (= test-divisor 2) 
      3
      (+ test-divisor 2)))
      ;;後は素数の計算時間を調べる。2倍早くなることを期待。

;;m1.24 timed-prime-test -> use fast-prime?

;;とりあえず、できそうな1.25と1.26からはじめてみる。
;;m1.25
;;よくわからなかった。問題としてでているから、正しくないのだと思うのだけれど…
   ;;(runtimeを探している時に見つけた回答によると、メモリ使用量が多くなるらしい）
   ;;桁数とかメモリ使用量とか把握するの苦手です＞＜
;;m1.26
;たぶん、作用的順序だからだと思う。
;試しに、fという関数が3回まで増えてから収束するようなときを考えてみる。
;1,squareの場合
(square (f x))
(square (f (f x)))
    ;1
(square (f (fx))) ;;fx = (f x)で計算された値
(square (f (f (fx))))
    ;1
(square (f (ffx)))
(square (fffx))
    ;1
ffffffx
    ;1
    ;1+1+1+1=4
 ;2,*を使った場合
(* (f x) (f x))
(* (f (f x)) (f ( f x)))
    ;2
(* (f fx) (f fx))
(* (f (f fx)) (f (f fx)))
    ;2
(* (f ffx) (f ffx))
    ;2
(* fffx fffx)
    ;1
ffffffx
    ;2+2+2+1
;;関数fがn回まで増えてから収束するとき、計算回数は1*n+1と2*n+1のように変わる。
;;とりあえず*を使った方が効率が悪いということは分かった。

;;m1.27,m1.28はめんどくさそう。


;;1.3.1
(define (sum-integers a b)
  (if (> a b)
      0
      (+ a (sum-integers (+ a 1) b))))
(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1 (* a (+ a 2))) (pi-sum (+ a 4) b))))

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a) (sum term (next a) next b))))
;;確かにみんなそうなっている。(sumでまとめられる！)
(define (inc i) (+ i 1))
(define (cube x) (* x x x))
(define (sum-cubes a b)
  (sum cube a inc b))
;;(sum-cubes 1 3) ;=> 36=1+8+27

(define (integral f a b dx)
  (define (add-dx x (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx)))

ステップ数、メモリ使用量などの計算のコツが掴めていないかもしれない。
（あとでまた考えると、分かるかもしれない）

復習？

newlineとdisplayの使い方を確かめるために、
今までの知識を使って作ってみた。

(define (fib n)
  (define (fib-iter a b n)
    (cond ((= n 0) b)
          (else (fib-iter (+ a b) a (- n 1)))))
  (fib-iter 1 0 n))
(define (fib-from-to from to result)
  (display result)
  (newline)
  (if (= from to)
      "done"
      (fib-from-to (+ from 1) to (fib from))))

gosh> (fib-from-to 1 10 0)
0
1
1
2
3
5
8
13
21
34
"done"

今のところはこんなところ。

追記

たぶん、こっちのほうがいい。

(define (fib-from-to from to)
  (define (fib-iter a b n)
    (cond ((>= (- to from) n)
           (display b)
           (newline)))
    (if (= n 0)
        "done"
    (fib-iter (+ a b) a (- n 1))))
         (fib-iter 1 0 to))

gosh> (fib-from-to 8 10)
21
34
55
"done"

さらに追記

この方が計算量少ないかも（　(- to from)を計算してないので）

(define (fib-from-to from to)
  (define (fib-iter a b n)
    (cond ((<= from n)
           (display b)
           (newline)))
    (if (= n to)
       "done"
    (fib-iter (+ a b) a (+ n 1))))
         (fib-iter 1 0 0))

問題なのは、fib-iterの中にfib-from-to評価するべき式が入っているところ。
これでも、本質的にはおなじだし…

(define (fib-from-to from to)
  (define (output? n b)
    (cond ((<= from n)
           (display b)
           (newline))))
  (define (fib-iter a b n)
    (output? n b)
    (if (= n to)
        "done"
    (fib-iter (+ a b) a (+ n 1))))
         (fib-iter 1 0 0))