How to reduce calculation time for iterative functions that involve squaring a number in every iteration. Working with numbers in millions of digits

Question

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) = x² - 2

We always start with x = 4. This means our first iteration looks as below

4² - 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

1. The x² part
2. The -2 part

If we are squaring a number for n number of times, we can make it easier by doing the below.

x⁽²ⁿ⁾ - Where n is the number of iterations to be done. So, we raise x to the power of 2ⁿ

e.g: n = 3, x = 4

Iterative

1. 4² = 16
2. 16² = 256
3. 256² = 65536

This can also be done without iteration with x⁽²ⁿ⁾ as:

4⁽²³⁾ = 4⁽⁸⁾ = 65536 | Same result without any iteration

Since we are always starting with 4, we can always use the below

4⁽²ⁿ⁾

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) = x² - 2

This has not been applied to 4⁽²ⁿ⁾

For us to make the new solution same as the original equation, we need to subtract something.

such that, 4⁽²ⁿ⁾ - 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.

Answer 1

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.$$