[KnifeTea]

I'm currently learning C, and this is from the book 'Programming in C'. Though I doubt it's language specific, or unique to this book, hence posting in this section.

I'm currently finding that I trip up / get confused on the phrasing of problems or the syntax of the math used.

The problem I'm working on currently is worded as :



I'm getting confused almost immediately when going through this text, as follows.

The number whose square root you want to obtain is divided by the initial guess and is then added to the value of guess. This intermediate result is then divided by 2.

So say I want to find the square root of the number 400. It's said already that the initial guess is 1 so...


divide 400 by 1 (the initial guess) = 400.

and is then added to the value of guess

So I have a separate variable to the initial guess called guess, or that the initial guess is guess and the result is added to this variable?

This intermediate result is then divided by 2

I'm not sure what is referred to by this intermediate result either... the division or the addition?


I'm sure this is very basic, but it just doesn't make sense to me! If anyone could walk me through it a bit that'd be ace.

[macosxnerd101]

So we're consider x² - 400[/sup], which has derivative 2x. Our initial guess is x₀ = 1.

So we take:
x₁ = 1 - (1² - 400)/2 = 1 + 1/2 = 400/2
x₂ = 400/2 - ((400/2)^2 - 400)/2 = 3/2 - 1/8 = 101.25

You then continue this process.

I have a tutorial covering the Newton method which has another example.

This post has been edited by macosxnerd101: 26 March 2014 - 01:04 PM
Reason for edit:: Fixed typos

[KnifeTea]

Cheers Mac, I can't follow your answer though, like I said I'm struggling with the syntax etc.

Where does x2 - 400[/sup] come from? What is sup ?

I'll read the tutorial nice one, though whether it makes sense to me or not

can't follow that tutorialcheers though

[macosxnerd101]

You're trying to approximate sqrt(400) right? So isn't sqrt(400) a solution to f(x) = x² - 400? That's where the function came from. I take an initial guess, x₀ = 1 and subtract out from it f(x_{0/sub])/f'(x[sub]0}).

Perhaps in pseudo-code, it will make more sense:

newtonsMethod(int target, double errorMargin)
    approximation := 1 //start with the initial guess, here you chose one

    while |target - approximation * approximation| > errorMargin
       approximation := approximation - f(approximation)/f'(approximation)

    return approximation
end newtonsMethod

function f(int approximation)
   return approximation * approximation - 400
end function

//the derivative function
function f'(int approximation)
   return 2 * approximation
end function

This post has been edited by macosxnerd101: 26 March 2014 - 01:02 PM
Reason for edit:: Square approximation

[KnifeTea]

You're trying to approximate sqrt(400) right?


yep

So isn't sqrt(400) a solution to f(x) = x² - 400?

I don't know. I'm guessing that the square root will solve what ever this problem represents... But f(x) = x doesn't mean anything to me. So the rest of the explanation is lost because I don't follow the beginning.

Perhaps in pseudo-code, it will make more sense:


I'll try and work through this, though it would have been easier in C syntax (for me to follow)

so newtonsMethod(400, NOT SURE WHAT TO PUT HERE, 0?)


approximation := 1 I've never seen that := sign before, but I'm guessing that it's the same as = in C.

while |target - approximation| > errorMargin
approximation := approximation - f(approximation)/f'(approximation)

So I'm guessing that the | | signs are the same as brackets in C...? So

while ( (400 - 1) > errorMargin)
approximation = approximation - f(approximation)/f'(approximation);

so the f function first :

f(approximation) = f(1) = (1 * 1) - 400 which returns -399.

f' function now :

f'(approximation) = f'(1) = (2*1) so the returned int is 2.

so back to the while :

approximation = approximation - (-399 / 2);

or

approximation = 1 - (-199) which is -198.

So after one run of the while loop approximation is now equal to -198.

400 - -198 = 598, which is larger than the error margin of 0 (not sure what the error margin should have been...gone with zero)


So the loop is run again :


approximation = approximation - f(598)/f'(598);

so f first :

(598 * 598) - 400 = 357,204 (at this point I'm feeling something is wrong, I'll see this loop out though...)

so f returns 357, 204


Ah no, now I'm thinking that I might have confused the local variables, phuq.

Hopefully I've been clear enough to show any obvious mistakes / misunderstandings though

cheers

[macosxnerd101]

Quote

I don't know. I'm guessing that the square root will solve what ever this problem represents... But f(x) = x doesn't mean anything to me. So the rest of the explanation is lost because I don't follow the beginning.

I'm not sure if you're in a numerical analysis class or if this is an intro to programming assignment. I think if you're going to be working with computational math, you might want to take some time to understand the basics of functions, as presented in a high school algebra class. It'll make weeding through the algorithms a bit easier. At the very least, you can go on Wolfram Alpha to graph the function.

As for the algebra, isn't sqrt(400)² = sqrt(400) * sqrt(400) = 400? So sqrt(400)² - 400 = 0. Does that make sense?

Quote

so newtonsMethod(400, NOT SURE WHAT TO PUT HERE, 0?)

The Netwon Method algorithm produces an approximation. The epsilon says that we want our approximation and the actual value to be no more epsilon apart. The bars represent absolute value. It's standard notation you should have seen in a high school Algebra class, if not before.

Quote

Hopefully I've been clear enough to show any obvious mistakes / misunderstandings though

Actually, you've caught a few of mine. I've updated my example in the prior post to handle this.

Quote

approximation = approximation - (-399 / 2);

or

approximation = 1 - (-199) which is -198.

Not exactly. Don't round down to an int. Keep the decimal place. So 1 - (-399/2) = 401/2.

[KnifeTea]

cheers mac...

Quote

I'm not sure if you're in a numerical analysis class or if this is an intro to programming assignment

The later... though it's not with a teacher as such, I'm currently learning solo.

Quote

you might want to take some time to understand the basics of functions, as presented in a high school algebra class

Yeah it seems so! A lot of the time I find that I don't have any of the shorthand necessary to read through simple explanations (such as what you provided me) so it spirals into a barrage of crappy paragraphs (from my end)

Quote

go on Wolfram Alpha to graph the function

Haven't used / heard of this, I'll try and get familiar with it though

Quote

As for the algebra, isn't sqrt(400)2 = sqrt(400) * sqrt(400) = 400? So sqrt(400)2 - 400 = 0. Does that make sense?

Yeah, I'm fine with that

Quote

The Netwon Method algorithm produces an approximation. The epsilon says that we want our approximation and the actual value to be no more epsilon apart

Right - so where's the actual value worked out in that program? I'm guessing that the actual value is the actual square root of something... So the actual value (in this context) for 16 would be 4. And if we were working to an accuracy of 0.1 then the approximate value of 11 would be within 0.1 of 3.316624....

Quote

The bars represent absolute value. It's standard notation you should have seen in a high school Algebra class, if not before

Honestly never seen them before
I've recently started going through some stuff over at the khan academy, there seem's to be mixed reviews on it's values... I didn't really find much else though (open to any suggestions here)

Quote

Actually, you've caught a few of mine

Throw enough dirt and some might stick ha

Quote

Not exactly. Don't round down to an int

Ah damn yeah, I was truncating the answer there...

[macosxnerd101]

Quote

Right - so where's the actual value worked out in that program? I'm guessing that the actual value is the actual square root of something... So the actual value (in this context) for 16 would be 4. And if we were working to an accuracy of 0.1 then the approximate value of 11 would be within 0.1 of 3.316624....

The resultant value will be returned from the approximation variable I used. Your understanding of accuracy is correct. For 16, even though sqrt(4) is rational, you may still get an approximation within 0.1 of 4 based on the epsilon.

Quote

Honestly never seen them before
I've recently started going through some stuff over at the khan academy, there seem's to be mixed reviews on it's values... I didn't really find much else though (open to any suggestions here)

I like Paul's Notes for a gentle introduction. I've used it many times to supplement for other classes.

[KnifeTea]

Quote

The resultant value will be returned from the approximation variable I used. Your understanding of accuracy is correct. For 16, even though sqrt(4) is rational, you may still get an approximation within 0.1 of 4 based on the epsilon.

The approximation variable was 1... So theoretically could this program (the pseudo one that you made, or just the theory in general) return a value of 3, 4, or 5 for the square root of 16? (As they're all within 1 of 4...) Or is that silly talk?

Quote

I like Paul's Notes for a gentle introduction. I've used it many times to supplement for other classes.

cheers for the link - where to start on that site then?

[macosxnerd101]

Quote

The approximation variable was 1.

The initial guess was 1. Remember that the approximation changes as you continue to iterate.

Quote

return a value of 3, 4, or 5 for the square root of 16? (As they're all within 1 of 4...) Or is that silly talk?

If you modify the initial guess or the epsilon value, it possibly could.

Quote

where to start on that site then?

I'd probably start with Algebra.