SchemeまたはCommon Lispのニュートン平方根法

Question

私はこのプログラムでエラーを理解することができません。これがSchemeのバージョンです。私はCommon Lispバージョンも試しました。どちらの場合も、プログラムは実行されずに実行されます。助けてください。

(define (sqrt1 x) 

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

    (define (isGoodEnough g x) 
     (< (abs (- (square g) (square x))) 0.01)) 

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

    (define (improvedGuess g x) 
     (average g (/ x g))) 

    (define (sqrt-iter g x) 
     (if (isGoodEnough g x) 
      g 
      (sqrt-iter (improvedGuess g x) x))) 

    (sqrt-iter 1.0 x)) 

Answer 1

isGoodEnoughはバグがあります。あなたは現在の推測gと数字xを二乗しています。しかし、gはxの平方根であると仮定されているので、それらを両方とも正方形にすると決して接近しません。あなたは、推測を正方形にする必要があります。

(define (isGoodEnough g x) 
    (< (abs (- (square g) x)) 0.01)) 

Answer 2

あなた自身で問題を見つけることができます。私はあなたにそれを行う方法を示します。私はLispWorksを使用しますが、ほとんどのLisp実装と同様の方法で動作します。

これは、Common Lispでは、あなたのコードです：

(defun square (x) 
    (* x x)) 

(defun isGoodEnough (g x) 
    (< (abs (- (square g) 
      (square x))) 
    0.01)) 

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

(defun improvedGuess (g x) 
    (average g (/ x g))) 

(defun sqrt-iter (g x) 
    (if (isGoodEnough g x) 
     g 
    (sqrt-iter (improvedGuess g x) x))) 

(defun sqrt1 (x) 
    (sqrt-iter 1.0 x)) 

私は今LispWorksでコードが評価されました。

はのは2.0の平方根を計算してみましょう：

CL-USER 8 > (sqrt1 2.0) 

LispWorksは、スタックオーバーフローを与えるが、それは無限ループにあった場合、我々はそれを手動で中断している可能性：

Stack overflow (stack size 53998). 
    1 (continue) Extend stack by 50%. 
    2 (abort) Return to level 0. 
    3 Return to top loop level 0. 

Type :b for backtrace or :c <option number> to proceed. 
Type :bug-form "<subject>" for a bug report template or :? for other options. 

CL-USER 9 : 1 >プロンプトです。パッケージCL-USERでは、9つのフォームがリスナーとブレイクループレベル1で評価されます。

CL-USER 9 : 1 > :bq 

ERROR <- AVERAGE <- IMPROVEDGUESS <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER 
<- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER 
<- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER 
... 
<- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER 
<- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- EVAL 
<- CAPI::CAPI-TOP-LEVEL-FUNCTION <- CAPI::INTERACTIVE-PANE-TOP-LOOP 
<- MP::PROCESS-SG-FUNCTION 

:nは、次のスタックフレームに移動するためのコマンドです：

:bqは、迅速なバックトレースの概要ためのコマンドです。

CL-USER 10 : 1 > :n 
Interpreted call to AVERAGE 

CL-USER 11 : 1 > :n 
Interpreted call to IMPROVEDGUESS 

CL-USER 12 : 1 > :n 
Interpreted call to SQRT-ITER 

:vは、そのスタックフレームの変数値を調べるコマンドです。この関数と次のフレームを見て、関数がどのように呼び出されたかを確認します。

CL-USER 13 : 1 > :v 
Interpreted call to SQRT-ITER: 
    G : 1.4142135     ; current guess 
    X : 2.0 

CL-USER 14 : 1 > :n 
Interpreted call to SQRT-ITER 

CL-USER 15 : 1 > :v 
Interpreted call to SQRT-ITER: 
    G : 1.4142135     ; prior guess 
    X : 2.0 

したがって、現在の推測値と以前の推測値は同じです。あなたのコードで

ルック：

(defun sqrt-iter (g x) 
    (if (isGoodEnough g x) 
     g 
    (sqrt-iter (improvedGuess g x) x))) 

この再帰呼び出しは推測が十分でない場合にのみ発生します。

CL-USER 16 : 1 > (isgoodenough 1.4142135 2.0) 
NIL 

をしかし推測が十分に実際に良いですので、それは、Tのようになります。 現在の値を使用して、それを確認してください。 バグがあります！コードを見てみましょう：

(defun isGoodEnough (g x) 
    (< (abs (- (square g) 
      (square x))) 
    0.01)) 

まあ、あなたは二乗しています。 1.4142135および2.0。それは間違っている。今LispWorksはクールです

CL-USER 18 : 1 > (isgoodenough 1.4142135 2.0) 
T 

とあなたが:resコマンドを使用して現在の通話(sqrt-iter 1.4142135 2.0)を再起動してみましょう：

CL-USER 17 : 1 > (defun isGoodEnough (g x) 
        (< (abs (- (square g) 
           x)) 
         0.01)) 
ISGOODENOUGH 

確認しますのは、 `のxの値を二乗しないようにそれを変更してみましょう

CL-USER 19 : 1 > :res 
1.4142135 

CL-USER 20 > 

十分な結果が得られ、LispWorksはトップレベルに戻る：1.4142135です。