The square root of 2 (approximately 1.4142) is a positive real number that, when multiplied by itself, equals the number 2.
There are a number of algorithms for approximating √2 as a ratio of integers or as a decimal. The most common algorithm for this, which is used as a basis in many computers and calculators, is the Babylonian method for computing square roots, which is one of many methods of computing square roots. It goes as follows:
First, pick a guess, a0 > 0; the value of the guess affects only how many iterations are required to reach an approximation of a certain accuracy. Then, using that guess, iterate through the following recursive computation:
\(a_{n+1}=\frac{a_{n}+\frac{2}{a_{n}}}{2}=\frac{a_{n}}{2}+\frac{1}{a_{n}}\)
In general, suppose we want to evaluate the square root of a number n. Let’s assume the \(n=a^2+b\), where \(a^2\) is the biggest square number that is less or equal to \(n\).
Then, we can write it as:
\(n-a^2=b\)
or:
\(\left( {\sqrt n + a} \right)\left( {\sqrt n – a} \right) = b \Leftrightarrow \sqrt n – a = \frac{b}{{\sqrt n + a}}\)
and then:
\(\sqrt n = a + \frac{b}{{\sqrt n + a}}\)
Recursively replacing the \(\sqrt{n}\):
\(\sqrt n = a + \frac{b}{{2a + \frac{b}{{\sqrt n + a}}}}\)
or:
For \(n=2\) we have \(a=1\) and \(b=2-1=1\). So:
In general, we will write the sequence:
\({a_{n + 1}} = 1 + \frac{1}{{{a_n} + 1}}\)
In Python:
import numpy as np
import decimal
def twoSqrt(EPS):
decimal.getcontext().prec = 10000
x = decimal.Decimal(1)
t = x
# while error is still big
while abs(x*x - decimal.Decimal(2)) > EPS:
x = decimal.Decimal(1) + decimal.Decimal(1)/(decimal.Decimal(1)+t)
# converge the answer
t = x
return x
EPS = decimal.Decimal(1e-200)
r1 = twoSqrt(EPS)
r2 = decimal.Decimal(2).sqrt()
print('%.19f' % r1)
def twoSqrt(EPS):
decimal.getcontext().prec = 10000
myList = []
myCount = []
x = decimal.Decimal(1)
t = x
i = 0
myList.append(x)
myCount.append(i)
# while error is still big
while abs(x*x - decimal.Decimal(2)) > EPS:
x = decimal.Decimal(1) + decimal.Decimal(1)/(decimal.Decimal(1)+t)
# converge the answer
myList.append(x)
i = i+1
t = x
myCount.append(i)
plt.xlabel("iterations")
plt.ylabel("$\sqrt{2}$ values")
plt.plot(myCount,myList, marker = "x")
plt.savefig("sqrt2.jpg")
plt.show()
return xWith this code change, the following diagram can be obtained:
checksum: 38957cccdef0229b17dfce1dfb41c983f71f59d88a0e338d8718d21943258cae965609e9d16032c9fa87a0271e120d2c465784b7048fa0c9cd7dfecbe94e7680