問題1.8、traceの使い方 – SICP(計算機プログラムの構造と解釈)その3

問題1.8

立方根(cube root)を求める。

(define (cube x)
  (* x x x))

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

(define (improve guess x)
  (/ (+ (/ x (square guess)) (* guess 2.0))
     3.0))

(define (cube-root-iter old-guess new-guess x)
  (if (good-enough? old-guess new-guess)
      new-guess
      (cube-root-iter new-guess (improve new-guess x) x)))

(define (good-enough? old-guess new-guess)
  (< (abs (- 1.0 (/ old-guess new-guess))) 0.001))

(define (cube-root x)
  (cube-root-iter 1.0 x x))

(cube-root 27)              ;=> 3.0000000017936714
(cube (cube-root 27))       ;=> 27.000000048429133

(cube-root 1.0E29)          ;=> 4.641589185026574e9
(cube (cube-root 1.0E29))   ;=> 1.0000002271294386e29

(cube-root 1.0E-6)          ;=> 0.010000000334749248
(cube (cube-root 1.0E-6))   ;=> 1.0000001004247776e-6

最初 improve で整数を使っていたら結果が有理数で返されてしまった。

improve で整数を使った場合。

(define (improve guess x)
  (/ (+ (/ x (square guess)) (* guess 2))
     3))

(cube-root 3) の結果。

gosh> #<undef>
gosh> #t
gosh> cube
gosh> square
gosh> improve
gosh> cube-root-iter
gosh> good-enough?
gosh> cube-root
gosh> #<closure (debug:trace-procedure debug:trace-procedure)>
gosh> CALL cube-root-iter 1.0 3 3
 CALL cube-root-iter 3 19/9 3
  CALL cube-root-iter 19/9 15905/9747 3
   CALL cube-root-iter 15905/9747 10824956912...7067260025 3
    CALL cube-root-iter 10824956...67260025 37511574...10947075 3
    RETN cube-root-iter 1583162344821038103589218638...3589076502821120648922370025
   RETN cube-root-iter 1583162344821038103589218638...3589076502821120648922370025
  RETN cube-root-iter 1583162344821038103589218638...3589076502821120648922370025
 RETN cube-root-iter 1583162344821038103589218638...3589076502821120648922370025
RETN cube-root-iter 1583162344821038103589218638...3589076502821120648922370025
158316234482103810358921863846157439441584532483589206734151913384891198442912501439920896569868995865798255520305085939/109770341197480813007589900424274738795165183741146886962733210716527447498666221135500807603589076502821120648922370025
gosh> 

improve で小数を使った場合。

(define (improve guess x)
  (/ (+ (/ x (square guess)) (* guess 2.0))
     3.0))

(cube-root 3) の結果。

gosh> #<undef>
gosh> #t
gosh> cube
gosh> square
gosh> improve
gosh> cube-root-iter
gosh> good-enough?
gosh> cube-root
gosh> #<closure (debug:trace-procedure debug:trace-procedure)>
gosh> CALL cube-root-iter 1.0 3 3
 CALL cube-root-iter 3 2.111111111111111 3
  CALL cube-root-iter 2.111111111111111 1.6317841387093466 3
   CALL cube-root-iter 1.6317841387093466 1.463411989089094 3
    CALL cube-root-iter 1.463411989089094 1.442554125137959 3
    RETN cube-root-iter 1.4422496346010913
   RETN cube-root-iter 1.4422496346010913
  RETN cube-root-iter 1.4422496346010913
 RETN cube-root-iter 1.4422496346010913
RETN cube-root-iter 1.4422496346010913
1.4422496346010913
gosh> 

trace の使い方

trace の使い方については、
関数型言語の勉強にSICPを読もう – (6) 1章 – 小休止 traceを使えるようにする – ひげぽん OSとか作っちゃうかMona-
404 Blog Not Found:scheme – traceとslib
を参考にした。
いつインストールしたのか覚えてないが slib はすでにインストール済みだった。

(use slib)
(require 'trace)
...略...
(trace cube-root-iter)
(cube-root 3)
計算機プログラムの構造と解釈
ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542
«
»