Фибоначчи, Haskell, O(log n)

(Внимание: дальше не написано ничего нового, но если вы не знаете о возведении в степень за \(O(\log n)\), можете чуть-чуть почитать.)

Не секрет, что числа Фибоначчи можно вычислить за экспоненциальное время, используя наивную рекурсию; за линейное время, используя более аккуратный способ; и даже за константное время, используя округление \(\frac{\phi^n}{\sqrt5}\) до ближайшего целого и скрещивая пальцы, что знаков хватит.

Так же не секрет, что, не используя floating point, можно обойтись и \(O(\log n)\) с помощью вычисления степени за \(O(\log n)\). Но всё равно опишу это.

Начнём со степени. Пускай у нас есть операция \(*\colon A\to A\). Тогда можно определить натуральночисленную степень \(a^{*n}\):\[a^{*1} = a, \quad a^{*(n+1)} = a*a^{*n}.\]Если \(*\) — ассоциативная, можно доказать, что для любых \(m\), \(n\) будет выполняться знакомое \(a^{*m} * a^{*n} = a^{*(m+n)}\). Это-то и нужно.

Пускай нам надо вычислить большуую степень \(a^{*n}\). Можно отправиться из определения и сделать это за \(n-1\) вычисление \(a * b\). А можно и лучше.
Если \(n = 2m\), пускай \(a^{*n} = a^{*m} * a^{*m}\). Аналогично, \(a^{*(2m+1)} = a^{*m} * a^{*m} * a\). Такой способ занимает логарифмическое количество вычислений \(a * b\).

Как же это использовать с числами Фибоначчи?

Заметили, что\[\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} = \begin{bmatrix} a + b & b \\ b & a \end{bmatrix}.\]Матрицы такого вида умножаются довольно просто:\[\begin{bmatrix} a + b & b \\ b & a \end{bmatrix}\cdot\begin{bmatrix} a’ + b’ & b’ \\ b’ & a’ \end{bmatrix} = \begin{bmatrix} \cdots & ab’ + ba’ + bb’ \\ ab’ + ba’ + bb’ & aa’ + bb’ \end{bmatrix}.\]Из-за замкнутости их относительно умножения можно спокойно забыть о «матричности» этих объектов. \(X_{a, b}\) — и ладно.

У нас есть операция, соответствующая ей степень и \(X_{0, 1}\). Можно приступать к реализации.

К реализации же на хаскеле приступать надо только после знакомства с тем, что операция (^) :: (Integral b, Num a) => a -> b -> a возведения в натуральную (тут уже с нулём) степень не проходит мимо описанного выше фольклора и использует бинарное возведение в степень, не сомневаясь в своих действиях (интересно, как бы операция могла сомневаться в своих действиях?). И лишь только мы определим эти \(X_{a, b}\) как экземпляр Num, всё остальное появится автоматически.

module Fibonacci (fib) where data X a = X a a deriving (Eq, Show)

(Ума не приложу, зачем экземпляр Num должен быть проверяем на равенство (Eq) и представим строкой (Show), однако в определении читаем: class (Eq a, Show a) => Num a <…>, так что пришлось отягощать определение типа.)

instance Num a => Num (X a) where     X a b * X a' b' = X (a * a' + b * b') (b * a' + (a + b) * b')     fromInteger n = X (fromInteger n) 0

…ээ, а это ещё зачем? А затем, что в вычислении (^ 0) надо откуда-то брать единицу. Она получается этим методом: fromInteger 1.

И вообще, хорошим тоном будет определить и остальные методы Num, пусть даже и в виде undefined, иначе GHC выдаёт предупреждения. Но ладно, закончим:

fib = getB . ((X 0 1) ^) where getB (X _ b) = b

Импортировав этот модуль (заметьте: экспортируется только fib, т. к. X — это деталь реализации), проверим правильность писанины:

я: fib [0..10]

GHCi: [0,1,1,2,3,5,8,13,21,34,55]

Разве не мило?

Фибоначчи, Haskell, O(log n): 1 комментарий

  1. Почему берутся матрицы именно указанного вида, можно легко увидеть, записав уравнения \(F_{n+1} = F_n + F_{n-1}, F_n = F_n\) как умножение матрицы на \((F_n, F_{n-1})^t\).

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

:) :D :( :E: ;) :yes: :no: :donno: more »

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.