Scheme - 手続きによる抽象の構築(Newton法による平方根)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田英一 (翻訳)

開発環境

OS X Mavericks - Apple(OS)
Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
Scheme (プログラミング言語)
Gauche (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の1(手続きによる抽象の構築)、1.1(プログラミングの要素)、1.1.7(例: Newton法による平方根)、問題 1.7.を解いてみる。

その他参考書籍

問題 1.7.

非常に小さい数の場合は、good-enough?手続きで、すぐに前もって決めた許容値より小さくなるため、あまり答えを改善することが出来ないのでテストは失敗する。

非常に大きい数の場合は、限られた精度で実行されるために、improve手続きのaverage手続きの(/x guess)の計算結果の精度が落ちていき(guessは減少していき、xは非常に大きな一定の値、よって(/ x guess)は非常に大きな値になっていく、つまり精度は落ちていく)一定の値になり、循環してテストは失敗する。

非常に小さい値、1e-50(平方根1e-25)と非常に大きい値、1e+50(平方根1e+25)で確認。

コード(BBEdit, Emacs)

sample.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

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

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

a$ gosh
gosh> (load "./sample.scm")
#t
gosh> (sqrt 1e-50)

1.0e-50

2.0e-50

4.0e-50

8.0e-50

1.6e-49
0.03125
gosh> (sqrt 1e+50)
1.0e50

2.0

4.0

8.0

16.0

32.0

64.0

128.0

256.0

512.0

1024.0

2048.0

4096.0

8192.0

16384.0

32768.0

65536.0

131072.0

262144.0

524288.0

1048576.0

2097152.0

4194304.0

8388608.0

16777216.0

33554432.0

67108864.0

134217728.0

268435456.0

536870912.0

1.073741824e9

2.147483648e9

4.294967296e9

8.589934592e9

1.7179869184e10

3.4359738368e10

6.8719476736e10

1.37438953472e11

2.74877906944e11

5.49755813888e11

1.099511627776e12

2.199023255552e12

4.398046511104e12

8.796093022208e12

1.7592186044416e13

3.5184372088832e13

7.0368744177664e13

1.40737488355328e14

2.81474976710656e14

5.62949953421312e14

1.125899906842624e15

2.251799813685248e15

4.503599627370496e15

9.007199254740992e15

1.8014398509481984e16

3.602879701896397e16

7.205759403792794e16

1.4411518807585587e17

2.8823037615171168e17

5.764607523034229e17

1.152921504606842e18

2.3058430092136532e18

4.611686018427061e18

9.22337203685216e18

1.844674407368863e19

3.6893488147251716e19

7.378697629349909e19

1.475739525789635e20

2.951479050936495e20

5.902958096730788e20

1.1805916152323962e21

2.361183197554702e21

4.722366131828704e21

9.444730157412515e21

1.8889443464888424e22

3.7778752131005468e22

7.555642589492633e22

1.5110422559187373e23

3.021394652296521e23

6.03727797878921e23

1.2030705569220557e24

2.3718120104605807e24

4.4909840622157144e24

7.474450790154849e24

9.590780483071007e24

9.991277323943398e24

9.999996192426347e24

9.999999999999277e24

1.0e25

1.0e25

1.0e25

1.0e25

1.0e25

^C
*** UNHANDLED-SIGNAL-ERROR: unhandled signal 2 (SIGINT)
Stack Trace:
_______________________________________
  0  (print (/ x guess))
        At line 14 of "./sample.scm"
  1  (improve guess x)
        At line 9 of "./sample.scm"
1.0e25gosh>

guessの変化に注目する戦略で設計。

sample.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

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

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

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

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

(define (good-enough? guess previous-guess)
  (< (abs (- 1
             (/ guess
                previous-guess)))
     0.001))

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

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

$ gosh
gosh> (load "./sample.scm")
#t
gosh> (sqrt 1e-50)
1.0000003807575104e-25
gosh> (sqrt 1e+50)
1.0000003807575104e25
gosh> (exit)
$

Kamimura's blog

ほしい物リスト

2014年1月21日火曜日

Scheme - 手続きによる抽象の構築(Newton法による平方根)

0 コメント:

コメントを投稿