Monday, July 19, 2010

例題1.37

SICPの例題1.37。
再帰で書くのは簡単。
(define (cont-frac n d k)
  (define (recursive count)
    (if (> count k)
        0
        (/ (n count) (+ (d count) (recursive (+ count 1))))))
  (recursive 1))
反復で書くのも別に難しくは無いかな。
(define (cont-frac n d k)
  (define (iter product count)
    (if (= count 0)
        product
        (iter (/ (n count) (+ (d count) product)) (- count 1))))
  (iter 0 k))
再帰は上から、反復はしたから計算してく、と。

Friday, July 16, 2010

SICPよんでみる 1.2

計算機プログラミングの構造と解釈1.2。
ここは手続きの効率化がテーマっぽい。












Friday, July 9, 2010

ミラー・ラビン素数判定(修正)

昨日のプログラムの修正。
こっちの方が多分だいぶマシ。

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

(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 (miller-rabin-test n)
  (define (test-iter a b)
    (if (odd? b)
        (or (= (expmod a b n) (- n 1)) (= (expmod a b n) 1))
        (or (test-iter a (/ b 2))
            (= (expmod a (/ b 2) n) (- n 1)))))
  (test-iter (+ 1 (random (- n 1))) (- n 1)))

(define (good-prime? n times)
  (cond ((= times 0) true)
        ((miller-rabin-test n) (good-prime? n (- times 1)))
        (else false)))

Thursday, July 8, 2010

ミラー・ラビン素数判定

SICPの例題1.28のミラー・ラビン素数判定。
・・・一応カーマイケル数の判定にも成功するけど、コレでいいのかどうか・・・
(追記:修正しました)

同じ計算を繰り返しているところがあって、効率はあまりよくない。
一番底で-1かどうかチェックするだけでいいのか。

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

(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 (miller-rabin-test n)
  (define (test-iter a b)
    (if (odd? b)
        (= (expmod a b n) 1)
        (or (test-iter a (/ b 2))
            (and (= (expmod a b n) 1)
                 (= (expmod a (/ b 2) n) (- n 1))))))
  (test-iter (+ 1 (random (- n 1))) (- n 1)))

(define (good-prime? n times)
  (cond ((= times 0) true)
        ((miller-rabin-test n) (good-prime? n (- times 1)))
        (else false)))

Wednesday, July 7, 2010

SICPよんでみる 1.1

計算機プログラムの構造と解釈をまんがにするという誰得企画。
実は専門用語に詳しくないので、訳語がかなりおかしいかも。
まあこちらを見ておかしな言葉は脳内補完してください。














Sunday, July 4, 2010

πを計算してみた

「数学にときめく」(p.216)に書いてあったπを計算するアルゴリズムを試してみた。
…一応動いてるような気はするけど…
(define (square x) (* x x))
(define (pi-iter a b c x)
  (define (good-enough? a b)
    (< (abs (- a b)) 0.000001))
  (if (good-enough? a b)
      (/ (* (+ a b) (+ a b)) (* 4 c))
      (pi-iter (/ (+ a b) 2)
               (sqrt (* b a))
               (- c (* x (square (- (/ (+ a b) 2) a))))
               (* 2 x))))
(define pi
  (pi-iter 1 (/ 1 (sqrt 2)) (/ 1 4) 1))

Saturday, July 3, 2010

フィボナッチ数列の行列的アルゴリズム

SICPの問題1.19から
フィボナッチ数列をO(log N)で求めるプログラム。
行列をもとにした解法らしいんだけど、なんで動くのかちょっと不安。

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (* p p) (* q q))     ; compute p'
                   (+ (* 2 (* p q)) (* q q))      ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

参考になるかどうか・・・