Последовательность Фибоначчи быстрее, но с разными начальными числами (F [n] = F [n-1] + F [n-2])

Question

Последовательность Фибоначчи быстрее, но с разными начальными числами (F [n] = F [n-1] + F [n-2])

(начинающий здесь)

Я хочу знать, как найти n-й номер последовательности F [n] = F [n-1] + F [n-2].

Входные данные:

F[0] =  a;
F[1] =  b;
a,b < 101
N < 1000000001
M < 8; M=10^M;

А и В — начальные порядковые номера.

n — это n-й номер последовательности, которую мне нужно найти.

M по модулю, число быстро становится очень большим, поэтому F [n] = F [n]% 10 ^ M, мы находим остаток, потому что нужны только последние цифры n-го числа

Рекурсивный подход слишком медленный:

int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}

Решение динамического программирования, которое занимает время O (n), также слишком медленное:

f[i] = f[i-1] + f[i-2];

Хотя есть решения о том, как найти n-е число быстрее, если первые числа последовательности равны 0 и 1 (n-е число можно найти в O (log n)), используя следующую формулу:

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

(ссылка на формулу и код реализации с ней: https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/)

Но эта формула не работает, если начальные числа примерно 25 и 60. А рекурсивный подход слишком медленный.

Поэтому я хочу знать, как я могу найти n-й номер последовательности быстрее, чем O (n). Частичный код будет полезен.

Спасибо.

1

c++c++14 fibonacci sequence sequences

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Эта матрица:

A = / 1  1 \
\ 1  0 /

При умножении на вектор столбца (f_{п + 1}, е_N) где f_N это n-е число в последовательности Фибоначчи, даст вам вектор столбца (f_{п + 2}, е_{п + 1}), то есть он продвинет вас на один шаг. Это работает независимо от того, какими были начальные элементы последовательности.

Например:

/ 1  1 \ / 8 \  =  / 13 \
\ 1  0 / \ 5 /     \ 8  /

Таким образом, n-е число Фибоначчи является первым элементом A^н-1v, где v — вектор-столбец, содержащий f₁ и е₀, первые два числа в вашей последовательности.

Поэтому, если вы можете быстро рассчитать^н-1 по модулю некоторое число, это даст вам F_N. Это можно сделать с помощью Возведение в степень по квадрату, который работает в O (логн). Просто убедитесь, что выполняете по модулю после каждого умножения и сложения, чтобы числа не становились слишком большими.

7