Compute Square Root of 2 Using Basic Operations

The first problem in Project PI goes as follows:

Using only basic operations $+$, $-$, $\cdot$, $/$ calculate the value of $\sqrt{2}$! The number $\sqrt{2}$ is a real number $x$, for which the square equals $2$: $x^2=2$!

The submitted answer has to have a precision of 10 significant digits.

I wanted to solve this problem without much researching to avoid yeah-I-totally-knew-that moments of self-deception and test myself. I started pondering, where have I encountered $\sqrt{2}$? The first thing that came onto my mind was a square with a length side of 1. Through Pythogorean theorem we get the diagonal of such square with

$$ a^2+a^2=c^2 \Rightarrow c^2 = 2 \Rightarrow c = \sqrt{2} $$

I started to think how to devise an iterative procedure to compute the value. I could not remember the Newton method for finding roots entirely. I had remembered that we had to know the value for $\cos{\frac{\pi}{4}} = \frac{\sqrt{2}}{2}$ in our high school. We can see this equality in the following figure. Using the unit circle the cosine of the angle $\frac{\pi}{4}$ equals to the $x$ value of the endpoint on the unit circle. Similarily the sine of the angle $\frac{\pi}{4}$ equals to the $y$ value of the endpoint on the unit circle. Since the sum of interior angles in a triangle always sum to $\pi$ the opposite angle is also equal to $\frac{\pi}{4}$ and we get an isosceles right triangle.

Using Pythagorean theorem we can determine the value of $a$:

Therefore the only question remains how to compute the cosine iteratively.

Cosine approximation with Taylor polynomials

We can approximate the cosine function with Taylor polynomials. I could not remember the exact formula for it )(even terms something something) but I know the Taylor polynomial for $exp$ function:

$$ \exp(x) = 1 + x + \frac{x^2}{2!} + … = \sum_{n=0}^{N}\frac{x^n}{n!} $$

and Euler’s formula $e^{i\theta}=\cos{\theta}+i\sin{\theta}$.

We have to get rid of sine function somehow to get the cosine on one side expressed with $exp$ function. I could use the fact that $\cos{\frac{\pi}{4}} = \sin{\frac{\pi}{4}}$. However if we express the Euler’s formula for $-\theta$, which is

since $\cos{-x} = \cos{x}$ and $\sin{-x} = -\sin{x}$. Then we can combine it together with the original formula for $\theta$:

Therefore we can now compute the cosine with the $exp$ polynomial:

 1import math
 2
 3def exp(x, N=100):
 4    return sum([x ** i / math.factorial(i) for i in range(0, N)])
 5	
 6def cos(phi, N=100):
 7    return (exp(phi * 1j, N) + exp(phi * -1j, N)) / 2
 8
 9	
10print(2*cos(math.pi / 4))

The result with $N=100$ is $1.414213562373095$ and this is accurate enough for submission. Problem solved.

Computing error

I wondered if I could estimate a minimum $N$ that would still give us the correct value. I took the $exp$ formula and assumed that $(N+1)th$ term $\frac{x^{(n+1)}}{(n+1)!}$ should be less than $10^-9$. Since $\sqrt{2}$ is around 1.41 and we care about the 10 significant digits, we have to make sure the remaining 9 decimals are correct. I iterated through the $n$s to find, which one satisfies this criteria:

 1def find_lowest_n(phi):
 2    for n in range(1, 100):
 3        if math.pow(phi, n) / math.factorial(n) <= exp(phi) * 10e-9:
 4            return n
 5
 6    raise IndexError("Lowest n is bigger than 100.")
 7
 8lowest_n = find_lowest_n(phi)
 9print(f"{lowest_n-1}: {2*cos(phi, lowest_n-1)}")
10print(f"{lowest_n}: {2*cos(phi, lowest_n)}")

and luckily enough I get the following result:

110: (1.4142136113665884+0j)
211: (1.4142135621438494+0j)

If we had only used $N=10$ the 8th digit would already be different from the correct result and does not pass submission.

I looked a bit into this and it appears I got a bit lucky. The Lagrange Error Bound formula gives us the error approximation Lagrange Error Bound¹

$$ |R_n| \leq \frac{f^{n+1}(z)|x-a|^{n+1}}{(n+1)!} $$

where $f^{n+1}(z)$ is the max value between $a$ and $x$ looking at the next unused term. The $(n+1)th$ derivative for $e^x$ is $e^x$ and we have to compute it for $x=\frac{\pi}{4}$, which is $\approx 2.2$ and $a = 0$, which is $1$. The maximum of both values is $2.2$ and remainder should therefore be written as:

$$ |R_n| \leq \frac{2.2(\frac{\pi}{4})^{n+1}}{(n+1)!} $$

whereas I used the value of $1$ in the beginning. However the result is the same, $N=11$. 😅

Conclusion

I challenged myself to figure this problem without looking up any material and I succeeded. It would most likely be more fruitful using Netwon’s method or bisection method as described in the problem’s solution but sometimes you just have to test yourself.