Изучение формулы Фибоначчи в Python
Давайте рассмотрим множество различных методов и техник вычисления рядов Фибоначчи с использованием Python.
Ряд Фибоначчи - это красиво, завораживающе, загадочно! Ряд определяется следующим образом: каждое число является суммой двух предыдущих. Простой:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Итерационное вычисление Фибоначчи
Самый простой способ вычислить число Фибоначчи (n) - просто начать с самого начала и итеративно продвигаться вперед. Это решение вычисляет все предыдущие значения, давая ему экспоненциальное время работы - для вычисления больших чисел требуется все больше времени.
Рекурсивное вычисление Фибоначчи
Рекурсивный подход к нахождению чисел Фибоначчи иногда используется в качестве учебного пособия на уроках информатики. Вы можете видеть здесь, что функция вызывает себя в строке 14, что делает ее рекурсивной.
Этот метод работает в обратном направлении от начальной позиции, пока не достигнет 1 или 0. В противном случае он вычисляет сумму всех предыдущих рекурсий.
Рекурсия работает, потому что компьютер отслеживает, где мы используем конструкцию памяти, известную как стековая память. Это ограничено! Попытка найти большие числа Фибоначчи исчерпала бы стек.
Также: рекурсивный алгоритм страдает той же проблемой временной сложности, что и итерационный алгоритм - он должен вычислять все значения.
Использование мемоизации для эффективной рекурсии
Предыдущая рекурсивная функция вызывается повторно для некоторых значений i. Вместо того, чтобы пересчитывать это значение, мы можем использовать метод, известный как мемоизация.
Мемоизация - это просто запись или меморандум о ранее рассчитанных выходных значениях. Затем мы возвращаем памятку вместо того, чтобы пересчитывать значение.
Python очень хорошо поддерживает мемоизацию, если мы используем функцию декоратора. Декоратор оборачивает алгоритм и перехватывает все вызовы и все возвращаемые значения. Перехватывая вызовы и возвращаемые значения, мы можем сохранить их в локальном кеше - и в будущем использовать кешированные ответы.
Теперь мы можем применить декоратор memo к нашей функции fibonacci_wrapped и увидеть очень большое улучшение скорости. К сожалению, ограничения на рекурсию все еще действуют.
Python имеет встроенный декоратор мемоизации, наименее используемый кеш lru_cache:
@functools.lru_cache(maxsize=None)
Мы могли бы избавить себя от необходимости писать собственный (неэффективный!) Декоратор мемоизации и вместо этого использовать @functools.lru_cache. Не забудьте import functools, если хотите его использовать.
Использование умножения матриц для вычисления чисел Фибоначчи
Все предыдущие примеры страдали от одной и той же проблемы: необходимо было вычислить все предыдущие значения в последовательности. Мы можем избежать этой неэффективности, используя умножение матриц для прямого вычисления значения последовательности без вычисления предшественников.
Вы можете прочитать больше об умножении матриц здесь:
Поскольку последовательность Фибоначчи линейна и предсказуема, ее можно эффективно вычислить с помощью линейной алгебры.
Эта формула требует постоянного объема памяти для завершения и занимает линейно больше времени с увеличением значения n.
Использование золотого сечения для вычисления чисел Фибоначчи
Этот метод включен для полноты картины!
Последовательность Фибоначчи идеально представляет золотой рацион, поэтому мы можем использовать формулу Бине для его вычисления:
Вы видите, что я жульничаю. Если номер последовательности, который мы ищем, больше 71, эта функция незаметно обманывает и вместо этого использует метод умножения матриц.
Формула Бине - это точная алгебра. Однако компьютеры должны использовать неточное представление чисел с плавающей запятой. По мере увеличения значений n также накапливаются ошибки округления.
Использование битовых операций для вычисления Фибоначчи
В одной из первых статей я описал некоторые общие формулы для выполнения битовой арифметики с целыми числами. Мои давние подписчики, возможно, задавались вопросом, почему, но теперь все раскрыто!
Важно иметь представление о двоичной арифметике, прежде чем мы исследуем следующие способы вычисления чисел Фибоначчи.
Последовательность Лукаса
В этой трактовке чисел Фибоначчи я хотел бы также показать последовательность Люка. Как и числа Фибоначчи, числа Лукаса представляют собой сумму двух своих предшественников - они просто начинаются в другом месте:
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ....
Следовательно, числа Лукаса очень тесно связаны с числами Фибоначчи:
Давайте поработаем с этим с n=6.
F(n-1) = F(5) = 3 F(n+1) = F(7) = 8 F(n-1) + F(n+1) = (3 + 8) = 11 L(6) = 11
Расчет чисел Фибоначчи по формуле Джикстры
Эдсгар Джикстра был, пожалуй, самым блестящим теоретиком информатики в современной истории. Он предложил алгоритм, который использует степени чисел Лукаса для получения соответствующего числа Фибоначчи.
Действительно великолепно. Вот полный алгоритм:
Функция fibonacci_djikstra явно использует взаимосвязь между числами Люка и числами Фибоначчи, которые я показал ранее: L(n) = F(n-1) + F(n+1).
Он идет еще дальше и использует степенную функцию Лукаса для использования части формулы Бине - видите в нем целое число 5 и узнаете ли вы это из обсуждения золотого пайка?
Для более глубокого обсуждения алгоритма Джикстры см. Эту информацию.
Карацуба быстрое умножение
Следуя нашему обсуждению двоичной арифметики, есть один действительно интересный способ вычисления очень больших произведений - умножение Карацубы.
Согласно Википедии, алгоритм Карацубы был первым алгоритмом умножения, асимптотически более быстрым, чем квадратичный алгоритм начальной школы, он предлагает ускорение в 17,75 раза по сравнению с традиционной квадратной формулой для достаточно больших значений.
Мы будем использовать этот алгоритм в нашей следующей и последней формуле для вычисления чисел Фибоначчи!
Рекурсивное быстрое удвоение для вычисления Фибоначчи
В следующей формуле быстрого удвоения используются четыре инструмента, описанных ранее: рекурсия, запоминание, двоичная арифметика и умножение Карацубы. Вы можете догадаться, почему я решил поставить эту формулу в последнюю очередь!
Эта формула очень быстрая. Он вычисляет Фибоначчи с точностью до 80 000 микросекунд на моем MacBook Pro.
Далее я объясню, как это работает, используя итеративный вариант.
Итеративное быстрое удвоение для вычисления Фибоначчи
Мы можем легко изменить формы алгоритма: от рекурсивного к итеративному или итеративному к рекурсивному. Посмотрите, чем отличается следующая итеративная версия предыдущей:
Он содержит две петли. Первый последовательно уменьшает вдвое искомый порядковый номер. Второй последовательно удваивает его на обратном пути. Итерационная версия, очевидно, медленнее, но позволяет избежать переполнения стека.
В этом алгоритме используется важное свойство, идентифицированное теоретиками чисел: «свойство деления пополам». Это также значительно упрощает метод умножения матриц за счет использования формулы:
Вычисляется множество квадратов, поэтому умножение Карацубы полезно.
Результаты по времени
Я подумал, что вас могут заинтересовать результаты по срокам. Я решил сравнить алгоритм умножения матриц, алгоритм быстрого удвоения и алгоритм Джикстры. Совершенно очевидно, что золотое сечение и наивные итеративные и рекурсивные алгоритмы будут медленнее.
Вот код для сбора данных о времени:
А вот график результатов хронометража:
Надеюсь, вам понравилась эта статья! Я хочу пригласить вас подписаться на меня, чтобы вы получали уведомление, когда я опубликую следующую статью!
