How can I calculate Fibonacci of Fibonacci iteratively K times in sublinear time?

Question

For example for $K=3$ time and $N=6$,

$Fib(Fib(Fib(6))) =Fib(Fib(8)) =Fib(21) =10946 $

Note I need the answer modulo a large integer(say P). ie formally speaking calculate in most efficient way:

$Fib(Fib(Fib(.....K times.....Fib(N)))\ modulo\ P$ where P is a given integer.

My thoughts:

I am aware of how to calculate $i_{th}$ Fibonacci number $\ modulo\ P$ in $O(log(P))$. So taking that approach I can at best calculate it iteratively looping K times ie overall complexity will be $O(K\ log(P))$ but I believe it would be possible to do it in sublinear time, maybe something like $O(log(K)\ P^{0.25})$ or $O(log^2(K)\ P^{0.25})$ or $O(K^{0.25}\ P^{0.25})$

Here are the series for K = 2 and K = 3

Answer 1

As you are considering Fibonacci numbers modulo some number P, you could take advantage of Pisano periods.

Concretely, for $K = 3$, if $\pi(n)$ denotes the period of Fibonacci numbers modulo $n$ and $\pi^k$ the k-th iterate of $\pi$ (for example, $\pi^2(P) = \pi(\pi(P))$), you have this identity:

$Fib(Fib(Fib(v)))\ modulo\ P = Fib(Fib(Fib(v\ modulo\ \pi^3(P))\ modulo\ \pi^2(P))\ modulo\ \pi(P))\ modulo\ P$

This result can be obtained as follows:

• Fibonacci numbers modulo $P$ are $\pi(P)$ periodic,
• so $Fib(Fib(Fib(v)))\ modulo\ P = Fib(Fib(Fib(v))\ modulo\ \pi(P))\ modulo\ P$,
• Fibonacci numbers modulo $\pi(P)$ are $\pi^2(P)$ periodic,
• so $Fib(Fib(Fib(v)))\ modulo\ P = Fib(Fib(Fib(v)\ modulo\ \pi^2(P))\ modulo\ \pi(P))\ modulo\ P$,
• Fibonacci numbers modulo $\pi^2(P)$ are $\pi^3(P)$ periodic,
• so $Fib(Fib(Fib(v)))\ modulo\ P = Fib(Fib(Fib(v\ modulo\ \pi^3(P))\ modulo\ \pi^2(P))\ modulo\ \pi(P))\ modulo\ P.$

Of course, determining Pisano periods adds complexity, and some of the required $\pi^k(P)$ may not fit in 64 bits.