2008-11-19

SICPの宿題

SICP

問題1.19

Tをn回作用させた時のa, bを $a_{n}, b_{n}$ とすると $a_{n+1}, b_{n+1}$ は
$a_{n+1} = b_{n}q + a_{n}q + a_{n}p$
$b_{n+1} = b_{n}p + a_{n}q$
となる。
さらに、もう一回Tを作用させたとき $a_{n+2}, b_{n+2}$ は
$a_{n+2}$
$= b_{n+1}q + a_{n+1}q + a_{n+1}p$
$= (b_{n}p + a_{n}q)q + (b_{n}q + a_{n}q + a_{n}p)q + (b_{n}q + a_{n}q + a_{n}p)p$
$= b_{n}(2pq + q^{2}) + a_{n}(2pq + q^{2}) + a_{n}(p^{2} + q^{2})$
$b_{n+2}$
$= b_{n+1}p + a_{n+1}q$
$= (b_{n}p + a_{n}q)p + (b_{n}q + a_{n}q + a_{n}p)q$
$= b_{n}(p^{2} + q^{2}) + a_{n}(2pq + q^{2})$
これから
$p' = p^{2} + q^{2}, q' = 2pq + q^{2}$
とすると、 $T_{pq}$ を２回作用させるのは、 $T_{p'q'}$ を１回作用させるのと同じになる。

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

(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
                   (+ (square p) (square q)) ;; p'
                   (+ (* 2 p q) (square q))  ;; q'
                   (/ count 2))]
        [else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1))]))

実行結果

gosh> (fib 3)
2
gosh> (fib 4)
3
gosh> (fib 5)
5
gosh> (fib 6)
8
gosh> (fib 7)
13
gosh> (fib 8)
21

2008-11-09

SICPの宿題

SICP

問題1.14がワカラナイヨ。
明日の答え合わせで教えてもらおう。

問題1.16

;; if n is even, procedure returns true, otherwise false.      
(define (even? n)
  (= (remainder n 2) 0))

;; ex1.16 procedure "fast-expt and fast-expt-iter"                                         
(define (fast-expt x n)
  (fast-expt-iter x n 1))

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

問題1.17

;; double                                                      
(define (double n)
  (+ n n))

;; halve                                                       
(define (halve n)
  (/ n 2))

;; ex1.17 procedure "fast-mult"                                
(define (fast-mult x n)
  (cond [(= n 0) 0]
        [(= n 1) x]
        [(even? n) (fast-mult (double x) (halve n))]
        [else (+ x (fast-mult x (- n 1)))]))

問題1.18

;; ex1.18 procedure "fast-mult and fast-mult-iter"             
(define (fast-mult x n)
  (fast-mult-iter x n 0))

(define (fast-mult-iter x n a)
  (cond [(= n 0) a]
        [(even? n) (fast-mult-iter (double x) (halve n) a)]
        [else (fast-mult-iter x (- n 1) (+ x a))]))

2008-10-30

問題1.13

SICP 証明

gabuchan : 「さあ、証明するのだ」
babanban : 「yes master」

証明スタート
$\phi = (1 + \sqrt{5})/2, \psi = (1 - \sqrt{5})/2$ として
$Fib(n) = (\phi^{n} - \psi^{n})/\sqrt{5}$ が０を含む全ての自然数について成り立つことをnに関する数学的帰納法をつかって証明する。
基底
n = 0 のとき
Fib(0) = 0
$(\phi^{0} - \psi^{0})/\sqrt{5} = 0$ より成り立つ
n = 1 のとき
Fib(1) = 1
$(\phi^{1} - \psi^{1})/\sqrt{5} = 1$ より成り立つ
帰納段階
Fib(n) = Fib(n-1) + Fib(n-2)
ここで帰納法の仮定を使って
Fib(n-1) = $(\phi^{n-1} - \psi^{n-1})/\sqrt{5}$
Fib(n-2) = $(\phi^{n-2} - \psi^{n-2})/\sqrt{5}$
がいえる。
Fib(n)
= Fib(n-1) + Fib(n-2)
= $\frac{\phi^{n-1} - \psi^{n-1}}{\sqrt{5}} + \frac{\phi^{n-2} - \psi^{n-2}}{\sqrt{5}}$
= $\frac{\phi^{n-2}(\phi + 1) - \psi^{n-2}(\psi + 1)}{\sqrt{5}$
( $\phi^{2} = \phi + 1, \psi^{2} = \psi + 1$ より)
= $\frac{\phi^{n-2}*\phi^{2} - \psi^{n-2}*\psi^{2}}{\sqrt{5}}$
= $\frac{\phi^{n} - \psi^{n}}{\sqrt{5}}$
よって成り立つ
証明終了

（一口メモ）
今回は帰納法の仮定を使うときにn-1とn-2が必要になるので基底ではn=0とn=1の２つの場合が成り立つことを証明しなくちゃいけない。

2008-10-27

SICPの宿題

SICP

こつこつやろうということで今日は問題1.13を解きました。
証明問題だからちょっとあせったけど、ヒント通りにやればできました。というかヒントなしじゃできませんでした。
答えを書こうとしたけど、tex記法のフォントが気に入らなかったのでやめました。

2008-10-12

CSNagoyaの宿題

CSNagoya sml compiler

皆さんがんばって実装しているみたいなので僕も、今回smlでスキャナを実装した。
Gaucheは後回し。すいません。
でも、関数型で実装するイメージはこれでだいぶつかんだと思う。
TextIOモジュールのlookaheadは先読みする関数なので、これを使えば１文字ずつ読み込んでいくスタイルでも難なく実装できた。
とはいえ、けっこう手抜きなところがあって申し訳ないですが。
次回の勉強会ではパーサの実装に入る予定なので、それまでに、Gauche版スキャナを実装せねば。。。

datatype token =
    EOF
  | IDENT of string    | NUMBER of string
  | STR of string
  | MODULE of string   | BEGIN of string
  | END of string      | VAR of string
  | INTEGER of string  | STRING of string
  | IF of string       | THEN of string
  | ELSE of string     | WHILE of string
  | DO of string
  | OPEN    | CLOSE  | PERIOD
  | COMMA   | COLON  | SEMICOLON
  | EQ      | MINUS  | PLUS
  | MULT    | DIV    | LT
  | LE      | GT     | GE
  | NE      | MYASSIGN
  | UNKNOWN


structure T = TextIO
fun skipSpaces ins =
    case T.lookahead ins of
        SOME c => (if Char.isSpace c
                        then (T.input1 ins;skipSpaces ins)
                   else ())
      |  _     => ()

fun getID ins =
    let fun getRest s =
        case T.lookahead ins of
            SOME c => (if Char.isAlphaNum c then getRest (s ^ T.inputN(ins,1))
                       else s)
          | _ => s
    in IDENT(getRest "")
    end


fun isReserved (IDENT(str)) =
    case str of
        "MODULE"  => MODULE(str)
      | "BEGIN"   => BEGIN(str)
      | "END"     => END(str)
      | "VAR"     => VAR(str)
      | "INTEGER" => INTEGER(str)
      | "STRING"  => STRING(str)
      | "IF"      => IF(str)
      | "THEN"    => THEN(str)
      | "ELSE"    => ELSE(str)
      | "WHILE"   => WHILE(str)
      | "DO"      => DO(str)
      | _         => IDENT(str)


fun getNum ins =
    let fun getRest s =
        case T.lookahead ins of
            SOME c => (if Char.isDigit c then getRest (s ^ T.inputN(ins,1))
                       else s)
          | _ => s
    in NUMBER(getRest "")
    end
fun getStr ins =
    let fun getRest s =
        case valOf(T.input1 ins) of
            #"\"" => s
          | c => getRest(s ^ str c)
    in STR(getRest "")
    end

fun lex ins =
    (skipSpaces ins;
     if T.endOfStream ins then EOF
     else let val c = valOf(T.lookahead ins)
          in if Char.isDigit c then getNum ins
             else if Char.isAlpha c then isReserved(getID ins)
                  else case valOf (T.input1 ins) of
                      #"+"  => PLUS
                    | #"-"  => MINUS
                    | #"*"  => MULT
                    | #"/"  => DIV
                    | #"="  => EQ
                    | #"<"  => LT
                    | #">"  => GT
                    | #":"  => COLON
                    | #";"  => SEMICOLON
                    | #","  => COMMA
                    | #"("  => OPEN
                    | #")"  => CLOSE
                    | #"."  => PERIOD
                    | #"\"" => getStr ins
                    | _ => UNKNOWN
          end)


fun toString (IDENT(str)) = "ID(" ^ str ^ ")"
  | toString (NUMBER(str)) = "NUMBER(" ^ str ^ ")"
  | toString (STR(str)) = "STR(" ^ str ^ ")"
  | toString (MODULE(str)) = "MODULE(" ^ str ^ ")"
  | toString (BEGIN(str)) = "BEGIN(" ^ str ^ ")"
  | toString PLUS = "PLUS"
  | toString MINUS = "MINUS"
  | toString MULT = "MULT"
  | toString DIV = "DIV"
  | toString EQ = "EQ"
  | toString LT = "LT"
  | toString RT = "RT"

fun testLex () =
    let val token = lex TextIO.stdIn
        in case token of
            EOF => ()
          | _ => (print (toString token ^ "\n"); testLex())
    end

2008-10-07

プログ開設

軽い気持ちではじめました。
今日バイトの面接に行ってきました。

あっれー？C言語全然書けないじゃんワタシ！！
なんかすっごい冷や汗かいちゃいましたw
こんなんでバイト大丈夫なんかなー？

で、今日からjavaのお勉強（焦り気味）
でもSICPへの意欲はまだまだアルヨ！

CSNagoyaの宿題であるscannerは…gabuさんのがあるからokでしょ！
暇ができたらSMLで実装して紹介できたらいいなー。