Square root

Try Newtons Iteration:

square root







"You know you're obsessed with computer graphics when you're outside and you look up at the trees and think, "Wow! That's spectacular resolution!""

For sqrt(x) do the iteration y = (y + x/y)/2 to approximate sqrt(x), with some start value for y.

Visit our homepage: www.rarebyte.de.st

GA

What do you mean by "start value"? could you lend me an example?

E.g. if we want to calculate sqrt(3), we take e.g. 1 as start value, we get
1. y = (1 + 3/1)/2 = 2
2. y = (2 + 3/2)/2 = 7/4
3. y = (7/4 + 3/(7/4))/2 = ........

Visit our homepage: www.rarebyte.de.st

GA

Edited by - ga on June 20, 2000 8:33:56 AM

To calculate any sqrt stuff try this:

y = exp(ln(base)/power);

or

exp(number, 1/base)

[Sorry, Psycho, but after a several conversation with
some people i am no further sure whether this is correct]
-------
pseudo-programmer, webmaster @
digital impulse

Edited by - Wolti on June 22, 2000 9:36:30 AM

Thanks for your help, everybody! I appreciate it. Anyone else with suggestions, feel free to add to the thread. I need as many suggestions as I can get.

The easiest way to do is by x^(1/2) because:

x = y^2
ln(x) = ln(y^2)
ln(x) = ln(y) * 2
ln(x) / 2 = ln(y)
ln(x) * 1/2 = ln(y)
ln(x^(1/2)) = ln(y)
x^(1/2) = y

BTW, isn''t sqrt in the math.h to??

x^(1/2) isnt really a solution.

Like... you can write x^2 as x*x, and you can figure that out with using normal multiplication. But..how do you write x^(1/2) the only way is the sqrt(x)...which is back where you started.

Its true. I mean, x^(1/2) == sqrt(x), but it doesnt really help you figure it out with a pencil and paper.

sorry to be picky

Regarding the suggestion to use the exp(ln(x)/base), that''s a cool little formula that I''ve never seen, and it appears to work, but c''mon, if PsychoProg doesn''t want to use the sqrt() function, then he probably doesn''t want to use ln() or exp() either.

When we did a sqrt() function in my CS class in high-school, it went like this:

find the nearest two integer roots thru trial and error. These are your "low" and "high" values for the first loop cycle: find the average of these two (the "mid"), then square it and compare to your original value. If you''re too high, repeat the cycle, keeping your existing "low" value and using your existing "mid" value as your new "high" value. If you''re too low, repeat the loop using the existing "mid" and "high" values as the new "low" and "high" values. Keep going until you get within some predefined margin of error.

Well, I admit that x^(1/2) isn't a good soloution. However there are other methods. One is the Newton-Raphson method wich is a graphical solution, but can be used algebraically to. Its hard to explain without a good drawing, but I'll try.

We have the equation:

x^2 = 5
wich is equal to
x^2 - 5 = 0

First well have set a start value, this can be any value but it is a good idea to use the result of the equation, 5.
Insert the start value into the equation
5^2 - 5
this is obviusly not right. What we want do now is to find the x value where the points tagent is crossing the x-axis. We can found this point by the forumla x - ( y / slope ). The slope of the tagent is equal to the derivative in that point so we differentiate the equation x^2 - 5:
2x
Now we calculate the new point by inserting the values in the
x - ( y / slope ) function.
5 - ( ( 5^2 - 5 ) / 2*5 ) = 3
3 isn't the right root so we just start over, but with 3 as x value.

3^2 - 5 = 4
3 - ( ( 3^2 - 5 ) / 2*3 ) = 2 + 1/3 ~= 2.333
2.333^2 - 5 = 0.44444444
2.333 - ( ( 2.333^2 - 5 ) / 2*2.333 ) ~= 2.238
2.238^2 - 5 ~= 0.009

You can iterate like this until x^2 - y = 0, because then you have found the root. Not all values have a square root that is rational. And of course, you might not want to iterate a million times, so it is wise to set a limit of the number of iterations.

The advantage of the newton-raphson method over the method Eric described (I think it is called bisection) is that you generally find the right root with less iterations.
There is a applet describing this here http://users.ox.ac.uk/~heg/cmer/newton.htm


Edited by - Snale on June 28, 2000 3:48:47 PM

Edited by - Snale on June 28, 2000 3:53:04 PM

the easiest way is to just use logs

Pehaps, but as Ratman pointed out, such methods isn''t really availble when you are using pen and paper, and when programming, you could just use sqrt().

well there is a way to do it with derivatives but i dont have my calc book with me so i dont know the algorithim off hand

I wanted to state, before the thread continued, that I''m not going for finding a square root with a pen and pencil, I''m just trying to do it without using anything from math.h. I hope that that clears things up. Thanks for your suggestions!

"Remember, I'm the monkey, and you're the cheese grater. So no messing around."
-Grand Theft Auto, London

"It's not whether I win or lose, as long as I piss you off"
-Morrigan, Super Puzzle Fighter II Turbo

Then you do want a paper & pencil algorithm.

And I vaguely remember one from a long time ago... my algebra teacher taught us it - wasn''t in the book... or in any math book I''ve seen for that matter

About all I remember is that it was like long division but you had to drop 2 digits instead of the customary one...

Maybe this will spark someone else''s memory...

Newton iteration & the likes will work but a dead-on method does exist. If you can locate one (if they still exist) a manual draftman may remember the process - if they''re in thier sixties. (they had to do it all the time... until machanical calculators came out in the late 60''s or early 70''s...)