C programming question

  • Thread starter mathrocks
  • Start date
106
0
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 seperate 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

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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

Staff Emeritus
Science Advisor
Gold Member
10,166
34
Use the Newton-Raphson root finding method. It's quick and simple.

- Warren
 
102
0
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

Staff Emeritus
Science Advisor
Gold Member
10,166
34
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
 
106
0
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

Staff Emeritus
Science Advisor
Gold Member
10,166
34
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 [itex]f(x) = x^2 - m[/itex].

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

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

[tex]x_{n+1} = \frac{x_n^2 - m}{2 x_n}[/tex]

Where [itex]x_n[/itex] is the current value, and [itex]x_{n+1}[/itex] is the next value. Keep doing this iteration, plugging that [itex]x_{n+1}[/itex] back in as [itex]x_n[/itex]. 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
 
691
1
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.

Code:
//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 wont work if you cut and paste it. If you're learning C see if you can spot the 'error' in my implementation.
 
Last edited:

Related Threads for: C programming question

  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
6
Views
2K
Replies
2
Views
10K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
19
Views
3K
  • Last Post
Replies
2
Views
15K
Replies
2
Views
2K
Top