How to reduce calculation time for iterative functions that involve squaring a number in every iteration. Working with numbers in millions of digits Introduction
I have the below function that is iterated a fixed number of times n. The result of the previous is used in the next iteration and so on. Until we have done n iterations
f(x) = x2 - 2
We always start with x = 4. This means our first iteration looks as below
42 - 2 = 14
x = 14 will be used in the next iteration and so on until n iterations are done. Then we stop.
Problem
The number of iterations that are to be done is in millions(up to 9 digits). If you see, squaring numbers these many times is not feasible at all even by a computer. The reason is the number of digits in the number resulting from each iteration goes up to more than a million digits in just a few hundred iterations. And we know the larger the number the more time and space it takes. Surely, this needs to be optimized.
Partly solution
I tried breaking down the above function to allow better calculation times. Below is what I did.
I broke the function into two parts


*

*The x2 part

*The -2 part


If we are squaring a number for n number of times, we can make it easier by doing the below.
x(2n) - Where n is the number of iterations to be done. So, we raise x to the power of 2n
e.g: n = 3, x = 4
Iterative


*

*42   = 16

*162  = 256

*2562 = 65536


This can also be done without iteration with x(2n) as:
4(23) = 4(8) =  65536 | Same result without any iteration
Since we are always starting with 4, we can always use the below
4(2n)
This will improve the calculation time drastically because I will always be using the number as a power of 4 for other calculations.
Missing part
If you see the original function, it has the -2 part and the result is used in the next iteration and so on up to n iterations
f(x) = x2 - 2
This has not been applied to 4(2n)
For us to make the new solution same as the original equation, we need to subtract something.
such that, 4(2n) - y. 
Where y is the something we need to subtract.
The issue now is, how can we find the 'y' in this scenario?
Using iterations here to find y is okay but it is preferred to not use if the number can get very large(more than hundreds of digits). I have not calculated how large this number can get. 
It'll also be appreciated if you let me know if you find any flaws in my math.
 A: Well, if you start with $x_0=4$ and continue with $x_{n+1}=x^2_n-2$, it's easy to prove (by induction) that $$x_n=(2+\sqrt{3})^{2^n}+(2-\sqrt{3})^{2^n}\tag1.$$ That shows that the difference $y_n=4^{2^n}-x_n$ is asymptotically even much bigger than $x_n$. Since all positive powers of $2-\sqrt{3}$ are $<1$, an immediate consequence of (1) is $$x_n=\left\lceil(2+\sqrt{3})^{2^n}\right\rceil\tag2.$$
Now, it depends what you are intending to achieve with the whole thing: If you need just the most significant figures, (2) will be enough. If you need the last few digits, or more generally $x_n\pmod{p^k}$ with some prime $p$, you'll use (1). That's especially  easy if $3$ is a quadratic residue $\pmod p$. It's possible also if it isn't, but a bit more complicated.
EDIT: The derivation is simple, if we assume that the starting value $x_0>=2$. Then, we can assume $x_n=u_n+\dfrac1{u_n}$ with $u_n\ge1$, and we obtain
$$u_{n+1}+\frac1{u_{n+1}}=\left(u_n+\dfrac1{u_n}\right)^2-2=u^2_n+\dfrac1{u^2_n},$$  implying $$u_{n+1}=u^2_n.$$ The starting value is $$u_0=\frac{x_0+\sqrt{x^2_0-4}}2.$$
