История изменений
Исправление unanimous, (текущая версия) :
Вот полное решение задачи на octave
function [A] = fib_mod (n, k)
if (n >= 2)
nn = fix(n/2);
mm = n - nn;
if (nn == mm)
A = mod(fib_mod(nn, k)^2, k);
else
A = mod(fib_mod(nn, k)*fib_mod(mm, k), k);
endif
else
A = [1,1; 1,0];
endif
endfunction
Работает до n <=2^63 \approx 9x10¹⁸
Пример:
octave:66> tic; fib_mod(2^63, 100001), toc
ans =
5930 78715
78715 27216
Elapsed time is 0.029707 seconds.
диагональные элементы суть F[n+1] mod k, F[n-1] mod k, недиагональный — F[n] mod k
Исходная версия unanimous, :
Вот полное решение задачи на octave
function [A] = fib_mod (n, k)
if (n >= 2)
nn = fix(n/2);
mm = n - nn;
if (nn == mm)
A = mod(fib_mod(nn, k)^2, k);
else
A = mod(fib_mod(nn, k)*fib_mod(mm, k), k);
endif
else
A = [1,1; 1,0];
endif
endfunction
Работает до n <=2^63 \approx 9x10¹⁸
Пример:
octave:66> tic; fib_mod(2^63, 100001), toc
ans =
5930 78715
78715 27216
Elapsed time is 0.029707 seconds.