Thread: Really need help writing a SQRT Method in C

  1. #1
    Registered User
    Join Date
    Oct 2013
    Posts
    5

    Really need help writing a SQRT Method in C

    nth root algorithm - Wikipedia, the free encyclopedia

    This is the method I am trying to code in C.

    My teacher has asked us to use this to calculate sqrts in our program and NOT TO USE MATH.H OR ANY OTHER LIBRARY FILE.

    My problem is, that I could do this program if I could use math.h in about two freaking seconds.

    Since I can't, I have no idea how to use Newton's Method to calculate a SQRT, nor do I understand it's concept because well, this is coding NOT MATH CLASS =_=.

    Can anyone please walk me through on how I would code this concept into C?

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by Jimmy King View Post
    nth root algorithm - Wikipedia, the free encyclopedia

    This is the method I am trying to code in C.

    My teacher has asked us to use this to calculate sqrts in our program and NOT TO USE MATH.H OR ANY OTHER LIBRARY FILE.

    My problem is, that I could do this program if I could use math.h in about two freaking seconds.

    Since I can't, I have no idea how to use Newton's Method to calculate a SQRT, nor do I understand it's concept because well, this is coding NOT MATH CLASS =_=.

    Can anyone please walk me through on how I would code this concept into C?
    You could start by coding up a simple "guess and adjust" algorithm. Say, split N in half. Too low? Add half of that to the first half. Too high? Split in half again. Etc. Once you have a working program put together you can try experimenting with more advanced techniques.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Registered User
    Join Date
    Oct 2013
    Posts
    5
    I feel as though if I had a picture of what Newton's method looked like in C programming I could go at it but I don't. This is a class environment I am in, it wouldn't make sense if I had 0 guidance by my own teacher or 0 resources to look at regarding the situation.

    I don't believe learning by trial and error is what my teacher wants me to do nor do I think it will help me reach a conclusion.

    I either know how to translate Newton's Method into code or I don't.

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by Jimmy King View Post
    I feel as though if I had a picture of what Newton's method looked like in C programming I could go at it but I don't. This is a class environment I am in, it wouldn't make sense if I had 0 guidance by my own teacher or 0 resources to look at regarding the situation.

    I don't believe learning by trial and error is what my teacher wants me to do nor do I think it will help me reach a conclusion.

    I either know how to translate Newton's Method into code or I don't.
    Well, you're wrong. Finding your own solutions to problems is probably the #1 most important skill in programming. Once you've got something that "works" it's just a matter of refinement, after all...
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  5. #5

  6. #6
    Registered User
    Join Date
    Oct 2013
    Posts
    5
    Quote Originally Posted by Sebastiani View Post
    Well, you're wrong. Finding your own solutions to problems is probably the #1 most important skill in programming. Once you've got something that "works" it's just a matter of refinement, after all...
    The problem with that is if I do go about trial and error, how do I turn what I believe is good enough to the right answer? Just because I make something that might work (and it probably won't if the only process I'm allowed to use for sqrt is Newton's method) doesn't mean it is newton's method in C programming.

    I am attempting to implement Newton's Method into C programming to calculate the root of any given input. If I am told that I am being graded on how my program works and am told to use N's Method then that is what I have to do.

    I cannot use any other method, and you simply can't refine something that isn't Newton's method into Newton's method.

    So I turn back to the original question. How do I translate Newton's Method into C programming?

    EDIT: I am not saying your wrong by any means, and I do agree with your idea but I just don't think it applies to this given case.

    Thanks for the link, sadly it doesn't explain what happens when you have 4th or 6th or 80th roots. I gave it a good read and all I could take out of it was that I would be setting an equation in C and that I may have to prompt for guesses.
    Last edited by Jimmy King; 10-07-2013 at 01:47 AM.

  7. #7
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by Jimmy King View Post
    The problem with that is if I do go about trial and error, how do I turn what I believe is good enough to the right answer? Just because I make something that might work (and it probably won't if the only process I'm allowed to use for sqrt is Newton's method) doesn't mean it is newton's method in C programming.

    I am attempting to implement Newton's Method into C programming to calculate the root of any given input. If I am told that I am being graded on how my program works and am told to use N's Method then that is what I have to do.

    I cannot use any other method, and you simply can't refine something that isn't Newton's method into Newton's method.

    So I turn back to the original question. How do I translate Newton's Method into C programming?
    It's one thing if you know how do something one way but not another. But since you probably haven't the slightest clue how to calculate square roots with anything but a calculator it would indeed be a very good idea to first try to work out your own solution. Short of that, I'd say you should at least put together an attempt to program Newton's method from whatever you can gather from what you've read and then post it here for review...
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  8. #8
    Registered User
    Join Date
    Oct 2013
    Posts
    5
    Quote Originally Posted by Sebastiani View Post
    It's one thing if you know how do something one way but not another. But since you probably haven't the slightest clue how to calculate square roots with anything but a calculator it would indeed be a very good idea to first try to work out your own solution. Short of that, I'd say you should at least put together an attempt to program Newton's method from whatever you can gather from what you've read and then post it here for review...
    Yeah I'll definitely give it a shot, have been doing so. You're on the spot about me and sqrts though. I either know the square roots or I do them with a calculator, 4,9,81, and what not. if I was ever given a 5.93464306 I'd take the calculator out.

  9. #9
    11DE784A SirPrattlepod's Avatar
    Join Date
    Aug 2013
    Posts
    485
    Quote Originally Posted by Jimmy King View Post
    Thanks for the link, sadly it doesn't explain what happens when you have 4th or 6th or 80th roots. I gave it a good read and all I could take out of it was that I would be setting an equation in C and that I may have to prompt for guesses.
    Huh? The topic of this thread is "need help writing sqrt". Why are you bothering with the 4th, 6t and 80th "roots"?

    And no, you would not be prompting for guesses at all. Are you sure you read the link?

    Edit: Read the link again. The computer "guesses" a likely starting point and you iterate from that until the answer is "close enough"
    Last edited by SirPrattlepod; 10-07-2013 at 04:36 AM.

  10. #10
    Registered User
    Join Date
    May 2009
    Posts
    3,687
    1. Do you know Calculus?
    2. Is Calculus taught in class or a prerequisite for the class you are taking?

    If no to both of those, I think SirPrattlepod link is the correct choice to take.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  11. #11
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,532
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This info I quoted there, is straight from the website that Sir Prattlepod found and linked, into his answer, a few posts before this.

    I thought it required Calculus, but it didn't need it at all.

    Jimmy King, if you haven't clicked on the link posted by SirPrattlepod yet, you should. It's very simple to do understand.

  13. #13
    Registered User
    Join Date
    Apr 2013
    Posts
    1,646
    Quote Originally Posted by Jimmy King View Post
    Thanks for the link, sadly it doesn't explain what happens when you have 4th or 6th or 80th roots. I gave it a good read and all I could take out of it was that I would be setting an equation in C and that I may have to prompt for guesses.
    You don't need to prompt for guesses. Use the number/2 as your first guess. Newton's method converges quadratically, so the number of good bits doubles with each iteration.

    For the other roots, you'll need to use the general form of Newton's method, which is based on derivatives. For example, for the forth root of n, start with r = n/4 and use this formula repeatedly: r = 1/4 (3 r + n/(r^3)).

  14. #14
    Registered User ledow's Avatar
    Join Date
    Dec 2011
    Posts
    435
    I feel as though if I had a picture of what Newton's method looked like in C programming I could go at it but I don't. This is a class environment I am in, it wouldn't make sense if I had 0 guidance by my own teacher or 0 resources to look at regarding the situation.

    I don't believe learning by trial and error is what my teacher wants me to do nor do I think it will help me reach a conclusion.
    Honestly? Really? Are you genuinely thinking this?

    A class environment does not mean you are taken by the hand and told how to do every step. Not once you're out of nursery. And, shock, real life is just the same. That's why they say that school is supposed to prepare you for real life. Age 11-18 (depending on the country / education system) you're suddenly expected to be able to learn things for YOURSELF and motivate yourself to learn them.

    Zero resources? Maybe you should go find some. Like the two-second Google it takes. Back when I was a kid, that would have been an hour in the library, tops, but even that wouldn't be unduly burdensome for a homework task.

    I either know how to translate Newton's Method into code or I don't.
    Precisely. So your next logical step if you NEED to do that, but "don't know how" is to...

    Seriously, you're coming across as a child and I don't know why you've got the help you've had so far in this thread.

    this is coding NOT MATH CLASS =_=
    Believe it or not, coding and maths both have absolutely enormous overlaps. Take it from someone who's studied both. If you can't do one, you'll struggle with the other (doesn't mean you CAN'T do it, but you'll struggle), from the basics of binary up to how to manipulate coordinates in 3D space through matrix transforms, and beyond. Programming is how to express something in binary and simple operations that does something MUCH more complicated, and almost all the time along the way you have to use clever maths tricks to make it work. The sqrt example is almost perfect to demonstrate this - though some machines might have a "sqrt" instruction in their processor, most of them require someone to do clever maths to tell them how to get the same result using only boolean operators and simple arithmetic on integers (and in the case of the processor instruction, still some coder somewhere had to write the EXACT same thing but implement it in a logic circuit instead).

    If you haven't noticed, phrases like "converges quadratically" have already appeared in this thread. How much maths is involved in making a sqrt instruction? A lot.

    - Compiler warnings are like "Bridge Out Ahead" warnings. DON'T just ignore them.
    - A compiler error is something SO stupid that the compiler genuinely can't carry on with its job. A compiler warning is the compiler saying "Well, that's bloody stupid but if you WANT to ignore me..." and carrying on.
    - The best debugging tool in the world is a bunch of printf()'s for everything important around the bits you think might be wrong.

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Between Sir Prattlepod and rcgldr's post above, you have great info to help you get this started. Even I understand it, and my math ... well, let's not go into that...

    Time for Jimmy to get to work on it!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Encrypt method (from decrypt method)
    By mmmmmm in forum C# Programming
    Replies: 3
    Last Post: 09-19-2009, 10:35 AM
  2. writing code on paper method ..
    By transgalactic2 in forum C Programming
    Replies: 6
    Last Post: 04-15-2009, 04:41 PM
  3. sqrt()
    By caduardo21 in forum C Programming
    Replies: 2
    Last Post: 06-01-2005, 12:10 AM
  4. sqrt
    By modec in forum C Programming
    Replies: 3
    Last Post: 04-16-2003, 07:19 AM
  5. how sqrt ?
    By sambs1978 in forum C Programming
    Replies: 3
    Last Post: 09-20-2001, 08:14 AM