Hatena::Groupsicp

yharaの日記

参考リンク

2007-05-03

[].7 21:02

「差が0.001以下」で判定すると、

  1. 非常に小さい数の平方根を取ると、必ず1回目で再帰が終わる
  2. 非常に大きい数の平方根を取ると、差がなかなか収束しなくなる

という問題がありそう。

sqrt-iterデバッグプリントを仕込んで実験してみる。

1.7.scm

(define (sqrt-iter guess x)
  (print #`"sort-iter: ,guess ,x")
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))
;あとは1.6.scmといっしょ

非常に小さい数のsqrtを求めるとどうなるか。

yhara@meteor:~/src/sicp % gosh
gosh> (load "./1.7.scm")
#t
gosh> (sqrt 0.000000001)
sort-iter: 1.0 1.0e-9
sort-iter: 0.5000000005 1.0e-9
sort-iter: 0.25000000125 1.0e-9
sort-iter: 0.125000002625 1.0e-9
sort-iter: 0.06250000531249991 1.0e-9
sort-iter: 0.03125001065624928 1.0e-9
0.03125001065624928
gosh>

√0.000000001 が 0.03 に^^;

しかし「再帰が1回~」は嘘だったな。「近似の精度が落ちる」が正解か。

今度は大きい方。

gosh> (sqrt 100000000)
sort-iter: 1.0 100000000
sort-iter: 50000000.5 100000000
sort-iter: 25000001.24999999 100000000
sort-iter: 12500002.624999894 100000000
sort-iter: 6250005.312499107 100000000
sort-iter: 3125010.6562427534 100000000
sort-iter: 1562521.328066817 100000000
sort-iter: 781292.6635966157 100000000
sort-iter: 390710.3283034968 100000000
sort-iter: 195483.13619747627 100000000
sort-iter: 97997.34463768976 100000000
sort-iter: 49508.89022510405 100000000
sort-iter: 25764.364740575656 100000000
sort-iter: 14822.847335384222 100000000
sort-iter: 10784.594750729779 100000000
sort-iter: 10028.540197249 100000000
sort-iter: 10000.040611237677 100000000
sort-iter: 10000.000000082462 100000000
sort-iter: 10000.0 100000000

うーん、収束が遅い…とは言えないか?

続きはあとで書く

[].6 21:02

制御構造を自分で定義できるか?の話。Schemeでは引数が先に評価されるので、

new-ifを呼び出す*前に*sqrt-iterが呼ばれてしまい無限ループになる。

試してみよう。(書籍内のコードhttp://mitpress.mit.edu/sicp/code/index.htmlコピペすると楽です)

1.6.scm

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

;(define (sqrt-iter guess x)
;  (if (good-enough? guess x)
;      guess
;      (sqrt-iter (improve guess x)
;                 x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))

(define (new-if predicate then-clause else-clause)
    (cond (predicate then-clause)
              (else else-clause)))

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x)
                     x)))

この定義で√5を求めてみる。

yhara@meteor:~/src/sicp % rlwrap gosh
gosh> (load "./1.6.scm")
#t
gosh> (sqrt 5.0)
(帰ってこないのでCtrl-cを押す)
*** ERROR: unhandled signal 2 (SIGINT)
Stack Trace:
_______________________________________
  0  (* x x)
        At line 1 of "./1.6.scm"
  1  (square guess)
        At line 16 of "./1.6.scm"
  2  (abs (- (square guess) x))
        At line 16 of "./1.6.scm"
  3  (good-enough? guess x)
        At line 26 of "./1.6.scm"
 (中略)
 29  (sqrt-iter (improve guess x) x)
        At line 28 of "./1.6.scm"
... (more stack dump truncated)
gosh>

無限ループになったようだ。

Haskellだと遅延評価なのでmy-ifが定義できる。

Schemeでもマクロを使えばmy-ifが定義できる(マクロ引数マクロ展開前に評価されない)。

[] はてなグループにはブログモードってないのかな 16:45

設定が見つからん。

[].5 16:39

CBVとCBNの話。関数を呼び出すときに、引数を先に評価するか、関数を先に評価する(?)か、という。

用語をまとめてみる。

作用的順序(applicative-order)eager値呼び(call by value, CBV)正格
正規順序(normal-order)lazy名前呼び(call by name, CBN)非正格

世の中のほとんど言語はeagerが基本。lazyが基本の言語HaskellとかCleanとか(くらいしか知らない)。

さて、(test 0 (p)は作用的順序だと

(test 0 (p))
→ (test 0 (p))
→ (test 0 (p))
→ (test 0 (p))
...

無限ループになってしまう。

goshで確かめてみよう。

yhara@meteor:~/src/sicp % gosh
gosh> (define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))
p
gosh> test
gosh> (test 0 (p))


無限ループしているようだ。

正規順序だと、

(test 0 (p))
→ (if (= 0 0) 0 (p))
→ 0

のように計算が停止する。

Haskellで確かめてみよう。

1.5.hs

p = p
test x y = if x == 0 then x else y

main = print $ test 0 p
yhara@meteor:~/src/sicp % runhugs 1.5.hs
0

ちゃんと停止したようだ。


[].4 16:03

((if (> b 0) + -) a b) みたいに書ける、という話。+ - なんての書いたことはないけど、

確かに動くなぁ。

これが「関数ファーストクラス」の力だ。

Haskellでも似たような書き方ができるね。

(if b>0 then (+) else (-)) a b

Rubyだと関数そのものはファーストクラスではないのでcallをつける必要がある。

(if b>0 
  proc{|a,b| a+b}
 else
  proc{|a,b| a-b}
 end).call(a, b)

あとHaskellの(+)みたいな書き方はできない。

いや、Object#methodでメソッドを取り出すことはできるんだけど、

RubyのInteger#+は1引数なんでうまく行かない(0.method(:+)のように、+の片側が固定

されてしまう)。

ちょっと違うやり方になるけど、__send__を使う方がRubyらしいかもな。

a.__send__(if b>0 then :+ else :- end, b)

[].3 15:34

テストファーストするよ。

1.3.scm:

(define (sum-of-squares-of-biggest-two a b c)
  0)

test-1.3.scm:

(use gauche.test)
(load "./1.3.scm")

(test-start "1.3")
(test* "test1"
       13
       (sum-of-squares-of-biggest-two 1 2 3))
(test* "test2"
       (+ 25 36)
       (sum-of-squares-of-biggest-two 6 4 5))
(test-end)

実行結果:

yhara@meteor:~/src/sicp % gosh test-1.3.scm
Testing 1.3 ...
test test1, expects 13 ==> ERROR: GOT 0
test test2, expects 61 ==> ERROR: GOT 0
failed.
discrepancies found.  Errors are:
test test1: expects 13 => got 0
test test2: expects 61 => got 0

正しく失敗した模様。

1.3.scmをちゃんと実装するよ。

(define (sum-of-squares-of-biggest-two a b c)
  (let1 sorted (sort (list a b c))
        (+ (expt (car sorted) 2)
           (expt (cadr sorted) 2))))

こんなんでどうでしょ。(あんまり、綺麗でも速そうでもないけど…。) exptは累乗ね。

yhara@meteor:~/src/sicp % gosh test-1.3.scm
Testing 1.3 ...
test test1, expects 13 ==> ERROR: GOT 5
test test2, expects 61 ==> ERROR: GOT 41
failed.
discrepancies found.  Errors are:
test test1: expects 13 => got 5
test test2: expects 61 => got 41

ありゃ?

ああ、sortは小さい順に並ぶんだっけ。

(define (sum-of-squares-of-biggest-two a b c)
  (let1 sorted (sort (list a b c) >)
        (+ (expt (car sorted) 2)
           (expt (cadr sorted) 2))))

これでどうだ。

yhara@meteor:~/src/sicp % gosh test-1.3.scm
Testing 1.3 ...
test test1, expects 13 ==> ok
test test2, expects 61 ==> ok
passed.

OKのようです。


[].2 15:24

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
   (* 3 (- 6 2) (- 2 7)))

こんな感じで。

確か、Schemeでは完全数(exact number)と不完全数(inexact number)は区別されるんだよね。

有理数(分数、誤差なし)と少数(誤差あり)ってことかな。

(/ 4 5)はどっちなんだろ。

yhara@meteor:~/src/sicp % gosh
gosh> (/ 4 5)
0.8

あれ、少数なのか。

っていうかCtrl-pが効かねぇ(^^; rlwrapしないと。

yhara@meteor:~/src/sicp % rlwrap gosh
gosh> (/ 4 5)
0.8
gosh> (/ 1 3)
0.3333333333333333
gosh> (exact? (/ 1 3))
#f
gosh> (exact? 1/3)
#f

「/」は不完全数を返すみたい。完全数の「3分の1」を求めるにはどうすればいいのかな?

http://www.shiro.dreamhost.com/scheme/gauche/man/?l=jp&p=%2f

註:0.8.8までGaucheは正確な有理数サポートしておらず、それ以前は除数と被除数がともに正確な数であっても商が整数にならなければ結果は非正確な数へと変換されていました。今のGaucheはそうではありません。

しまった、使っているGaucheが0.8.3だった。

yhara@meteor:~/src/sicp % gosh -V
Gauche scheme interpreter, version 0.8.3 [utf-8,pthreads]

[].1 14:45

上から順に

10
12
8
3
6
(処理系依存) a=3
(処理系依存) b=4
19
#f
4 ((> b a)は#tで、(< b (* a b))も#tなので)
16
6
16

だろ?


MITの原文( http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-10.html#%_sec_1.1.6 )をgoshにコピペしてみる。

yhara@meteor:~/src/sicp % gosh
gosh> 10
10
gosh> (+ 5 3 4)
12
gosh> (- 9 1)
8
gosh> (/ 6 2)
3
gosh> (+ (* 2 4) (- 4 6))
6
gosh> (define a 3)
a
gosh> (define b (+ a 1))
b
gosh> (+ a b (* a b))
19
gosh> (= a b)
#f
gosh> (if (and (> b a) (< b (* a b)))
    b
    a)
4
gosh> (cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
16
gosh> (+ 2 (if (> b a) b a))
6
gosh> (* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1))
16
gosh>

合ってたみたい。

ChristianaChristiana2012/01/10 09:33That's more than snebsile! That's a great post!

sgiodkkfjgssgiodkkfjgs2012/01/10 19:14Gv8tkW <a href="http://cjqpfjauqswr.com/">cjqpfjauqswr</a>

ntfhyvcwntfhyvcw2012/01/12 22:54TKFix7 <a href="http://egvshzpudncy.com/">egvshzpudncy</a>