Ньютонов метод последовательных приближений для вычисления квадратного корня

squrt-newton-method.lisp

; Ньютонов метод последовательных приближений
; для вычисления квадратного корня.
; ----
;
; Основан на том, что имея некоторое неточное значение y
; для квадратного корня из числа x, мы можем с помощью
; простой манипуляции получить более точное значение (более близкое к настоя-
; щему квадратному корню), если возьмем среднее между y и x/y.
;
; Например, мы можем вычислить квадратный корень из 2 следующим образом: предположим,
; что начальное приближение равно 1.


(define y 1.0)
(define x 2)

(define y (/ (+ y (/ x y)) 2)) ; -> 1.5
(* y y) ; -> 2.25

(define y (/ (+ y (/ x y)) 2)) ; -> 1.4166666666666665
(* y y) ; -> 2.006944444444444

(define y (/ (+ y (/ x y)) 2)) ; -> 1.4142156862745097
(* y y) ; -> 2.0000060073048824

; ...

; Продолжая этот процесс, мы получаем все
; более точные приближения к квадратному корню.

; Теперь формализуем этот процесс в терминах процедур.

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

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

(define (good-enought? guess x)
  (< (abs (- (square guess) x)) 0.001))
(define (square x) (* x x))
(define (abs x) (if (< x 0) (- x) x))

(define (improve-guess guess x) (average guess (/ x guess)))
(define (average x y) (/ (+ x y) 2))

; Проверка
(= (sqrt 4) 2.0000000929222947)

; Упражнение 1.6
;
; Лиза П. Хакер не понимает, почему if должна быть особой формой. «Почему нельзя просто
; определить ее как обычную процедуру с помощью cond?» — спрашивает она. Лизина подруга
; Ева Лу Атор утверждает, что, разумеется, можно, и определяет новую версию if:
(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

; Ева показывает Лизе новую программу:
(new-if (= 2 3) 0 5) ; -> 5
(new-if (= 1 1) 0 5) ; -> 0

; Обрадованная Лиза переписывает через new-if программу вычисления квадратного корня:
(define (new-sqrt-iter guess x) (new-if (good-enought? guess x)
                                        guess
                                        (new-sqrt-iter (improve-guess guess x) x)
                                        ))

; Что получится, когда Лиза попытается использовать эту процедуру для вычисления квадрат-
; ных корней? Объясните.

; Бесконечная рекусрия потому, что сначало вычисляются аргументы для процедуры
; а потом применяется процедура (Аппликативный порядок вычисления)
; Встроенный if это специальная форма, которая сначало вычисляет предикат, а потом нужный аргумент
(new-sqrt-iter 1.0 2) ; -> ;Aborting!: maximum recursion depth exceeded

0.001 - «достаточно хорошее» приближение