Title: Square Roots
Description: How to do them manualy
FrozenKnight - January 5, 2007 11:06 AM (GMT)
ok after much thought i decided to show some of the newbs how to make a function to solve for square roots. Warning: i don't expect anyone who doesn't know calc to be able to understand all of this.
Ok first i need to break down the function.
SQRT(n) = x
ok now for some algebra.
n = x^2
0 = x^2 - n
why did i solve for 0?
Well, because using calc you can solve any equation for 0.
Using Newtons method we can now solve for the square root.
| QUOTE (Newtons Method) |
| x - f(x)/f'(x) |
if you use this function recursively substituting x for the last value the function output then you will eventually end up with the result you are looking for. this function works best when you feed it with a value close to what you are looking for. another note is that there are 2 possible results for (x^2 - n) = 0, -SQRT(n) and SQRT(n) since were looking for the positive result we should assume that all negative results are invalid. (also all negative values for n should be invalid because negative square roots are imaginary values)
Ok some of you are wondering about f'(x) pronounced F prime of X. this basically means that you need to take the derivative of f(x). now i don't have enough time to give you a lesson covering most of Calc 1 I'll do this for you for the purposes of this turt.
if f(x) = x^2 - n = x*x - n
then f'(x) = 2 * x
Some of you already know where this is going. next and your right yes we can put this into C code.
But first a few notes. one we can just run this a set number of times which would give this a decent amount of accuracy. or we could check to make sure that our square root is accurate by multiplying our square root by it's self and checking how close it is to our original value n. I'll use the latter for checking because it gives a user settable amount of accuracy
and finally my code
| CODE |
#define accuracy (double)0.000001 //6 decimal places
double SQRT(double n)
{
if (n <= 0)
return 0; //check for imposable condision
double x = n/2; //init to half of n
while (fabs(x*x - n) > accuracy)
x = x - ((x*x - n)/(2 * x));
return x;
} |
note: i haven't tested this code but it should work. if you find any mistakes please tell me.
C-Man - January 5, 2007 05:25 PM (GMT)
| CODE |
double sqrt_ (double x,double a) {
double g = x;
while (fabs (x - g * g) > a)
g = (g + x/g)*0.5;
return g;
}
|
FrozenKnight - January 5, 2007 10:18 PM (GMT)
i wasn't showing an optimized method just a method
and it's the same formula
x = x - ((x*x - n)/(2 * x));
separate the equation and get the same denominator
x = (2*x*x)/(2*x)-(x*x)/(2*x)+(n)/(2*x)
combine like terms (2*(x*x)-(x*x)) = (x*x)
x = (x*x)/(2*x)+(n)/(2*x)
reduce and the (x*x)/(2*x) to x/2 then factor out 1/2 from the equation
x = (x + n/x) / 2
optimize by multiplying by reciprocal of 2 instead of dividing by 2
x = (x + n/x) * 0.5
or if you like you could substitute
x = ((2*x)+(n/(x*x)))/3
for
x = (x + n/x) * 0.5
to get a cube root (don't forget to change the x*x in the check to x*x*x)
tubapro12 - January 6, 2007 03:30 AM (GMT)
or an even less optimized version...
| CODE |
#define E (double)2.71828183
double sqrt(double a) {
double b;
b = pow(E, .5*log(a));
return b;
} |
lol
FrozenKnight - January 6, 2007 10:30 PM (GMT)
i was trying to show the newbs how to do a square root without having access to the advanced library's available with most compilers. as i have run into a few games and/or some compilers that don't have access to math.h.
BTW if your going to use the pow() function you could do a square root simply by b = pow(a, .5); you don't need to use a logarithm.
tubapro12 - January 7, 2007 12:28 AM (GMT)
true. but what would be the point of a sarcastically less optimized version that takes the easy route? :lol:
dr voodoo - January 7, 2007 10:51 AM (GMT)
How do you know it's slower? It might be hardware accelerated.
FrozenKnight - January 9, 2007 10:20 PM (GMT)
just for fun i decided to compute a function for x roots unfortunately i haven't quite figured out how to get it to represent fractional exponents so until then you will just have to deal with it using integer exponents.
| CODE |
#define accuracy (double)0.000001 //6 decimal places
double pow(double n, int p)
{
bool sign = 0;
int i;
double ret = n;
if (p == 0)
return 1;
if (p < 0)
{
sign = 1;
p = 0 - p;
}
for (i = 2; i <= p; ++i)
ret *= n;
if (sign)
return 1/ret;
return ret;
}
double fabs(double n)
{
if(n >= 0)
return n;
return 0-n;
}
double root(double n, int p)
{
int p2 = 1 - p;
double x = n/p;
if ((p&1 == 0) && (n < 0))
return 0;
while (fabs(n - pow(x, p)) > accuracy)
x = (n * pow(x, p2) - x)/p + x;
return x;
} |
| QUOTE (Edit) |
Code now tested and works fine.
Fixed: a syntax error in wehre pow returned type double double instead of double
Fixed: a math error in the pow function that razed to n^(p+1) rather than n^p
Fixed: a semicolon after the while loop in the root function which effectively created an infinite loop.
Update: added a check to prevent an infinite loop when trying to find find an even root of a negative number.
|
