; ======================================================================
;
;          Structure and Interpretation of Computer Programs
;                  (trial answer to excercises)
;
;                  计算机程序的构造和解释(习题试解)
;
;                                             created: code17 03/06/05
;                                             modified:
; (保持内容完整不变前提下，可以任意转载)
; ======================================================================

;; SICP No.1.36

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (display guess)
    (newline)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))


;; 方程x^x=1000的根可以这样计算，方程两面同时取自然对数
;; 得， xlog(x)=log(1000) ==> x=log(1000)/log(x)
;; 即x是 x|->log(1000)/log(x)的不动点。

;; 若采用average damping的方法，我们可以继续推导
;; x=log(1000)/log(x) ==> x+x = log(1000)/log(x) + x
;;                    ==> x = (log(1000)/log(x) + x)/2
;; 即x是 x|->(log(1000)/log(x) + x)/2的不动点
;; 不失一般性，设x是f(x)的不动点，则有 x+x = f(x)+x，
;; x=(f(x)+x)/2, 即x也是x|->(f(x)+x)/2的不动点，
;; 此为原公式的average damping公式

;; Test-it:
;; Welcome to MzScheme version 209, Copyright (c) 2004 PLT Scheme, Inc.
;;> (fixed-point (lambda (x) (/ (log 1000) (log x))) 1.5)
;; 1.5
;; 17.036620761802716
;; 2.436284152826871
;; 7.7573914048784065
;; 3.3718636013068974
;; 5.683217478018266
;; 3.97564638093712
;; 5.004940305230897
;; 4.2893976408423535
;; 4.743860707684508
;; 4.437003894526853
;; 4.6361416205906485
;; 4.503444951269147
;; 4.590350549476868
;; 4.532777517802648
;; 4.570631779772813
;; 4.545618222336422
;; 4.562092653795064
;; 4.551218723744055
;; 4.558385805707352
;; 4.553657479516671
;; 4.55677495241968
;; 4.554718702465183
;; 4.556074615314888
;; 4.555180352768613
;; 4.555770074687025
;; 4.555381152108018
;; 4.555637634081652
;; 4.555468486740348
;; 4.555580035270157
;; 4.555506470667713
;; 4.555554984963888
;; 4.5555229906097905
;; 4.555544090254035
;; 4.555530175417048
;; 4.555539351985717
;; > (fixed-point (lambda (x) (/ (+ (/ (log 1000) (log x)) x) 2)) 1.5)
;; 1.5
;; 9.268310380901358
;; 6.185343522487719
;; 4.988133688461795
;; 4.643254620420954
;; 4.571101497091747
;; 4.5582061760763715
;; 4.555990975858476
;; 4.555613236666653
;; 4.555548906156018
;; 4.555537952796512
;; 4.555536087870658
;; >

;; 测试结果表明，使用average damping的版本显然收敛得快得多。