SICP 読み (8)

新年早々、オレオレ 20% ルール適用。

問題 1.20 (gcd の展開)

正規順序評価では if の中のソレ以外は引数展開されず、作用的順序では引数の評価が先、とゆー事で正規順序評価はゆっくり紙に書きたいな。作用的順序な評価は量が少なそうなので以下に。

まず、gcd の定義は以下。

(define (gcd a b)
  (if (= b 0)
     a
     (gcd b (remainder a b))))

(gcd 206 40)

 (if (= 40 0)
     206
     (gcd 40 (remainder 206 40)))

 (gcd 40 (remainder 206 40)) ;; 一回目

 (gcd 40 6)

  (if (= 6 0)
      40
      (gcd 6 (remainder 40 6)))

  (gcd 6 (remainder 40 6)) ;; 二回目

  (gcd 6 4)

   (if (= 4 0)
       6
       (gcd 4 (remainder 6 4)))

   (gcd 4 (remainder 6 4)) ;; 三回目

   (gcd 4 2)

    (if (= 2 0))
        4
        (gcd 2 (remainder 4 2))

    (gcd 2 (remainder 4 2))  ;; 四回目

    (gcd 2 0)

     (if (= 0 0))
         2
         (gcd 0 (remainder 2 0))

     2

で、四回となりました。これでも十分長い。これ、正規順序なナニはもの凄いコトになりそうです。ワケがわからなくなりそう。(アセらず、一日一題を目処にした方が良いかなぁ。スルー多いし)

問題 1.22

1.21 はスルー。で、1.22 ですが、runtime 手続きは guile では未定義な模様。get-internal-run-time 手続きで取得可能なのかなぁ。get-internal-real-time なんてのもある。とりあえず get-internal-real-time で試してみたのが以下。コードが長い。要リファクタリングとゆー感じッス。(変数名とか微妙スギ)

(define (test-timed-prime-test)
  (let f ((l (reverse (search-for-prime '(100000000 1000000000 10000000000)))))
    (cond ((not (null? l))
	   (let ff ((prime-list (car l)))
	     (cond ((null? prime-list) (f (cdr l)))
		   (else
		    (timed-prime-test (car prime-list))
		    (ff (cdr prime-list)))))))))

(define (search-for-prime l)
  (let f ((l l) (result '()))
    (cond ((null? l) result)
	  (else
	   (f (cdr l)
	      (let ff ((n (car l)) (r result) (primes '()))
		(if (= (length primes) 3)
		    (cons primes r)
		    (cond ((prime? n) (ff (+ n 1) r (append primes (cons n '()))))
			  (else (ff (+ n 1) r primes))))))))))

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (get-internal-real-time)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (get-internal-real-time) start-time))
      (newline)))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time)
  (newline))

(define (square n)
  (* n n))
(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)))

で、test-timed-prime-test 内の search-for-prime の引数なリストですが、0 を 4 桁くらい増やさないとちゃんとした数字が出てきませんでした。実行結果は以下。

guile> (test-timed-prime-test)

100000007 *** 13

100000037 *** 13

100000039 *** 14

1000000007 *** 42

1000000009 *** 44

1000000021 *** 43

10000000019 *** 161

10000000033 *** 160

10000000061 *** 161
guile> 

大体 √10 倍くらいの数値になっているのか。