Изучение метода Ньютона для вычисления квадратных корней в схеме
Я еще раз посетил 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)))
Поскольку в Лиспе довольно легко заблудиться в скобках и полированной нотации (префикс вместо инфиксных операторов), даже простой процесс усреднения двух чисел рекомендуется определять как отдельную функцию.
В заключение, вот полный код: