How can I calculate Fibonacci of Fibonacci iteratively K times in sublinear time? 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
 A: 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.
