Доброго времени суток.
Нашел в книге по программированию одну интересную задачу, долго бился и никак не могу её решить.
Вот как она звучит:

"Существует хитрый алгоритм получения чисел Фибоначчи за логарифмическое число шагов.
Вспомните трансформацию переменных состояния a и b процесса fib-iter из раздела 1.2.2:
a ← a + b и b ← a. Назовем эту трансформацию T и заметим, что n-кратное применение T, начи-
ная с 1 и 0, дает нам пару Fib(n + 1) и Fib(n). Другими словами, числа Фибоначчи получаются
путем применения Tn, n-ой степени трансформации T, к паре (1,0). Теперь рассмотрим T как
частный случай p = 0, q = 1 в семействе трансформаций Tpq, где Tpq преобразует пару (a, b) по
правилу a ← bq + aq + ap, b ← bp + aq. Покажите, что двукратное применение трансформации
Tpq равносильно однократному применению трансформации Tp′q′ того же типа, и вычислите p′ и
q′ через p и q. Это дает нам прямой способ возводить такие трансформации в квадрат, и таким
образом, мы можем вычислить Tn с помощью последовательного возведения в квадрат, как в
процедуре fast-expt. Используя все эти идеи, завершите следующую процедуру, которая дает
результат за логарифмическое число шагов"

Далее приведен незаконченный код на языке LISP:



Помогите найти решение.
Заранее благодарен.

Есть закрытая формула для вычисления чисел Фиобоначи.

По этой формуле можно быстро посчитать

А где найти эту формулу? Гугл ничего не дал.
Кроме того, мой вопрос состоял в решении конкретной задачи, а не в поиске формулы.

Если более полно - то для нахождения решения надо возвести матрицу 2x2 ( (0,1), (1,1) ) в n-ю степень, и тогда ответом будет число во второй строке, первой колонке. Как возводить матрицу в степень за логарифмическое время - метод бинарного возведения (или по книге "fast-exp"). Чаще всего его описывают применительно к числам, но он применим и для матриц:


Добавлено через 2 минуты и 48 секунд
Собственно одна такая матрица ( (0,1), (1,1) ) - она описывает однократное применение преобразования, о котором идёт речь в книге. Применяя n раз это преобразование, получаем матрицу, которая исходный вектор чисел Фибоначчи (F0, F1) = (0, 1) преобразует при умножении на себя в вектор (Fn, F{n+1}). Отсюда как раз и следует, что первый элемент результирующего вектора, Fn = 0 * A[1][1] + 1 * A[2][1] = A[2][1], и даст ответ.

p'=(+ (* p p ) (* q q))
q'=(+ (* 2 p q) (* q q))

Все что требовалось при решении задачи - это посчитать
  a'(i+1)=bq+aq+ap
  b'(i+1)=bp+aq
где
   a=b'q+a'q+a'p
   b=b'p+a'q
тогда получиться
  a'<-...
  b'<-b'(p*p+q*q)+a'(2pq+q*q) <=> b'p'+a'q'
следовательно
  p'=p*p+q*q
  q'=2pq+q*q
(Это можно проверить посчитав a' или подставив значения в программу или посчитав в матричном виде)