Thread: Really need help writing a SQRT Method in C

1. 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. Originally Posted by Jimmy King
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.

3. 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. Originally Posted by Jimmy King
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...

5. Originally Posted by Sebastiani
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.

6. Originally Posted by Jimmy King
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...

7. Originally Posted by Sebastiani
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.

8. Originally Posted by Jimmy King
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"

9. 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.

10. 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.

11. Originally Posted by Jimmy King
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)).

12. 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.

13. 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!