5 способов вычисления чисел Фибоначчи: реализация и сравнение

Original author: Sahand Saba
  • Translation

Введение


Программистам числа Фибоначчи должны уже поднадоесть. Примеры их вычисления используются везде. Всё от того, что эти числа предоставляют простейший пример рекурсии. А ещё они являются хорошим примером динамического программирования. Но надо ли вычислять их так в реальном проекте? Не надо. Ни рекурсия, ни динамическое программирование не являются идеальными вариантами. И не замкнутая формула, использующая числа с плавающей запятой. Сейчас я расскажу, как правильно. Но сначала пройдёмся по всем известным вариантам решения.

Код предназначен для Python 3, хотя должен идти и на Python 2.

Для начала – напомню определение:

Fn= Fn-1+ Fn-2

и F1= F2=1.

Замкнутая формула


Пропустим детали, но желающие могут ознакомиться с выводом формулы. Идея в том, чтобы предположить, что есть некий x, для которого Fn = xn, а затем найти x.



что означает



сокращаем xn-2



Решаем квадратное уравнение:



Откуда и растёт «золотое сечение» ϕ=(1+√5)/2. Подставив исходные значения и проделав ещё вычисления, мы получаем:



что и используем для вычисления Fn.

from __future__ import division
import math

def fib(n):
    SQRT5 = math.sqrt(5)
    PHI = (SQRT5 + 1) / 2
    return int(PHI ** n / SQRT5 + 0.5)


Хорошее:
Быстро и просто для малых n
Плохое:
Требуются операции с плавающей запятой. Для больших n потребуется большая точность.
Злое:
Использование комплексных чисел для вычисления Fn красиво с математической точки зрения, но уродливо — с компьютерной.

Рекурсия


Самое очевидное решение, которое вы уже много раз видели – скорее всего, в качестве примера того, что такое рекурсия. Повторю его ещё раз, для полноты. В Python её можно записать в одну строку:

fib = lambda n: fib(n - 1) + fib(n - 2) if n > 2 else 1


Хорошее:
Очень простая реализация, повторяющая математическое определение
Плохое:
Экспоненциальное время выполнения. Для больших n очень медленно
Злое:
Переполнение стека

Запоминание


У решения с рекурсией есть большая проблема: пересекающиеся вычисления. Когда вызывается fib(n), то подсчитываются fib(n-1) и fib(n-2). Но когда считается fib(n-1), она снова независимо подсчитает fib(n-2) – то есть, fib(n-2) подсчитается дважды. Если продолжить рассуждения, будет видно, что fib(n-3) будет подсчитана трижды, и т.д. Слишком много пересечений.

Поэтому надо просто запоминать результаты, чтобы не подсчитывать их снова. Время и память у этого решения расходуются линейным образом. В решении я использую словарь, но можно было бы использовать и простой массив.

M = {0: 0, 1: 1}

def fib(n):
    if n in M:
        return M[n]
    M[n] = fib(n - 1) + fib(n - 2)
    return M[n]


(В Python это можно также сделать при помощи декоратора, functools.lru_cache.)

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

Динамическое программирование


После решения с запоминанием становится понятно, что нам нужны не все предыдущие результаты, а только два последних. Кроме этого, вместо того, чтобы начинать с fib(n) и идти назад, можно начать с fib(0) и идти вперёд. У следующего кода линейное время выполнение, а использование памяти – фиксированное. На практике скорость решения будет ещё выше, поскольку тут отсутствуют рекурсивные вызовы функций и связанная с этим работа. И код выглядит проще.

Это решение часто приводится в качестве примера динамического программирования.

def fib(n):
    a = 0
    b = 1
    for __ in range(n):
        a, b = b, a + b
    return a


Хорошее:
Быстро работает для малых n, простой код
Плохое:
Всё ещё линейное время выполнения
Злое:
Да особо ничего.

Матричная алгебра


И, наконец, наименее освещаемое, но наиболее правильное решение, грамотно использующее как время, так и память. Его также можно расширить на любую гомогенную линейную последовательность. Идея в использовании матриц. Достаточно просто видеть, что



А обобщение этого говорит о том, что



Два значения для x, полученных нами ранее, из которых одно представляло собою золотое сечение, являются собственными значениями матрицы. Поэтому, ещё одним способом вывода замкнутой формулы является использование матричного уравнения и линейной алгебры.

Так чем же полезна такая формулировка? Тем, что возведение в степень можно произвести за логарифмическое время. Это делается через возведения в квадрат. Суть в том, что



где первое выражение используется для чётных A, второе для нечётных. Осталось только организовать перемножения матриц, и всё готово. Получается следующий код. Я организовал рекурсивную реализацию pow, поскольку её проще понять. Итеративную версию смотрите тут.

def pow(x, n, I, mult):
    """
    Возвращает x в степени n. Предполагает, что I – это единичная матрица, которая 
    перемножается с mult, а n – положительное целое
    """
    if n == 0:
        return I
    elif n == 1:
        return x
    else:
        y = pow(x, n // 2, I, mult)
        y = mult(y, y)
        if n % 2:
            y = mult(x, y)
        return y


def identity_matrix(n):
    """Возвращает единичную матрицу n на n"""
    r = list(range(n))
    return [[1 if i == j else 0 for i in r] for j in r]


def matrix_multiply(A, B):
    BT = list(zip(*B))
    return [[sum(a * b
                 for a, b in zip(row_a, col_b))
            for col_b in BT]
            for row_a in A]


def fib(n):
    F = pow([[1, 1], [1, 0]], n, identity_matrix(2), matrix_multiply)
    return F[0][1]


Хорошее:
Фиксированный объём памяти, логарифмическое время
Плохое:
Код посложнее
Злое:
Приходится работать с матрицами, хотя они не так уж и плохи

Сравнение быстродействия


Сравнивать стоит только вариант динамического программирования и матрицы. Если сравнивать их по количеству знаков в числе n, то получится, что матричное решение линейно, а решение с динамическим программированием – экспоненциально. Практический пример – вычисление fib(10 ** 6), числа, у которого будет больше двухсот тысяч знаков.

n = 10 ** 6
Вычисляем fib_matrix: у fib(n) всего 208988 цифр, расчёт занял 0.24993 секунд.
Вычисляем fib_dynamic: у fib(n) всего 208988 цифр, расчёт занял 11.83377 секунд.




Теоретические замечания


Не напрямую касаясь приведённого выше кода, данное замечание всё-таки имеет определённый интерес. Рассмотрим следующий граф:

image

Подсчитаем количество путей длины n от A до B. Например, для n = 1 у нас есть один путь, 1. Для n = 2 у нас опять есть один путь, 01. Для n = 3 у нас есть два пути, 001 и 101. Довольно просто можно показать, что количество путей длины n от А до В равно в точности Fn. Записав матрицу смежности для графа, мы получим такую же матрицу, которая была описана выше. Это известный результат из теории графов, что при заданной матрице смежности А, вхождения в Аn — это количество путей длины n в графе (одна из задач, упоминавшихся в фильме «Умница Уилл Хантинг»).

Почему на рёбрах стоят такие обозначения? Оказывается, что при рассмотрении бесконечной последовательности символов на бесконечной в обе стороны последовательности путей на графе, вы получите нечто под названием "подсдвиги конечного типа", представляющее собой тип системы символической динамики. Конкретно этот подсдвиг конечного типа известен, как «сдвиг золотого сечения», и задаётся набором «запрещённых слов» {11}. Иными словами, мы получим бесконечные в обе стороны двоичные последовательности и никакие пары из них не будут смежными. Топологическая энтропия этой динамической системы равна золотому сечению ϕ. Интересно, как это число периодически появляется в разных областях математики.
Support the author
Share post

Comments 19

    0
    Пусть меня поправят математики через личные сообщения, поскольку в последнем абзаце начался такой математический угар, что русскоязычных аналогов некоторых терминов я просто не нашёл.
      +11
      Использование комплексных чисел для вычисления Fn красиво с математической точки зрения, но уродливо — с компьютерной.

      Где вы там комплексные числа то нашли? В том плане, что функция может применяться к комплексным числам (как и к не целым, в этом её большое преимущество, которое, почему-то опущено), но для вычисления i-того номера комплексные числа не нужны.

      P.S. Мне кажется, что это 4-ая статья с одними и теми же методами на хабре. Я уж молчу, что они все есть на вики.
        0
        О чем статья?
          0
          О том, как отвечать на один из вопросов на интервью. К сожалению, есть места где такое спрашивают. Встречаются вариации, например, вывести список простых чисел.
          • UFO just landed and posted this here
              0
              Поскольку тип результата — int, то достаточно сделать табличную реализацию первых 48 или 94 чисел. Ибо вотще.
              • UFO just landed and posted this here
          0
          Вариант 6 (небольшое развитие матричного)
          F_{2n+1} = F_n^2 + F_{n+1}^2
          F_{2n} = F_n (2F_{n+1} — F_n)

          вместо матрицы 2x2, используется пара
          • UFO just landed and posted this here
              +7
              Хорошее:
              Фиксированный объём памяти, логарифмическое время
              Ну сколько же можно. Где там логарифмическое время? Ну невозможно умножать за логарифмическое время. Длина байтового представления n-го числа Фиббоначи растет линейно. В uint64 влезет 93е (если не ошибаюсь) число фиббоначи, кешируется все это в 0.7Кб, т.е. на практике сложность или константная (если нам надо числа до определенного) или уж никак ни логарифмическая, коли даже битовое представление числа уже линейно растет, не говоря уже про умножение.
              Тем, что возведение в степень можно произвести за логарифмическое время.
              То что работает в рамках 64 битных регистров нельзя переносить на большие числа. Правильнее было бы сказать что в целую степень можно возвести за логарифмическое количество умножений.
                0
                Всё верно. Можно выкрутиться, и сказать, что мы вычисляем N-ное число по модулю M (где модуль M фиксирован и не зависит от N). Тогда действительно будет O(log N). Обычно этот способ и применяется для вычисления по модулю. Для предложенной автором реализации сложность будет примерно такая: сложение двух полиномов за O(N), возведение в квадрат за O(N log N); итераций алгоритма O(log N); тогда итоговая сложность будет O(N log N) для матриц и O(N^2) для тупого алгоритма. У обоих O(N) памяти.
                Для оценки первого я пользовался этим:
                image
                image
                0
                Кстати, код в параграфе «Динамическое программирование» прямо реализуется рекурсивным цифровым фильтром с двумя ячейками памяти: просто и естественно.
                  0
                  Капитан Очевидность (TL;DR): матричный вариант всех ест с хрустом на завтрак. Господа, матрицы не причём, вопрос в том, используется возможность человеческого мозга абстрагировть, или нет.
                    0
                    1. Не увидел, что там динамического в «динамическом программировании» по сравнению с другими вариантами.

                    2. В начале статьи все же хотелось бы примеров, где, когда и каких порядков числа Фибоначи нужны в реальных задачах. Иначе все в n-ый выглядит как «динамически» высосанное из пальца.
                      0
                      То же на Haskell по модулю 2^32, но с упрощенными формулами
                      fib 0 = 0
                      fib 1 = 1
                      fib nn = if even nn
                      	then let n = div nn 2 in
                      		(2 * fib (n - 1) + fib n) * fib n
                      	else let n = div (nn+1) 2 in
                      		fib n ^ 2 + fib (n-1) ^ 2
                      

                      К сожалению, в Haskell нет встроенной длинной арифметики. Сложность вычисления сильно зависит от реализации длинной арифметики. Можно и быстрее, чем за O(N).
                        0
                        Как это в хаскеле нет встроенной длинной арифметики? Тип Integer разве не оно?
                          0
                          Значит с Integer будет то же самое, а с Int по модулю. Не суть.
                        0
                        Не могли бы вы перевести предпоследний вариант в java подобный язык а то я с питоном не в ладах. Заранее спасибо.
                          0
                          Мой старый вариант, есть куда улучшать, но идею демонстрирует:

                          using System;
                          using System.Diagnostics;
                          using System.Numerics;
                           
                          namespace ConsoleApplication1
                          {
                              class Program
                              {
                                  public static BigInteger Fib(BigInteger n)
                                  {
                                      if (n < 0)
                                          throw new ArgumentException("The fibo value cannot be negative");
                                      if (n <= 1) 
                                          return n;
                           
                                      BigInteger[,] result = { { 1, 0 }, { 0, 1 } };
                                      BigInteger[,] fiboM = { { 1, 1 }, { 1, 0 } };
                           
                                      while (n > 0)
                                      {
                                          if (n%2 == 1)
                                              Mult2x2Matrix(result, fiboM);
                                          n /= 2;
                                          Mult2x2Matrix(fiboM, fiboM);
                                      }
                           
                                      return result[1,0];
                                  }
                           
                                  private static void Mult2x2Matrix(BigInteger[,] m, BigInteger[,] n)
                                  {
                                      BigInteger a = m[0,0] * n[0,0] + m[0,1] * n[1,0];
                                      BigInteger b = m[0,0] * n[0,1] + m[0,1] * n[1,1];
                                      BigInteger c = m[1,0] * n[0,0] + m[1,1] * n[0,1];
                                      BigInteger d = m[1,0] * n[0,1] + m[1,1] * n[1,1];
                           
                                      m[0,0] = a;
                                      m[0,1] = b;
                                      m[1,0] = c;
                                      m[1,1] = d;
                                  }
                           
                                  static void Main(string[] args)
                                  {
                                      var sw = Stopwatch.StartNew();
                                      var bigInteger = Fib(65536);
                                      sw.Stop();
                                      Console.WriteLine("Elapsed milliseconds = {0}, number length = {1} digits", sw.ElapsedMilliseconds, bigInteger.ToString().Length);
                                  }
                              } 
                          }
                          

                        Only users with full accounts can post comments. Log in, please.