Printable View
I would like to know exactly how sqrt() works. Either in assembly or C, doesn't matter. What I need it for, is for my Controller on our schools robot. It doesn't have any sqrt function, and I would write one if I knew how it worked. Can anybody help?
Does it have a pow() function? If it does, you could just do pow( x, 0.5 ).
Does the compiler have float/double arithmetic, or only ints?
Dave
Look up Newton-Raphson eg. here:
http://www.sosmath.com/calculus/diff/der07/der07.html
DavT
This code is in JAVA. I never wrote the C equivalent, but it should help you understand the math behind finding the square root of a number. This function finds the sqrt with .1 proximity.
Sorry it has no comments: My laziness. In short, it finds the closest perfect square to the number you want to find the sqrt for and then takes away perfect square from the whole thing.Code:public static double SquareRT(int num)
{
int cnt, x;
double sqrt, tmp;
for (cnt = 0; (cnt*cnt) <= num; cnt++);
if ((cnt*cnt) == num)
return cnt;
if ((cnt*cnt) > num)
/* now I'm pretty sure you need this unless
you changed the 'for' condition to (cnt*cnt) < num */
cnt--;
tmp = num - (cnt*cnt); /*find the difference of two squares. */
x = cnt * 2;/* length of formed rect. (inaccurate) */
sqrt = tmp / x; /* the width of rect. */
sqrt += cnt; /* add the width toe cnt */
return sqrt;
}
To understand the rest, you need to imagine a square with the area num. cnt will be a number whose square is closest to num.(ie. if num is 30, cnt is 5). Then you take away from num the square of cnt.(ie. 30 -25). If you can picture this, you'll see that a little strip would be left around the original square. If you make a rectangle from this strip, your rectangle will be 2*cnt in length and the area is the difference of the two areas (ie. the 30 - 25 = 5). You can find the width and add it to the cnt.
The inaccuracy comes in when you assume that 2 *cnt is the length of the rectangle you formed. You'll actually miss a little bit. I might actually try to see if I can fix the inaccuracy, but it's already accurate enough for most applications.
The 'if' statement is just overly-cautious just because when I wrote it I didn't exactly understand how the for loop worked.
Just copy the important parts - which is most of the code. Better yet, if you understand how it workes, write your own.
I desparately hope that is what you were asking or I just wasted a lot of time.
edit : added the math explanation of how to calculate the sqrt.
edit2: added comments to code.
some code to play around with:
http://www.functionx.com/cpp/examples/squareroot.htm
If you want to have your own algorithm, just use the BINOMIAL THEOREM
That is a joke right?Quote:
If you want to have your own algorithm, just use the BINOMIAL THEOREM