Странная петля Фибоначчи: красота математического начала

Поговорим об удивительной последовательности Фибоначчи, золотом сечении и бактериях. Будьте готовы найти совпадения там, где не ожидали их увидеть.

Странная петля Фибоначчи: красота математического начала

Говоря об алгоритмах, нельзя не упомянуть о последовательности Фибоначчи. Она тесно связана с золотым сечением, которое мы снова и снова встречаем в природе, архитектуре, искусстве и даже романе Дэна Брауна. От раковин морских животных до сакральной геометрии, по-видимому, Золотое Сечение закодировано во многих аспектах нашей Вселенной.

Невозможно перечислить все места, где мы можем встретить эту удивительную последовательность, но самое невероятное – она появляется даже внутри самой себя. Рекурсия внутри рекурсии, математическое начало, то, что Хофштадтер мог бы назвать «странной петлей» (strange loop).

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

Python

def fib(n):
if n <= 1:
return 1

return fib(n — 2) + fib(n — 1)

12345 def fib(n):    if n <= 1:        return 1     return fib(n — 2) + fib(n — 1)

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

Последовательность была описана в 1202 году Леонардо Фибоначчи. Она начинается с двух единиц, а последующие члены вычисляются путем сложения двух предыдущих. Третий член 1 + 1 = 2, а четвертый 1 + 2 = 3, далее 2 + 3 = 5. Вот первые несколько цифр:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …

1 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …

Рекурсивный код выше означает следующее: если n равно 0 или 1, функция вернет единицу, иначе – результат сложения fib(n-1) и fib(n-2), то есть сумму двух предыдущих членов.

Ряд Фибоначчи и золотое сечение

Кроме самой последовательности, Фибоначчи обнаружил ее связь с золотым сечением.

Золотое сечение – иррациональное число. Как и ? (число Пи), оно имеет бесконечное количество цифр после запятой, которые никогда не образуют повторяющихся шаблонов. Большинство из нас помнят ? как 3.14, а золотое сечение можно запомнить как 1.618. Буквенное представление этой величины – ? (фи, Phi).

Если взять n-ный член последовательности Фибоначчи и разделить его на (n-1)-ный, то полученный результат будет приблизительно равен золотому сечению. Чем дальше от начала, тем точнее приближение:

5/3 = 1.666
8/5 = 1.6
13/8 = 1.625
21/13 = 1.61538461538

1234 5/3 = 1.6668/5 = 1.613/8 = 1.62521/13 = 1.61538461538

Ряд Фибоначчи как алгоритмическая сложность

Вероятно, вы знаете, что рекурсивный код работает медленно. А знаете ли вы, что он работает медленно таким образом, который тесно связан с числом ??

Смоделируем наш пример с помощью дерева (так можно представить практически все рекурсивные функции). Каждый вызов – это внутренний узел, а базовые случаи – листья. Дерево для fib(5) выглядит вот так:

Странная петля Фибоначчи: красота математического начала

Вы можете определить сложность этой функции как O(2n). Каждый вызов по существу приводит к еще двум вызовам – практически идеальный пример экспоненциального удвоения. Другими словами, дерево, представляющее наш код, имеет коэффициент ветвления 2, каждый узел имеет 2 дочерних элемента, поэтому на каждой глубине число узлов удваивается. Из одного узла получается 2, потом 4, потом 8…

Нотация «большое O» – это нечеткая линза, где оценка одновременно рекомендуется и требуется. Но действительно ли эта функция экспоненциально удваивается? Попробуем измерить время выполнения функции fib, определенной выше:

Python

def time_fib(n):
start = time.clock()
digit = fib(n)
stop = time.clock()

return digit, (stop — start)

for i in range(1, 100):
digit, time_elapsed = time_fib(i)
print(«{:3d} {:10d} {:5d}».format(i, digit, round(time_elapsed)))

1234567891011 def time_fib(n):    start = time.clock()    digit = fib(n)    stop = time.clock()     return digit, (stop — start)  for i in range(1, 100):    digit, time_elapsed = time_fib(i)    print(«{:3d} {:10d} {:5d}».format(i, digit, round(time_elapsed)))

Даже неуклюжий эмпирический анализ намекает на нашу странную петлю. После 32 итераций измерения приобретают знакомую форму…

n fib(b) time_elapsed
32 3524578 1
33 5702887 1
34 9227465 2
35 14930352 3
36 24157817 5
37 39088169 8
38 63245986 13

123456789 n  fib(b)    time_elapsed32 3524578   133 5702887   134 9227465   235 14930352  336 24157817  537 39088169  838 63245986  13…

Компьютеры, часы и интерпретаторы неточны, и постепенно значение time_elapsed становится плохим приближением ряда Фибоначчи:

n fib(b) time_elapsed
39 102334155 24
40 165580141 37
41 267914296 59
42 433494437 95
43 701408733 155
44 1134903170 253

1234567 n  fib(b)     time_elapsed39 102334155  2440 165580141  3741 267914296  5942 433494437  9543 701408733  15544 1134903170 253

Тем не менее, даже грязная реализация выявила теоретическую истину. Рекурсивный метод вычисления n-ного члена последовательности Фибоначчи имеет алгоритмическую сложность, которая отражает эту последовательность. Если бы его сложность была O(2n), количество времени бы удваивалось, но этого не происходит.

Колония бактерий и ряд Фибоначчи

Можно смоделировать сложность этой функции, используя рекуррентное отношение – формальный математический язык для описания рекурсивных функций. Не пугайтесь этого определения, тут все просто:

f (n) = f (n-1) + f (n-2)

1 f (n) = f (n-1) + f (n-2)

Объем работы, который требуется для вычисления n-ного числа, – это объем работы, который требуется для вычисления предыдущих двух цифр вместе взятых. Другими словами, количество листовых узлов в рекурсивном дереве для вычисления n-ного члена последовательности отражает значение этого n-ного члена.

Возьмем конкретный пример:

f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
f(2) = f(1) + f(0)

1234 f(5) = f(4) + f(3)f(4) = f(3) + f(2)f(3) = f(2) + f(1)f(2) = f(1) + f(0)

И f(1), и f(0) в нашем случае постоянны, так как метод просто возвращает 1. Поэтому можно сказать, что:

f (1) = 1
f (0) = 1

12 f (1) = 1f (0) = 1

Если сложить все это снизу вверх, получится следующее:

f (2) = 1 + 1 = 2
f (3) = 2 + 1 = 3
f (4) = 3 + 2 = 5
f (5) = 5 + 3 = 8

1234 f (2) = 1 + 1 = 2f (3) = 2 + 1 = 3f (4) = 3 + 2 = 5f (5) = 5 + 3 = 8

Вы уже догадываетесь, к чему все это ведет?

Давайте попробуем развернуть формулу для f(5) вместо того, чтобы вставлять в нее реальные значения:

f(5) = f(4) + f(3)
f(5) = [f(3) + f(2)] + [f(2) + f(1)]
f(5) = {[f(2) + f(1)] + [f(1) + f(0)]} + {[f(1) + f(0)] + f(1)}
f(5) = {f(1) + f(0) + f(1) + f(1) + f(0)} + {f(1) + f(0) + f(1)}

1234 f(5) = f(4) + f(3)f(5) = [f(3) + f(2)] + [f(2) + f(1)]f(5) = {[f(2) + f(1)] + [f(1) + f(0)]} + {[f(1) + f(0)] + f(1)}f(5) = {f(1) + f(0) + f(1) + f(1) + f(0)} + {f(1) + f(0) + f(1)}

Все эти f(0) и f(1) – это листовые узлы дерева, которые имеют константное значение 1.

Можно ли смоделировать это отношение лучшим способом, чем расширение? Возможно ли создать формулу, которая описывается, сколько f(0) и f(1) будет при разложении конкретного f(n)? Оказывается, возможно! Пристегнитесь, мы входим в зону математического анализа.

Многие рекуррентные соотношения, включая это, по существу являются геометрическими рядами. Рассмотрим рекуррентную зависимость, которая грубо моделирует рост популяции бактерий:

f (n) = 2*f(n-1)

1 f (n) = 2*f(n-1)

В каждый момент времени каждая бактерия разделяется на две, поэтому популяция увеличивается вдвое по сравнению с предыдущим моментом. Если начать с одной бактерии, в следующий момент будет уже две, затем 4, 8, 16, 32 и так далее. Это экспоненциальная функция f(n) = 2^n.

Вспомним, что умножение – это просто повторяющееся сложение, и увидим, насколько это похоже на последовательность Фибоначчи:

f(n) = 2 * f(n-1) = f(n — 1) + f(n — 1)

1 f(n) = 2 * f(n-1) = f(n — 1) + f(n — 1)

И тогда:

f(n) = f(n — 1) + f(n — 1) = 2^n
f(n) = f(n — 1) + f(n — 2) = ???

12 f(n) = f(n — 1) + f(n — 1) = 2^nf(n) = f(n — 1) + f(n — 2) = ???

Есть все основания полагать, что второе выражение также будет расти экспоненциально, но медленнее, чем 2n. С другой стороны, рекурсивное дерево для функции роста бактерий будет иметь больше узлов, чем дерево для fib, хотя в обоих деревьях у узла либо 2 ребенка, либо ни одного. Они похожи, но не идентичны.

Опять золотое сечение

Оказывается, что для «линейных гомогенных рекуррентных отношений с постоянными коэффициентами» можно использовать изящный трюк, для нахождения короткого решения. К счастью, ряд Фибоначчи является таким отношением и мы можем представить его без использования рекурсии (и даже итерации) всего в одной формуле.

Доказательство этого трюка, называемое «теоремой о различных корнях», можно найти здесь.

Мы знаем, что ряд растет по экспоненте, а этот трюк помогает найти «корни» экспоненциальной функции. Он довольно прост: нужно взять нижние индексы функции f и превратить их в экспоненты по переменной r (root – корень), для которой мы их затем решим.

Применим этот трюк для формулы роста бактерий:

f(n) = 2f(n-1)
r^n = 2r^n-1
r = 2

123 f(n) = 2f(n-1)r^n = 2r^n-1r = 2

На последнем шаге мы делим каждую сторону на r^n-1.

Этот трюк приводит к тому же ответу, что был получен выше – экспоненциальный рост колонии 2n.

Теперь попробуем то же самое для ряда Фибоначчи:

f(n) = f(n-1) + f(n-2)
r^n = r^n-1 + r^n-2
r^2 = r + 1 ; [разделить обе стороны на r^n-2]
r^2 — r — 1 = 0

1234 f(n) = f(n-1) + f(n-2)r^n = r^n-1 + r^n-2r^2 = r + 1 ; [разделить обе стороны на r^n-2]r^2 — r — 1 = 0

Полученное уравнение можно решить для r, используя квадратичную формулу.

r = [1 +- sqrt(1 — (4*(-1)))] / 2
r = (1 + sqrt(5)) / 2
r = (1 — sqrt(5)) / 2

123 r = [1 +- sqrt(1 — (4*(-1)))] / 2r = (1 + sqrt(5)) / 2r = (1 — sqrt(5)) / 2

Произошло нечто удивительное, даже если вы этого не заметили. Посчитайте на калькуляторе 1 + sqrt(5) / 2. Вы получите … 1.618: ?, золотое сечение. Поразительно.

Чтобы не потерять лес за деревьями, отметим, что это экспериментально демонстрирует экспоненциальный рост последовательности Фибоначчи с корнем экспоненты 1.618.  Если n-ный член, разделенный на (n-1)-ный член приблизительно равен ?, то умножение (n-1)-ного члена на ? будет равно n-ному члену.

Отметим также, что второй корень – это другое замечательное число ? (Psi, пси), которое похоже на золотое сечение и примерно равно -0.618.

Конечно, технически будет правильно сказать, что верхняя граница рекурсивной функции O(2n), все же гораздо более приятно знать, что более жесткая граница – O(?n).

Формула Бине

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

Вы можете самостоятельно доказать этот замечательный факт.

Это формула Бине, позволяющая определить n-ный член последовательности Фибоначчи:

f(n) = (?^n — ?^n) / sqrt(5)

1 f(n) = (?^n — ?^n) / sqrt(5)

Это невероятно!

Перевод статьи Fibonacci’s Strange Loop: the beauty of mathematical inception by Tyler Elliot Bettilyon

Просмотров:

Добавить комментарий