PsYcHoPrOg 115 Report post Posted June 17, 2000 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 0 Share this post Link to post Share on other sites

emfb 122 Report post Posted June 17, 2000 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!"" 0 Share this post Link to post Share on other sites

ga 126 Report post Posted June 18, 2000 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.stGA 0 Share this post Link to post Share on other sites

PsYcHoPrOg 115 Report post Posted June 19, 2000 What do you mean by "start value"? could you lend me an example? 0 Share this post Link to post Share on other sites

Guest Anonymous Poster Report post Posted June 19, 2000 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 0 Share this post Link to post Share on other sites

ga 126 Report post Posted June 20, 2000 E.g. if we want to calculate sqrt(3), we take e.g. 1 as start value, we get1. y = (1 + 3/1)/2 = 22. y = (2 + 3/2)/2 = 7/43. y = (7/4 + 3/(7/4))/2 = ........ Visit our homepage: www.rarebyte.de.stGAEdited by - ga on June 20, 2000 8:33:56 AM 0 Share this post Link to post Share on other sites

Wolti 122 Report post Posted June 22, 2000 To calculate any sqrt stuff try this:y = exp(ln(base)/power); orexp(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 impulseEdited by - Wolti on June 22, 2000 9:36:30 AM 0 Share this post Link to post Share on other sites

PsYcHoPrOg 115 Report post Posted June 22, 2000 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. 0 Share this post Link to post Share on other sites

Snale 122 Report post Posted June 27, 2000 The easiest way to do is by x^(1/2) because:x = y^2ln(x) = ln(y^2)ln(x) = ln(y) * 2ln(x) / 2 = ln(y)ln(x) * 1/2 = ln(y)ln(x^(1/2)) = ln(y)x^(1/2) = yBTW, isn''t sqrt in the math.h to?? 0 Share this post Link to post Share on other sites

Ratman 181 Report post Posted June 27, 2000 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 0 Share this post Link to post Share on other sites

Eric 138 Report post Posted June 28, 2000 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. 0 Share this post Link to post Share on other sites

Snale 122 Report post Posted June 28, 2000 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 = 5wich is equal tox^2 - 5 = 0First 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 equation5^2 - 5this 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 ) = 33 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.3332.333^2 - 5 = 0.444444442.333 - ( ( 2.333^2 - 5 ) / 2*2.333 ) ~= 2.2382.238^2 - 5 ~= 0.009You 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 PMEdited by - Snale on June 28, 2000 3:53:04 PM 0 Share this post Link to post Share on other sites

omegasyphon 100 Report post Posted June 28, 2000 the easiest way is to just use logs 0 Share this post Link to post Share on other sites

Snale 122 Report post Posted June 28, 2000 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(). 0 Share this post Link to post Share on other sites

Guest Anonymous Poster Report post Posted June 29, 2000 // in your program make sure you use#include // Lets say you wanted to evaluate ?50// just typefloat square_root_of_50;square_root = sqrt(50);Not much reason to do the square root yourself!-Mike (mike-rules@excite.com) 0 Share this post Link to post Share on other sites

omegasyphon 100 Report post Posted June 29, 2000 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 0 Share this post Link to post Share on other sites

PsYcHoPrOg 115 Report post Posted July 2, 2000 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 0 Share this post Link to post Share on other sites

Shannon Barber 1681 Report post Posted July 2, 2000 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...) 0 Share this post Link to post Share on other sites