Изучение метода Ньютона для вычисления квадратных корней в схеме

Я еще раз посетил SCIP (Структура и интерпретация языка программирования) и подумал, что смогу пройти через этот интересный метод.

Вот достаточно простое определение квадратного корня из x.

Мы могли бы перефразировать определение в схеме:

(define (sqrt-of? x y)
  (and (>= y 0) (= (* y y) x))

Что гласит: «y является квадратным корнем из x, если y больше или равно 0, а y ² равно x ».

Однако наиболее распространенный способ вычисления квадратного корня - использовать метод последовательных приближений Ньютона, который гласит, что при любом предположении y для значения квадратного корня числа x , мы могли бы получить лучшее предположение, которое ближе к действительному квадратному корню, усреднив y с x / y.

Например, мы можем вычислить квадратный корень из 2, но при первоначальном предположении 1 (это может быть любое число). Вот расширение процедуры:

В конечном итоге ключ здесь - когда остановиться и довольствоваться ценностью.

Очевидно, это рекурсивная процедура. Мы могли это сказать, потому что он продолжает повторять ту же процедуру с новым значением (предположением) из последнего. И, на мой взгляд, нет другого языка программирования, более понятного, чем Lisp, при работе с рекурсиями.

Сначала определите процедуру, которая будет повторяться:

(define (sqrt-of guess x)
  ; TBD )

Как и любую рекурсивную функцию, мы начинаем с добавления базового случая, чтобы остановить потенциально бесконечный цикл:

(define (sqrt-of guess x)
  (if (good-enough? guess x)
       guess
       (sqrt-of (improve guess x) 
                 x)))

good-enough - это (пока) несуществующая процедура, которая определяет, достаточно ли близко guess к фактическому квадратному корню. Если это правда, возвращается guess, иначе мы должны продолжать поиск.

improve - это еще одна процедура, которая абстрагирует процесс, описанный ранее. Это усреднение y с x / y, чтобы получить лучшее предположение.

Это выражение (или форма, известная в Лиспе) (sqrt-of (improve guess x) x) является рекурсивной частью. Вы можете думать об этом как о (sqrt-of better-guess x). Синтаксис Лиспа позволяет легко подниматься и спускаться по лестнице абстракции, не отвлекаясь на грязный синтаксис программирования.

Для этого теста достаточно просто сказать, что если квадрат предположения находится в пределах 0,001 от x, мы счастливы. Давайте определим good-enough для этого:

(define (good-enough? guess x)
  (< (abs (- (* guess guess) x)) 0.001))

Он гласит: «Если абсолютное значение разницы квадрата предположения и x меньше 0,001, возвращается истина, иначе - ложь». Мы заботимся только о разнице, следовательно, об абсолютном значении.

Процедура improve определяется как

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

Поскольку в Лиспе довольно легко заблудиться в скобках и полированной нотации (префикс вместо инфиксных операторов), даже простой процесс усреднения двух чисел рекомендуется определять как отдельную функцию.

В заключение, вот полный код: