square root

[Atlantic]

I'm trying to write a program in C++ that does square roots.

 

does anyone know the algorithm for a square root using division, multiplication, addition, subtraction etc.

[wolfson]

Are you interested in writing an algorithm that is fast, or just one that works and you can see how it works? One way to do it is subdivision. You know that sqrt(x) must be between 0 and x (if x>0). So, guess y=x/2. Calculate y2 and see if it is larger or smaller than x. If y2>x then sqrt(x) must be between 0 and x/2, if y2<x then sqrt(x) must be between x/2 and x. If you know that sqrt(x) is between 0 and x/2, look at (x/4)2 to find if sqrt(x) is between 0 and x/4 or between x/4 and x/2. In general, once you know that sqrt(x) is between a and b, calculate y2 for y=(a+b)/2 and see if it is bigger or smaller than x. If it's bigger than sqrt(x) is between a and (a+b)/2, otherwise it's between (a+b)/2 and b. Keep doing this until the difference between your a and b is small.

 

A faster algorithm is called "Newton's method". You need to know a bit of calculus to know why this works though.

[bloodhound]

yeah. newton raphsons method is much much faster. but the function must be nice and several conditions must be satisfied for convergence to the solution ure looking for .

[wolfson]

[bloodhound]

the reason its quicker is that the error involved decreases as a square rather than linearly in the other method.

 

we havent been introduced properly wolfson:)