Scheme - 高階手続きによる抽象(値として返される手続き(平均緩和とn乗根を近似する手続きの実装))

計算機プログラムの構造と解釈
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.3(高階手続きによる抽象)、1.3.4(値として返される手続き)、Newton法、抽象と第一級手続き、問題 1.45.を解いてみる。

その他参考書籍

問題 1.45.

実験。

コード(BBEdit, Emacs)

sample.scm

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

;; これまでに書いた手続き
(load "./procedures.scm")

(define (n-root-test n c)
  (fixed-point ((repeated average-damp c)
  (lambda (y)
    (/ (expt 2 n)
       (expt y
      (- n 1)))))
        1.0))

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

gosh> n-root-test
gosh> (n-root-test 2 1)
2.000000000000002
gosh> (n-root-test 3 1)
1.9999981824788517
gosh> (n-root-test 4 1)
  C-c C-c*** UNHANDLED-SIGNAL-ERROR: unhandled signal 2 (SIGINT)
Stack Trace:
_______________________________________
  0  ((real? x) (cond ((real? y) (%expt x y)) ((number? y) (* (%expt x  ...
        At line 158 of "/opt/local/share/gauche-0.9/0.9.3.3/lib/gauche/numerical.scm"
  1  (expt y (- n 1))
        At line 412 of "(stdin)"
  2  f

  3  f

gosh> (n-root-test 4 2)
2.0000000000021965
gosh> (n-root-test 5 2)
2.000001512995761
gosh> (n-root-test 6 2)
2.0000029334662086
gosh> (n-root-test 7 2)
2.0000035538623377
gosh> (n-root-test 8 2)
  C-c C-c*** UNHANDLED-SIGNAL-ERROR: unhandled signal 2 (SIGINT)
Stack Trace:
_______________________________________
  0  (expt y (- n 1))
        At line 412 of "(stdin)"
  1  f

  2  f

  3  f

gosh> (n-root-test 8 3)
2.0000000000039666
gosh> (n-root-test 9 3)
1.9999997106840102
gosh> (n-root-test 10 3)
2.000001183010332
gosh> (n-root-test 11 3)
1.999997600654736
gosh> (n-root-test 12 3)
1.9999976914703093
gosh> (n-root-test 13 3)
2.0000029085658984
gosh> (n-root-test 14 3)
1.9999963265447058
gosh> (n-root-test 15 3)
2.0000040951543023
gosh> (n-root-test 16 3)
  C-c C-c*** UNHANDLED-SIGNAL-ERROR: unhandled signal 2 (SIGINT)
Stack Trace:
_______________________________________
  0  f

gosh> (n-root-test 16 4)
2.000000000076957
gosh> (n-root-test 17 4)
2.0000000561635765
gosh> (n-root-test 18 4)
2.0000005848426476
gosh> (n-root-test 19 4)
2.0000003649180282
gosh> (n-root-test 20 4)
1.999999063225966
gosh> (n-root-test 21 4)
2.000001254054255
gosh> (n-root-test 22 4)
1.9999986334227027
gosh> (n-root-test 23 4)
1.999997131591442
gosh> (n-root-test 24 4)
1.999997814692085
gosh> (n-root-test 25 4)
1.9999977429539468
gosh> (n-root-test 26 4)
1.999997554120725
gosh> (n-root-test 27 4)
1.9999966641661142
gosh> (n-root-test 28 4)
1.999995794390521
gosh> (n-root-test 29 4)
1.9999957104786472
gosh> (n-root-test 30 4)
2.0000044907654058
gosh> (n-root-test 31 4)
1.9999951809750391
gosh> (n-root-test 32 4)
  C-c C-c*** UNHANDLED-SIGNAL-ERROR: unhandled signal 2 (SIGINT)
Stack Trace:
_______________________________________
  0  f

  1  f

gosh> (n-root-test 32 5)
2.000000000000006
gosh>

実験結果
n乗根	平均緩和回数
2	1
3	1
4	2
5	2
6	2
7	2
8	3
9	3
10	3
11	3
12	3
13	3
14	3
15	3
16	4
17	4
18	4
19	4
20	4
21	4
22	4
23	4
24	4
25	4
26	4
27	4
28	4
29	4
30	4
31	4
32	5

平均緩和回数について、1回増えるまで2、4、8、16(2の1乗、2の2乗、2の3乗、2の4乗)という間隔なっている。この実験結果から、n乗根を近似する為の平均緩和回数は、

[log2 n]

と予測できる。

このことからn乗根を計算する単純な手続きを実装。

sample.scm

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

;; これまでに書いた手続き
(load "./procedures.scm")

(define (n-root n x)
  (fixed-point ((repeated average-damp
     (floor (log n
          2)))
  (lambda (y)
    (/ x
       (expt y
      (- n 1)))))
        1.0))

(for-each (lambda (n)
     (define y (n-root n 100))
     (print 100 "の" n "乗根: " y
     " (" y "の" n "乗: " (expt y n) ")"))
   '(1 2 3 4 5 6 7 8 9 10))

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

gosh> 100の1乗根: 100.0 (100.0の1乗: 100.0)
100の2乗根: 10.0 (10.0の2乗: 100.0)
100の3乗根: 4.641585829030015 (4.641585829030015の3乗: 99.99980580480566)
100の4乗根: 3.162277660168379 (3.162277660168379の4乗: 99.99999999999997)
100の5乗根: 2.5118850413846463 (2.5118850413846463の5乗: 99.99972329095421)
100の6乗根: 2.1544323047105944 (2.1544323047105944の6乗: 99.99933570099907)
100の7乗根: 1.9307017486395444 (1.9307017486395444の7乗: 100.00145742491912)
100の8乗根: 1.7782794100800858 (1.7782794100800858の8乗: 100.00000001851814)
100の9乗根: 1.6681003815774011 (1.6681003815774011の9乗: 99.99991603603233)
100の10乗根: 1.584892548296255 (1.584892548296255の10乗: 99.99959356019488)
#<undef>
gosh>

Kamimura's blog

ほしい物リスト

2014年3月2日日曜日

Scheme - 高階手続きによる抽象(値として返される手続き(平均緩和とn乗根を近似する手続きの実装))

0 コメント:

コメントを投稿