Алгоритмы неформально. Инструкция для начинающих питонистов - [40]
Наше описание вавилонского алгоритма состоит из четырех шагов. С другой стороны, математик может выразить весь алгоритм одним уравнением:
В данном случае используется стандартная математическая практика описания бесконечной последовательности сериями индексов: (y1, y2... yn...). Если вам известен n-й элемент этой бесконечной последовательности, то (n + 1)-й элемент можно вычислить по приведенному выше выражению. Последовательность сходится к 
Чтобы понять, почему вавилонский алгоритм работает, можно рассмотреть два простых случая:
• Если
Но заметим, что
• Если 
Заметим, что
Эти случаи можно записать более компактно с удалением части текста:
• Если
• Если
Если y является заниженной оценкой для истинного значения
Квадратные корни на языке Python
Вавилонский алгоритм достаточно легко реализуется на Python. Определим функцию, которая получает в аргументах x, y и переменную error_tolerance. Мы создаем цикл while, который многократно выполняется, пока погрешность не станет достаточно малой. При каждой итерации цикла while вычисляется z, значение y обновляется средним y и z (в соответствии с шагами 2 и 3 в описании алгоритма), после чего обновляется погрешность, равная y2 – x. Код функции приведен в листинге 5.7.
Листинг 5.7. Функция для вычисления квадратных корней по вавилонскому алгоритму
def square_root(x,y,error_tolerance):
our_error = error_tolerance * 2
while(our_error > error_tolerance):
z = x/y
y = (y + z)/2
our_error = y**2 - x
return y
Возможно, вы заметили, что вавилонский алгоритм имеет нечто общее с градиентным подъемом и алгоритмом для задачи аутфилдера. Во всех случаях выполняются небольшие итеративные действия, пока вы не приблизитесь на достаточное расстояние к окончательной цели. Такая структура часто встречаются в алгоритмах.
Функцию для вычисления квадратного корня можно проверить следующим образом:
print(square_root(5,1,.000000000000001))
На консоль выводится число 2.23606797749979. Вы можете проверить, что это же число будет выведено методом math.sqrt(), стандартным для Python:
print(math.sqrt(5))
Вы получите точно такой же результат:2.23606797749979. Вы успешно написали собственную функцию для вычисления квадратных корней. Если вы когда-нибудь окажетесь на необитаемом острове без интернета, не имея возможности загрузить модули Python (в частности, модуль math), то всегда сможете самостоятельно написать такие функции, как math.sqrt(). Не забудьте поблагодарить жителей Вавилона за придуманный ими алгоритм.
Генераторы случайных чисел
До этого мы пытались в хаосе найти порядок. Математика хорошо подходит для этой цели, но в данном разделе мы займемся прямо противоположным делом: поиском хаоса в порядке. Иначе говоря, вы узнаете, как алгоритмически генерировать случайность.
Существует постоянная потребность в случайных числах. В видеоиграх используются случайно выбранные числа, чтобы игроки сталкивались с неожиданными положениями и перемещениями персонажей. Правильное функционирование некоторых из самых эффективных методов машинного обучения (включая случайные леса и нейронные сети) в значительной мере зависят от случайного выбора. То же можно сказать о некоторых эффективных статистических методах (например, бутстрэп в статистике), которые используют случайность, чтобы небольшие статические наборы данных в большей степени напоминали хаотичный мир. Корпорации и ученые-теоретики применяют тесты A/B, зависящие от случайного распределения элементов по условиям для правильного сравнения воздействия условий. Список можно продолжить; в большинстве технологических областей существует огромный постоянный спрос на случайность.
Возможна ли случайность
Такой спрос на случайные числа чреват одной проблемой: мы не полностью уверены в том, что они реально существуют. Некоторые люди считают, что Вселенная детерминирована: если нечто двигается, то его движение было вызвано другим полностью прослеживаемым движением, которое в свою очередь было вызвано другим движением, и т.д. — как при столкновении бильярдных шаров. Если Вселенная ведет себя как бильярдный стол, то, зная текущее состояние каждой частицы во Вселенной, мы могли бы однозначно определить все прошлое и будущее. В таком случае любое событие — выигрыш в лотерею, встреча со старым знакомым на другом конце света, падение метеорита на голову — в действительности не случайно, как нам хотелось бы думать, а всего лишь является полностью предопределенным следствием конфигурации Вселенной с десяток миллиардов лет назад. Это означало бы, что никакой случайности не существует, что мы застряли в мелодии механического пианино, а события кажутся случайными только потому, что мы о них недостаточно знаем.
