What are some algorithms used to find square root(or to approximate them)? Say #sqrt(2), sqrt(7)#

1 Answer
Apr 3, 2015

Probably the best approach is to use Newton's Method.

For example, for #sqrt(7)#, you could note that this number is a root of the function #f(x)=x^{2}-7#. Newton's Method is an iterative scheme based on the equation #x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})}=x_{n}-\frac{x_{n}^{2}-7}{2x_{n}}# (the derivation of this is based on finding the #x#-intercept of the tangent line to the graph of #f# at the point #(x_{n},f(x_{n}))#). Based on the initial guess #x_{0}=3#, we would get #x_{1}=3-\frac{9-7}{6}=3-\frac{1}{3}=\frac{8}{3}\approx 2.66667# as our next approximation (if you square this number, you'll get #\frac{64}{9}\approx 7.11111#).

If you use Newton's Method one more time here, you'll get #x_{2}=\frac{8}{3}-\frac{64/9-7}{16/3}=\frac{8}{3}-\frac{1/9}{16/3}=\frac{8}{3}-\frac{1}{48}=\frac{127}{48}\approx 2.64583333#, which is very close to #\sqrt{7}#.

In the general case where you want to approximate #\sqrt(c)# for some #c>0#, the recursive equation from Newton's Method simplifies to #x_{n+1}=\frac{x_{n}^{2}+c}{2x_{n}}# (based on the function #f(x)=x^{2}-c#). Pick #x_{0}# to be an integer such that #(x_{0}-1)^{2}< c \leq x_{0}^{2}# and already the number #x_{1}# from Newton's Method will be pretty close to #\sqrt{c}#.