Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C programming question

  1. Jun 23, 2004 #1
    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.
     
  2. jcsd
  3. Jun 23, 2004 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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!
     
  4. Jun 23, 2004 #3

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

    - Warren
     
  5. Jun 23, 2004 #4
    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.
     
  6. Jun 23, 2004 #5

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  7. Jun 24, 2004 #6
    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?
     
  8. Jun 24, 2004 #7

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  9. Jun 24, 2004 #8
    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 (Text):


    //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: Jun 24, 2004
  10. Jun 24, 2004 #9

    robphy

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: C programming question
  1. C++ program help (Replies: 2)

Loading...