SICP練習問題 1.16 - 1.24

今日はSICPの問題をガシガシ解いた。処理系はGauche。
なんか答えが載っているサイトを見つけた。後日答え合わせをする。

#?=はGaucheのマクロで、printfデバッグみたいに使っている。

SICP 1.16

(define (my-expt b n)

  (define (expt-iter a n)
	(cond ((= n 1)   #?=a)
		  ((even? n) #?=(expt-iter (* a a) (/ n 2)))
		  (else      #?=(* a (expt-iter a (- n 1))))))

  (expt-iter b n))

(print (my-expt 3 8))

結果は正しいけど、解き方は間違っているっぽい。
else節で後でaを掛けたらiterativeにならないもんなぁ。

というわけでもう一度考えてみた。要は途中状態を保存する変数を引数として追加すれば良いのだろう。
a ^ n => 1 * a ^ n
a ^ 2n => 1 * (a*a) ^ n
a ^ (n + 1) => a * a ^ n

(define (my-expt b n)

  (define (expt-iter k a n)
	(cond ((= n 1)   (* k a))
		  ((even? n) (expt-iter k (* a a) (/ n 2)))
		  (else      (expt-iter (* k a) a (- n 1)))))

  (expt-iter 1 b n))

SICP 1.17

(define (fast-mul x n)
	(let ((halv (lambda (n) (/ n 2)))
		  (double (lambda (n) (* n 2))))
	  (cond ((= n 1)   x)
			((even? n) (double (fast-mul x (halv n))))
			(else      (+ x (fast-mul x (- n 1)))))))

(fast-mul 3 4)

1.17と全く同じ解き方なんだけど、これはこれでいいのね。

SICP 1.18

(define (fast-mul x n)

  (define (mul-iter y n)
	(let ((halv (lambda (n) (/ n 2)))
		  (double (lambda (n) (* n 2))))
	  (cond ((= n 1)   #?=y)
			((even? n) #?=(mul-iter (double y) (halv n)))
			(else      #?=(+ x (mul-iter y (- n 1)))))))

  (mul-iter x n))

(fast-mul 3 4)

これも1.16と同じで間違ってる。本文を読まずにいきなり解いたのが良くなかった。
考え方は同じ。
x * n => 0 + x * n
x * 2n => 0 + 2x * n
x * (n+1) => x + x *n

(define (fast-mul x n)

  (define (mul-iter k y n)
	(let ((halv (lambda (n) (/ n 2)))
		  (double (lambda (n) (* n 2))))
	  (cond ((= n 0)   k)
			((even? n) (mul-iter k (double y) (halv n)))
			(else      (mul-iter (+ k y) y (- n 1))))))

  (mul-iter 0 x n))

SICP 1.19

ウーム、わからん。

SICP 1.20

自信なし。

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

;; normal-order
(gcd 206 40)
;->
(if (= 40 0)
	206
	(gcd 40 (remainder 206 40)))
;->
(if (= 40 0)
	206
	(gcd 40 6) ; call remainder
;->
(if (= 40 0)
	206
	(if (= 6 0)
		40
		(gcd 6 (remainder 40 6))))
;->
(if (= 40 0)
	206
	(if (= 6 0)
		40
		(gcd 6 4))) ; call remainder
;->
(if (= 40 0)
	206
	(if (= 6 0)
		40
		(if (= 4 0)
			6
			(gcd 4 (remainder 6 4)))))
;->
(if (= 40 0)
	206
	(if (= 6 0)
		40
		(if (= 4 0)
			6
			(gcd 4 2)))) ; call remainder
;->
(if (= 40 0)
	206
	(if (= 6 0)
		40
		(if (= 4 0)
			6
			(if (= 2 0)
				4
				(gcd 2 (remainder 4 2))))))
;->
(if (= 40 0)
	206
	(if (= 6 0)
		40
		(if (= 4 0)
			6
			(if (= 2 0)
				4
				(gcd 2 0))))) ; call remainder
;->
(if (= 40 0)
	206
	(if (= 6 0)
		40
		(if (= 4 0)
			6
			(if (= 2 0)
				4
				(if (= 0 0)
					2
					(gcd 0 (remainder 2 0)))))))
;->
2

;; applicative-order
(gcd 206 40)
;->
(if (= 0 40)
	206
	(gcd 40 (remainder 206 40)))
;->
(gcd 40 (remainder 206 40))
;->
(gcd 40 6) ; call remainder
;->
(if (= 0 6)
	40
	(gcd 6 (remainder 40 6)))
;->
(gcd 6 4) ; call remainder
;->
(if (= 0 2)
	6
	(gcd 2 (remainder 4 2)))
;->
(gcd 2 (remainder 4 2))
;->
(gcd 2 0) ; call remainder
;->
(if (= 0 0)
	2
	(gcd 0 (remainder 2 0)))
;->
2

SICP 1.21

(define (smallest-divisor n)

  (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 a)
	(* a a))

  (define (remainder a b)
	(modulo a b))

  (find-divisor n 2))

(smallest-divisor 199)
(smallest-divisor 1999)
(smallest-divisor 19999)

SICP 1.22

(use srfi-19)
(define (timed-prime-test n)

  (define (start-prime-test n start-time)
	(if (prime? n)
		(report-prime start-time)))

  (define (report-prime start-time)
	(display " *** ")
	(display (time-difference (current-time) start-time)))

  (define (prime? n)
	(= n (smallest-divisor 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)
	(= (modulo b a) 0))

  (define (square n)
	(* n n))

  (display n)
  (start-prime-test n (current-time)))

(timed-prime-test 90000000019) ; prime
(timed-prime-test 90000000020) ; non prime
(timed-prime-test 300000000077) ; prime
(timed-prime-test 300000000078) ; non prime

SICP 1.23

(use srfi-19)

(define (timed-prime-test n)

  (define (start-prime-test n start-time)
	(if (prime? n)
		(report-prime start-time)))

  (define (report-prime start-time)
	(display " *** ")
	(display (time-difference (current-time) start-time)))

  (define (prime? n)
	(= n (smallest-divisor 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)
	(= (modulo b a) 0))

  (define (square n)
	(* n n))
  
  (display n)
  (start-prime-test n (current-time)))

(timed-prime-test 90000000019) ; prime
(timed-prime-test 90000000020) ; non prime
(timed-prime-test 300000000077) ; prime
(timed-prime-test 300000000078) ; non prime

SICP 1.24

(use srfi-19)
(use srfi-27)

(define (timed-prime-test n)

  (define (start-prime-test n start-time)
	(if (fast-prime? n 10000)
		(report-prime start-time)))

  (define (report-prime start-time)
	(display " *** ")
	(display (time-difference (current-time) start-time)))

  (define (fast-prime? n times)
	(cond ((= times 0) #t)
		  ((fermat-test n) (fast-prime? n (- times 1)))
		  (else #f)))

  (define (fermat-test n)
	(define (try-it a)
	  (= (expmod a n n) a))
	(try-it (+ 1 (random-integer (- n 1)))))

  (define (expmod base exp m)
	(cond ((= exp 0)   1)
		  ((even? exp) (modulo (square (expmod base (/ exp 2) m)) m))
		  (else        (modulo (* base (expmod base (- exp 1) m)) m))))

  (define (square n)
	(* n n))
  
  (display n)
  (start-prime-test n (current-time)))

(timed-prime-test 90000000019) ; prime
(timed-prime-test 90000000020) ; non prime
(timed-prime-test 300000000077) ; prime
(timed-prime-test 300000000078) ; non prime