Вычисление чисел Фибоначчи: различия между версиями

== Решение быстрым возведением матрицы в степень ==

Существует более эффективное решение данной задачи с помощью быстрого возведения матрицы в степень. Оно основано на следующем [[w:Числа_Фибоначчи|тождестве]]:

\begin{pmatrix} F_{n+1} & F_n \\

F_n & F_{n-1} \end{pmatrix}.</math>

Без учета затрат на реализацию длинной арифметики этот алгоритм требует <math>O(log(n))</math> времени и <math>O(1)</math> памяти.

 

Ниже этот алгоритм реализован на языке С. Будем считать, что:

:: <math>A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}</math> — временная матрица, используемая в алгоритме возведения в степень. Инициализируется матрицей <math>P</math>.

:: <math>R = \begin{pmatrix} rc & rd \end{pmatrix}</math> — вектор результатов (вторая строка матрицы <math>P^n</math>), инициализируется как вторая строка единичной матрицы.