Генерация чисел Фибоначи за O(log n)

[lexand]

доброго времени суток

Купил книгу "Структура и интерпретация компьютерных программ" для само-развития, понимания и пр

[url]http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4[/url]
задание 1.19

решить само задание не сложно
просто два раза применить указанные преобразования сгруппировать похожие члены и дело в шляпе

конкретно интересует вопрос откуда вообще взялось такое преобразование? на основании чего его можно вывести?
$a \leftarrow bq+aq+ap$
$b \leftarrow bp+aq$

я пробовал зайти со стороны двойного применения матрици/оператора
$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} $ что в общем виде можно записать как $ \begin{pmatrix} k & l \\ l & m \end{pmatrix} $
но это ничего не дало, по крайней мере я ничего не заметил что можно с этим
$\begin{aligned} k &\leftarrow k^2+l^2 \\ l &\leftarrow kl+lm \\ m &\leftarrow l^2+m^2\\ \end{aligned} $
сделать

спасибо

[arseniiv]

Матрицу (и не только матрицу, но сейчас не об этом) можно возводить в $n$-ю степень за $O(\log n)$ умножений.

[lexand]

это то понятно

как раз
$\begin{aligned} k &\leftarrow k^2+l^2 \\ l &\leftarrow kl+lm \\ m &\leftarrow l^2+m^2\\ \end{aligned} $
если подставить в алгоритм (ну и немного допилить) вместо p и q
и будет считать за $O (log \ n)$ так как это именно возведение в квадрат (тоесть применение двойного преобразования) матрици
$ \begin{pmatrix} k & l \\ l & m \end{pmatrix} $

тут вопрос в том - откуда взялось преобразование указанное в книге?
как к нему прийти?

[Urnwestek]

Да это очень известный трюк. Попробуйте обобщить задачу и написать матрицу перехода для последовательности $f_n = c_{1} f_{n-1} + c_{2} f_{n-2} + ... + f_{n-k} c_{k}$ считая, что $c_1, c_2, ..., c_k$ — заданные (фиксированные) коэффициенты.

[arseniiv]

lexand
А, извините; так вы не то пишете. Надо применить такую матрицу к вектору $\begin{bmatrix} a \\ b \end{bmatrix}$, получая вектор $\begin{bmatrix} a' \\ b' \end{bmatrix}$.

-- Чт ноя 21, 2013 01:02:12 --

Там немного другое преобразование получится, конечно… Но к нему приводимо.

[svv]

В Википедии, в статье Числа Фибоначчи, приводится такое свойство:
$F_{n+m}=F_{n-1}F_{m}+F_{n}F_{m+1}$

Отсюда следует (если заменить $n$ на $n+1$):
$F_{n+m+1}=F_{n}F_{m}+F_{n+1}F_{m+1}$

Эти две формулы можно объединить в одну матричную:
$\begin{bmatrix}F_{n+m+1}\\F_{n+m}\end{bmatrix}=\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix} \begin{bmatrix}F_{m+1}\\F_{m}\end{bmatrix}$

Матрица равна
$T^n=\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}=\begin{bmatrix}F_{n}+F_{n-1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}$

Если обозначить $p=F_{n-1}$, $q=F_n$, то
$T^n=\begin{bmatrix}p+q&q\\q&p\end{bmatrix}$
Умножение её на вектор с компонентами $a, b$ и даёт то, что в статье:
$\begin{bmatrix}p+q&q\\q&p\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}=\begin{bmatrix}bq+aq+ap\\bp+aq\end{bmatrix}$

[lexand]

ааа
на 5 секунд не успел, теперь не докажешь что сам додумался

я только сейчас понял в чем была моя ошибка - я ввел три коэффициента в матрицу, в то время как k можно было выразить как $k=l+m$ что дало бы тот же результат

Вики читал не внимательно, может к счастью - хотел сам додуматься

всем огромное спасибо