Archived

This topic is now archived and is closed to further replies.

PsYcHoPrOg

Square root

Recommended Posts

Ok, I''ve asked countless math teachers, professors, and majors, the same thing: How do you get the sqaure root of a number without a calculator, and without guessing? I want to make an algorithm for a simple calculator program. Obviously, it''s possible. Calculators can do it, a desktop can definately do it. But nobody knows how to do it! It''s always "they taught us that a long time ago, but I don''t remember. They don''t teach that anymore. It must''ve been the invention of the calculator..." If anybody knows how I could do this, LET ME KNOW, PLEASE!!!!! "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

Share this post


Link to post
Share on other sites
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!""


Share this post


Link to post
Share on other sites
Guest Anonymous Poster
If you do the algebra...

sqrt(x) = y for some number y.
=> x = y^2
=> log(x) = log(y^2), where log is the natural logarithm.
=> log(x) = 2 * log(y)
=> log(y) = log(x) / 2
=> y = exp(log(x)/2) (or e^(log(x)/2)), where exp is the exponential function.

This would be extremely slow of course, but exp and log are defined in math.h.

There is another method explained here:

http://forum.swarthmore.edu/dr.math/problems/steve.8.6.96.html

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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??

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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().

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
// in your program make sure you use
#include

// Lets say you wanted to evaluate ?50
// just type

float square_root_of_50;

square_root = sqrt(50);

Not much reason to do the square root yourself!

-Mike (mike-rules@excite.com)

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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...)

Share this post


Link to post
Share on other sites