Числа Фибоначчи связаны с возведением в степень через матричный метод. 24

Для любого n справедливо равенство: (11 10)𝑛 = (𝐹�𝑛��+� 1 𝐹�𝑛��−� 1). 2 Оно означает, что квадратная матрица 2 на 2 со значениями 1, 1, 1, 0 в степени n (нужный номер члена в ряду Фибоначчи) будет давать новую квадратную матрицу такой же размерности со значениями Fn+1, Fn, Fn, Fn-1. 2

Возведение матрицы в степень n — это умножение матрицы саму на себя n количество раз. 2 Например, если взять матрицу с 6-м номером Фибоначчи 8: [8,5 | 5,3], умножить её на саму себя и получить первое число новой матрицы (88+55) = 89, это уже 11-й номер Фибоначчи. 1 Если полученную матрицу умножить на саму себя ещё раз, получится n4, далее n8, n*16 и т.д.. 1 Это сильно ускоряет процесс и позволяет достичь нужного номера за время O(log2 n). 1