C Prog Q: Find Dist btwn 2 Sets of Points Without math.h

[mathrocks]

I have a question about a C program that I'm trying to write. I need to write a program that finds the distance between two sets of points (x1, y1) and (x2, y2) without using the math.h header file. I'm currently doing functions in my class, so I suppose I have to write a separate function that calculates the distance. But what I'm having trouble with is how to take the square root without using the math library.

 

[Hurkyl]

You could brute force through steps of a fixed size. You could do a binary search. You could remember back to your math classes and use a numerical approximation. You could look up a numerical approximation in a reference book. Depending on your task, the squared difference might even be enough, meaning you don't have to take the square root!

 

[chroot]

Use the Newton-Raphson root finding method. It's quick and simple.

- Warren

 

[Goalie_Ca]

Which compiler do you use? You could easily embed 1 line of asm (which is essentially what math.h does).

I'm asking about which compiler because the syntax of inline asm varies from compiler to compiler. I'm sure you'll find it on google though.

 

[chroot]

Yes, you could certainly talk to the floating-point unit directly via asm, but I don't really think that's what the teacher intends for him to do. I believe this assignment is designed to teach C, not x86 architecture.

- Warren

 

[mathrocks]

Wow, all great responses but I guess I didn't tell you guys my level of programming. This is my first programming class, it's a beginners course and the most we've done is recursive functions and this problem was in that section. Any way to do it really simple?

 

[chroot]

I believe my answer is quite simple to implement. The Newton-Raphson method is an iterative way to numerically find a zero of a function.

If you're looking for the square root of some number m, it should be obvious that you're looking for the zero of the function f(x) = x^2 - m.

The first derivative of this function is f^\prime (x) = 2x.

The Newton-Raphson method begins with a guess. Any guess will do, but a bad guess will require more iterations to converge on the final answer. To apply the Newton-Raphson method, plug your guess into the relation

x_{n+1} = \frac{x_n^2 - m}{2 x_n}

Where x_n is the current value, and x_{n+1} is the next value. Keep doing this iteration, plugging that x_{n+1} back in as x_n. You'll see that after five or ten iterations, you've calculated a very very good approximation of the square root.

You could also keep iterating until the value only changes by say 0.0001 or less from one iteration to the next, guaranteeing at least that much precision.

You should be able to write this code in something like three or four lines of C code. If you need additional help, please let me know.

- Warren

 

[faust9]

Use Newtons method as already stated.
Here, this process should help: http://www.merriampark.com/bigsqrt.htm

You can do this as a recursive function, but that's not required.

//the non-recursive way to do it.
//doing this recursively is just as easy, good luck.
double squareRoot(double numToRoot, double guess)
{
	while(true) //sets up an infinite loop
	{
		//function to approximate the root
		double n=((numToRoot/guess) + guess)/2; 
		if (n==guess) //breaks out of loop when root is found
		break;
		guess=n; //reassignes guess for next iteration of loop
	}
	return guess; //returns the root to the function call.
}

Just as an aside, though you're learning about recursive functions, you should also avoid them like the plague unless absolutely necessary. Recursive functions can become unweildy very quickly.

Well, good luck.

[edit] Also, the above code probably won't work if you cut and paste it. If you're learning C see if you can spot the 'error' in my implementation.

 

[robphy]

This page "How to calculate square roots" by Paul Hsieh
http://www.azillionmonkeys.com/qed/sqroot.html
may be entertaining... but probably beyond the scope of the course.