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

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

*-Нравится статья? Кликни по рекламе! :)


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

На самом деле алгоритм нахождения квадратного корня представляет собой частный случай метода Ньютона, который является общим методом нахождения корней уравнений. Собственно алгоритм нахождения квадратного корня был разработан Героном Александрийским в первом веке н.э.

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

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

def sqrtIter(guess,x):
    if goodEnaugh(guess, x):
        return guess
    else:
        return sqrtIter(improve(guess, x), x)

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

def improve(guess, x):
    return average(guess, x/guess)

где

def average(x, y):
    return (x+y)/2

Нам нужно еще сказать, что такое для нас «достаточно хорошее» приближение. Идея состоит в том, чтобы улучшать приближения до тех пор, пока его квадрат не совпадет с подкоренным числом в пределах заранее заданного допуска, например 0.001:

def goodEnaugh(guess, x):
    if(abs(guess**2-x)<0.001):
        return 1
    else:
        return 0

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

def sqrt(x):
    return sqrtIter(1.0, x)

Sqrt — наш первый пример процесса, определенного множеством зависимых друг от друга процедур. Заметим, что определение sqrtIter рекурсивно (recursive); это означает, что процедура определяется в терминах самой себя. Идея, что можно определить процедуру саму через себя, возможно, кажется Вам подозрительной; неясно, как такое
«циклическое» определение вообще может иметь смысл, не то что описывать хорошо определенный процесс для исполнения компьютером. Рассмотрим, однако, некоторые другие важные детали, которые иллюстрирует пример с sqrt.

 Вся программа sqrt может рассматриваться как пучок процедур, отражающий декомпозицию задачи на подзадачи. Важность декомпозиционной стратегии не просто в том, что задача разделяется на части. Существенно то, что каждая процедура выполняет точно определенную задачу, которая может быть использована при определении других процедур. Проблема здесь состоит в том, что единственная процедура, которая важна для пользователей sqrt — это сама sqrt. Остальные процедуры (sqrtIter, goodEnough и improve) только забивают им головы. Теперь пользователи не могут определять других процедур с именем goodEnough ни в какой другой программе, которая должна работать совместно с программой вычисления квадратного корня, поскольку sqrt требуется это имя. Эта проблема становится особенно тяжелой при построении больших систем, которые пишут много различных программистов. Например, при построении большой библиотеки численных процедур многие числовые функции вычисляются как последовательные приближения и могут потому иметь в качестве вспомогательных процедуры goodEnough и improve. Нам хотелось бы локализовать подпроцедуры, спрятав их внутри sqrt, так, чтобы sqrt могла сосуществовать с другими последовательными приближениями, при том что у каждой из них была бы своя собственная процедура goodEnough. Чтобы сделать это возможным, мы разрешаем процедуре иметь внутренние определения, локальные для этой процедуры.

def sqrt(x):
    
    def sqrtIter(guess):
        if goodEnaugh(guess):
            return guess
        else:
            return sqrtIter(improve(guess))
        
    def improve(guess):
        return average(guess, x/guess)
    
    def average(x, y):
        return (x+y)/2
    
    def goodEnaugh(guess):
        if(abs(guess**2-x)<0.001):
            return 1
        else:
            return 0
        
    return sqrtIter(1.0)

Такое вложение определений, называемое блочной структурой (block structure), дает правильное решение для простейшей задачи упаковки имен. Но здесь таится еще одна идея. Помимо того, что мы можем вложить определения вспомогательных процедур внутрь главной, мы можем их упростить. Поскольку переменная x связана в определении sqrt, процедуры goodEnough, improve и sqrtIter, которые определены внутри sqrt, находятся в области действия x. Таким образом, нет нужды явно передавать x в каждую из этих процедур. Вместо этого мы можем сделать x свободной переменной во внутренних определениях, как это показано ниже. Тогда x получит свое значение от аргумента, с которым вызвана объемлющая их процедура sqrt. Такой порядок называется лексической сферой действия (lexical scoping) переменных.  
Используемая литература:

1. http://mitpress.mit.edu/sicp/