mahata@Choklog

問題1.33

組み合せる項にフィルタ(filter)の考えを入れることで,accumulate(問題1.32)の更に一般的なものが得られる.つまり範囲から得られて,指定した条件を満した項だけを組み合せる.出来上ったfiltered-accumulate抽象は,accumulateと同じ引数の他,フィルタを指定する一引数の述語をとる.filtered-accumulateを手続きとして書け.filtered-accumulateを使い,どう表現するかを示せ.

a. 区間a,bの素数の二乗の和(prime? 述語は持っていると仮定する.)
b. nと互いに素で,nより小さい正の整数(つまりi＜nでGCD(i,n)=1なる全整数i)の積

--

; --                                                                                                                            
; 標準的関数をロード                                                                                                            
; --                                                                                                                            
(load "./util.scm")

; --                                                                                                                            
; filter込みのaccumulate                                                                                                        
; --                                                                                                                            
(define (filtered-accumulate combiner null-value term a next b filter)
  (if (> a b)
      null-value
      (if (filter a)
          (combiner (term a) (filtered-accumulate combiner null-value term (next a) next b filter))
          (combiner null-value (filtered-accumulate combiner null-value term (next a) next b filter))
      )
  )
)

(print "計算結果: " (filtered-accumulate + 0 identity 1 inc 10 prime?))

このコードでaの問題を解決することができる。

$ gosh 1.33.scm
計算結果: 18

ただし、これではbの問題は解決できていない。gcdのように複数の引数を必要とするものはどう渡してよいのかわからない...。もう少し考えてみる。

問題1.32

a.
sumと(問題1.31の)productは,一般的なアキュムレーションの関数:

(accumulate combiner null-value term a next b)

を使い,項の集りを組み合せるaccumulateという更に一般的なものの特殊な場合であることを示せ.accumulateは引数としてsumやproductと同様,項と範囲指定と,先行する項のアキュムレーションと現在の項をどう組み合せるかを指定する(二引数の)combiner手続き,項がなくなった時に使う値を指定するnull-valueをとる.accumulateを書き,sumやproductがaccumulateの単なる呼出しで定義出来ることを示せ.

b.
上のaccumulateが再帰的プロセスを生成するなら,反復的プロセスを生成するものを書け.反復的プロセスを生成するなら,再帰的プロセスを生成するものを書け.

--

; --                                                                                                                          
; 標準的関数をロード                                                                                                          
; --                                                                                                                          
(load "./util.scm")

; --                                                                                                                          
; 再帰的なaccumulateの実装                                                                                                    
; --                                                                                                                          
(define (accumulate-rec combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate-rec combiner null-value term (next a) next b))
  )
)
(print "再帰的な実装: " (accumulate-rec + 0 identity 1 inc 10))

; --                                                                                                                          
; 反復的なaccumulateの実装                                                                                                    
; --                                                                                                                          
(define (accumulate-rep combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (term a))))
  )
  (iter a null-value)
)
(print "反復的な実装: " (accumulate-rep + 0 identity 1 inc 10))

実行する。

$ gosh 1.32.scm
再帰的な実装: 55
反復的な実装: 55

再帰的な実装も反復的な実装も、同じ値が返る。

問題1.31

a.
sum手続きは高階手続きとして書ける,同様な数多い抽象の最も単純なものに過ぎない.与えられた範囲の点での関数値の積を返すproductという似た手続きを書け.productを使って,factorialを定義せよ.また式

π/4 = (2*4*4*6*6*8...)/(3*3*5*5*7*7...)

によってπの近似値を計算するのにproductを使え.

b.
上のproductが再帰的プロセスを生成するなら,反復的プロセスを生成するものを書け.反復的プロセスを生成するなら,再帰的プロセスを生成するものを書け.

--

; --                                                                                                                          
; 標準的関数をロード                                                                                                          
; --                                                                                                                          
(load "./util.scm")

; --                                                                                                                          
; 再帰的なproductの実装                                                                                                       
; --                                                                                                                          
(define (product-rec term a next b)
  (if (> a b)
      1
      (* (term a)
         (product-rec term (next a) next b)))
)
(print "再帰的な計算(2): " (product-rec identity 1 inc 2)) ; (factorial 2)                                                    
(print "再帰的な計算(3): " (product-rec identity 1 inc 3)) ; (factorial 3)                                                    
(print "再帰的な計算(4): " (product-rec identity 1 inc 4)) ; (factorial 4)                                                    

; --                                                                                                                          
; πを近似する（バグってるぽい...）                                                                                            
; --                                                                                                                          
(define (plus2 n)
  (+ n 2)
)
(print (* (/ (* 2 (square (product-rec identity 4 plus2 10000))) (square (product-rec identity 3 plus2 10001))) 4))

; --                                                                                                                          
; 反復的なproductの実装                                                                                                       
; --                                                                                                                          
(define (product-rep term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* result (term a)) )))
  (iter a 1)
)
(print "反復的な計算(2): " (product-rep identity 1 inc 2)) ; (factorial 2)                                                    
(print "反復的な計算(3): " (product-rep identity 1 inc 3)) ; (factorial 3)                                                    
(print "反復的な計算(4): " (product-rep identity 1 inc 4)) ; (factorial 4) 

再帰的なproductと反復的なproductは実装できたが、πの近似値がでない。とても大きい値が返る。後でSICP読書会にてスーパーハッカー達に質問して、追記する。

問題1.30

上のsum手続きは線形再帰を生成する.総和が反復的に実行出来るように手続きを書き直せる.次の定義の欠けているところを補ってこれを示せ:

(define (sum term a next b)
  (define (iter a result)
    (if <??>
        <??>
        (iter <??> <??>)))
  (iter <??> <??>))

--

再帰的な実装と反復的な実装を併せて記述する。

; --                                                                                                                          
; 標準的関数をロード                                                                                                          
; --                                                                                                                          
(load "./util.scm")

; --                                                                                                                          
; 再帰的なsumの実装                                                                                                           
; --                                                                                                                          
(define (sum-rec term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum-rec term (next a) next b)))
)

; --                                                                                                                          
; 反復的なsumの実装                                                                                                           
; --                                                                                                                          
(define (sum-rep term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ result (term a)) )))
  (iter a 0)
)

(print "再帰的な計算(2): " (sum-rec cube 0 inc 2))
(print "反復的な計算(2): " (sum-rep cube 0 inc 2))
(print "再帰的な計算(3): " (sum-rec cube 0 inc 3))
(print "反復的な計算(3): " (sum-rep cube 0 inc 3))
(print "再帰的な計算(3): " (sum-rec cube 0 inc 4))
(print "反復的な計算(3): " (sum-rep cube 0 inc 4))

実行結果は次の通り。

$ gosh 1.30.scm
再帰的な計算(2): 9
反復的な計算(2): 9
再帰的な計算(3): 36
反復的な計算(3): 36
再帰的な計算(3): 100
反復的な計算(3): 100

再帰的な実装でも反復的な実装でも、同じ結果が返ることがわかる。

問題1.26

Louis Reasonerは問題1.24がなかなかうまくいかなかった.彼のfast-prime?はprime?よりずっと遅いようであった.Louisは友人のEva Lu Atorに助けを求めた.Louisのプログラムを見ていると,squareを呼び出す代りに乗算を陽に使うように変っていた.

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

「違いが分らん」とLouis,「分る」とEvaがいった.「手続きをこのように書き替えたので,Θ(log n)のプロセスをΘ(n)のプロセスにしてしまった.」説明せよ.


--


元(問題1.24)のコードでのexpmodが次のようなものであった。

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

こちらでは、expが偶数の場合、expmodを再帰的に呼び出し、それをsquareで平方を取る。一方で、Louisのコードでは、expが偶数の場合、expmodを再帰的に二度呼び出し、それを掛け合わせて平方を取る。したがって、Louisのコードは問題1.24のコードより遅くなる。

問題 1.25

Alyssa P. Hackerはexpmodを書くのに多くの余分なことをやったと不満で,結局べき乗の計算法は知っているから

(define (expmod base exp m)
(remainder (fast-expt base exp) m))

と単純に書ける筈だといった.これは正しいか.これも高速素数テストと同じに使えるか,説明せよ.


「Alyssa P.Hacker」のアイディアはうまくいかない。


remainderの引数である　(fast-expt base exp)　を評価すると、「baseのexp乗」という非常に大きい値が返るがこれが問題となる。remainderは引数1と引数2の剰余をとる手続きだが、その実装は次のようになる。

1) 引数1 = 引数1 - 引数2
2) if (引数1 < 引数2) => 引数1が剰余
   else 1) へジャンプ

このケースで、非常に大きい値が引数1に存在すると、この計算が重くなる。したがって、fast-exptで高速素数テストを行うことはできない。

(use slib)
(use srfi-19)
(load "/usr/local/lib/slib/random.scm")

(define (expmod base exp m)
  (remainder (fast-expt base exp) 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) 1)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else 0)))

(define (square x) (* x x))

(define (fast-prime-wrap from n)
  (cond ((= n 0) 1)
        ((fermat-test from)
            (print from " is prime")
            (fast-prime-wrap (+ from 1) (- n 1))
        )
        (else (fast-prime-wrap (+ from 1) n))
  )
)

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

(define (fast-prime-wrap-time from n start-time)
  (fast-prime-wrap from n)   
  (print (time-difference (current-time) start-time))
)

(fast-prime-wrap-time 1000 3 (current-time))
(fast-prime-wrap-time 10000 3 (current-time))
(fast-prime-wrap-time 100000 3 (current-time))

プログラムの実行時間を計測する方法


gaucheではruntimeの実装がデフォルトでは存在しないので、次のように書きます。

(define (runtime)
  (use srfi-11)
  (let-values (((a b) (sys-gettimeofday)))
              (+ (* a 1000000) b)))

(print (runtime))

let-valuesはsrfi-11で定義されており、手続きが返す複数の値を受け取ります。この例ではsys-gettimeofdayが秒数とマイクロ秒を返し、それをaとbが受けています。


もしくは、srfi-19をuseして、次のように書くこともできます。

(use srfi-19)

(define (time-check repeat-times start-time)
       (cond   ((= repeat-times 0) (print (time-difference (current-time) start-time)))
                       (else
                               (time-check (- repeat-times 1) start-time)
                       )
       )
)

(time-check 9999999 (current-time))

この例では、(current-time)で現在の時間を取得し、time-differenceで時間差を計算します。

問題1.24


問題1.22のtimed-prime-test手続きをfast-prime?(Fermat法参照)を使うように変え,その問題で見つけた12個の素数をテストせよ.Fermatテストはθ(log n)の増加なので,1000000近くの素数をテストする時間を1000近くの素数をテストする時間と比べ,どの位と予想するか.データはその予想を支持するか.違いがあれば説明出来るか.


コード(勢いで書いたので、後でもう少しちゃんと考える)

(use slib)
(use srfi-19)
(load "/usr/local/lib/slib/random.scm")

(define (expmod base exp m)
;  (print "base: " base ", exp: " exp ", m: " 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) 1)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else 0)))

(define (square x) (* x x))

(define (fast-prime-wrap from n)
  (cond ((= n 0) 1)
        ((fermat-test from)
            (print from " is prime")
            (fast-prime-wrap (+ from 1) (- n 1))
        )
        (else (fast-prime-wrap (+ from 1) n))
  )
)

(define (fast-prime-wrap-time from n start-time)
  (fast-prime-wrap from n)
  (print (time-difference (current-time) start-time))
)

(fast-prime-wrap-time 1000 3 (current-time))
(fast-prime-wrap-time 10000 3 (current-time))
(fast-prime-wrap-time 100000 3 (current-time))

問題文。


Exercise 1.13. Prove that Fib(n) is the closest integer to n/5, where = (1 + 5)/2. Hint: Let = (1 - 5)/2. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = (n - n)/5.


解は添付画像の通り(2008/03/24の勉強会のサマリはこれからまとめます)。

明日(2008/03/24)の勉強会に備えて、少し過去の問題を解いています。


問題文。


Exercise 1.11. A function f is defined by the rule that f(n) = n if n 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.


再帰的に実現するコード。

(define (f n)
  (cond ((< n 3) n)
        (else (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))
        )
  )
)

(print (f 2))
(print (f 3))
(print (f 4))
(print (f 5))
(print (f 10))

反復的に実現するコード。

(define (f-iter n)
  (define (iter a b c count)
    (cond ((= count 0) c)
          ((= count 1) b)
          (else (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))
  (iter 2 1 0 n)
)

(print (f-iter 2))
(print (f-iter 3))
(print (f-iter 4))
(print (f-iter 5))
(print (f-iter 10))