1.1.7. Пример: вычисление квадратного корня методом Ньютона

Процедуры, как они описаны выше, очень похожи на обыкновенные математические функции. Они устанавливают значение, которое определяется одним или более параметром. Но есть важное различие между математическими функциями и компьютерными

процедурами. Процедуры должны быть эффективными.

В качестве примера рассмотрим задачу вычисления квадратного корня. Мы можемопределить функцию «квадратный корень» так:

(картинка)

Это описывает совершенно нормальную математическую функцию. С помощью такого определения мы можем решать, является ли одно число квадратным корнем другого, или выводить общие свойства квадратных корней. С другой стороны, это определение

не описывает процедуры. В самом деле, оно почти ничего не говорит о том, как найти квадратный корень данного числа. Не поможет и попытка перевести это определение на псевдо-Лисп:

(define (sqrt x)

(the y (and (>= y 0)

(= (square y) x))))

Это только уход от вопроса.

Противопоставление функций и процедур отражает общее различие между описанием свойств объектов и описанием того, как что-то делать, или, как иногда говорят, различие между декларативным знанием и императивным знанием. В математике нас

обычно интересуют декларативные описания (что такое), а в информатике императивные описания (как).

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

(картинка)

Продолжая этот процесс, мы получаем все более точные приближения к квадратному корню. Теперь формализуем этот процесс в терминах процедур. Начнем с подкоренного числа и какого-то значения приближения. Если приближение достаточно хорошо подходит для наших целей, то процесс закончен; если нет, мы должны повторить его с улучшенным значением приближения. Запишем эту базовую стратегию в виде процедуры:

(define (sqrt-iter guess x)

(if (good-enough? guess x)

guess

(sqrt-iter (improve guess x)

x)))

Значение приближения улучшается с помощью взятия среднего между ним и частным подкоренного числа и старого значения приближения:

(define (improve guess x)

(average guess (/ x guess)))

где

(define (average x y)

(/ (+ x y) 2))

Нам нужно еще сказать, что такое для нас «достаточно хорошее» приближение. Следующий вариант сойдет для иллюстрации, но на самом деле это не очень хороший тест. (См.упражнение 1.7.) Идея состоит в том, чтобы улучшать приближения до тех пор, пока его квадрат не совпадет с подкоренным числом в пределах заранее заданного допуска (здесь 0.001) 22 :

(define (good-enough? guess x)

(< (abs (- (square guess) x)) 0.001))

Наконец, нужно с чего-то начинать. Например, мы можем для начала предполагать, что квадратный корень любого числа равен 1:

(define (sqrt x)

(sqrt-iter 1.0 x))

Если мы введем эти определения в интерпретатор, мы сможем использовать sqrt как любую другую процедуру:

(sqrt 9)

3.00009155413138

(sqrt (+ 100 37))

11.704699917758145

(sqrt (+ (sqrt 2) (sqrt 3)))

1.7739279023207892

(square (sqrt 1000))

1000.000369924366

Программа sqrt показывает также, что того простого процедурного языка, который мы описали до сих пор, достаточно, чтобы написать любую чисто вычислительную программу, которую можно было бы написать, скажем, на Си или Паскале. Это может показаться удивительным, поскольку в наш язык мы не включили никаких итеративных (циклических) конструкций, указывающих компьютеру, что нужно производить некое действие несколько раз. Sqrt-iter, с другой стороны, показывает, как можно

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