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

1 Answer
Apr 3, 2015

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

For example, for sqrt(7)7, you could note that this number is a root of the function f(x)=x^{2}-7f(x)=x27. 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}.