anonymous
  • anonymous
how to find the square root of a number in java without using the squrt function
MIT 6.00 Intro Computer Science (OCW)
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
blurbendy
  • blurbendy
you'd probably have to write your own method to do it
whpalmer4
  • whpalmer4
The Babylonian method is one you could easily do. https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
anonymous
  • anonymous
http://dpaste.com/1259775/

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

eSpeX
  • eSpeX
You could also try the Newtonian method. https://en.wikipedia.org/wiki/Newton%27s_method
whpalmer4
  • whpalmer4
The Babylonian method is very simple to implement and converges much faster than the binary search approach referenced by @bwCA. >>> def babysqrt2(x,tolerance): ... guess=x/2.0 ... while True: ... print "guess = ", guess ... if -tolerance <= (guess*guess)-x < tolerance: ... return guess ... guess = (guess + x/guess)/2 ... >>> babysqrt2(1000,0.00001) guess = 500.0 guess = 251.0 guess = 127.492031873 guess = 67.6678296579 guess = 41.2229503947 guess = 32.7406409949 guess = 31.6418602354 guess = 31.6227823565 guess = 31.6227766017 31.622776601684315 >>> babysqrt2(1000,0.000001) guess = 500.0 guess = 251.0 guess = 127.492031873 guess = 67.6678296579 guess = 41.2229503947 guess = 32.7406409949 guess = 31.6418602354 guess = 31.6227823565 guess = 31.6227766017 31.622776601684315 >>> babysqrt2(2,0.001) guess = 1.0 guess = 1.5 guess = 1.41666666667 guess = 1.41421568627 1.4142156862745097 >>> babysqrt2(2,0.00001) guess = 1.0 guess = 1.5 guess = 1.41666666667 guess = 1.41421568627 1.4142156862745097 Compare with the hi/lo method: >>> print sqrt(100) entering iter_sqrt( 100 , 100 , 0 ) entering iter_sqrt( 100 , 50.0 , 0 ) entering iter_sqrt( 100 , 25.0 , 0 ) entering iter_sqrt( 100 , 12.5 , 0 ) entering iter_sqrt( 100 , 12.5 , 6.25 ) entering iter_sqrt( 100 , 12.5 , 9.375 ) entering iter_sqrt( 100 , 10.9375 , 9.375 ) entering iter_sqrt( 100 , 10.15625 , 9.375 ) entering iter_sqrt( 100 , 10.15625 , 9.765625 ) entering iter_sqrt( 100 , 10.15625 , 9.9609375 ) entering iter_sqrt( 100 , 10.05859375 , 9.9609375 ) entering iter_sqrt( 100 , 10.009765625 , 9.9609375 ) entering iter_sqrt( 100 , 10.009765625 , 9.9853515625 ) entering iter_sqrt( 100 , 10.009765625 , 9.99755859375 ) entering iter_sqrt( 100 , 10.0036621094 , 9.99755859375 ) entering iter_sqrt( 100 , 10.0006103516 , 9.99755859375 ) entering iter_sqrt( 100 , 10.0006103516 , 9.99908447266 ) entering iter_sqrt( 100 , 10.0006103516 , 9.99984741211 ) entering iter_sqrt( 100 , 10.0002288818 , 9.99984741211 ) 10.000038147 >>> print sqrt(2) entering iter_sqrt( 2 , 2 , 0 ) entering iter_sqrt( 2 , 2 , 1.0 ) entering iter_sqrt( 2 , 1.5 , 1.0 ) entering iter_sqrt( 2 , 1.5 , 1.25 ) entering iter_sqrt( 2 , 1.5 , 1.375 ) entering iter_sqrt( 2 , 1.4375 , 1.375 ) entering iter_sqrt( 2 , 1.4375 , 1.40625 ) entering iter_sqrt( 2 , 1.421875 , 1.40625 ) 1.4140625
anonymous
  • anonymous
Actually, the Babylonian method is equivalent to Newton's method, so you could use either one. Proof: Newton's method: NewGuess = Guess - (f(Guess) - f(x_final))/f'(Guess) where f(x) is the inverse function of the function you are calculating. So: f(x) = x^2 f'(x) = 2x f(x_final) = Whatever you're trying to find the square root of... Let's call it A, for answer That gives us... NewGuess = Guess - (Guess^2 - A)/(2*Guess) Simplify: NewGuess = Guess - Guess^2/(2*Guess) - A/(2*Guess) NewGuess = Guess - 1/2*Guess + 1/2 * A/Guess NewGuess = (Guess + A/Guess)/2 ^ The Babylonian Method
anonymous
  • anonymous
Oh, so if you want it in java (even though the course is in python...) I'd write the method: public static double sqrt(double x) { double guess = 0.5 * x; double oldGuess = 0.0; while (guess != oldGuess) { oldGuess = guess; guess = (guess + x/guess) / 2.0; } return guess; } That should do it. If you want the method in python: def sqrt(x): guess = 0.5 * x oldGuess = 0.0 while guess != oldGuess: oldGuess = guess guess = (guess + x/guess) / 2.0 return guess
whpalmer4
  • whpalmer4
Numerical code like this: while guess != oldGuess: oldGuess = guess guess = (guess + x/guess) / 2.0 return guess is not necessarily a good idea. I'm not saying it will happen here, but you can get into states with some computations where the result bounces back and forth, never quite giving you a true equality. Numerical analysis is a decidedly non-trivial area of research. Just because an algorithm looks good on paper doesn't mean that implementing it on a computer will be a happy experience.
anonymous
  • anonymous
....but it's essentially your code with tolerance set at the most precise digit of the float... (or double, in the case of the java code). I'm fairly certain that newton's method almost always reaches equilibrium.
whpalmer4
  • whpalmer4
Newton's method isn't the issue — it's numerical methods implemented to limited precision. If for some reason you get values that oscillate back and forth in the last digit or two and never give an exact equality, termination tests written like your proposed version don't ever return. I hope you understand that is unexpected and generally unacceptable behavior for a math library routine.
anonymous
  • anonymous
Yes, but my point is that with the algorithm I used, that oscillation shouldn't occur. I get what your saying though for algorithms in general. At the same time, I think your method has the potential to hang if the user of the method puts in a very low tolerance in an attempt to be more precise. If you end up getting a square that's 48.9999998, which we interpret as 49 (granted, I don't know if it would happen for this value, but I think you know about the discrepancy which I'm talking about concerning the conversion between binary and decimal values), but your user-set tolerance is set at 0.000001, your method will become stuck in an infinite loop. Correct me if I'm wrong, but I see slight room for error in both of our approaches.
anonymous
  • anonymous
Also, if all of the actual math library functions were programmed with tolerance values, like your method, wouldn't there be error bounds associated with each function?
anonymous
  • anonymous
@whpalmer4 What do you think about this compromise? I tried to incorporate the ideas of both of our solutions into one: def sqrt(x,tolerance): guess = 0.5 * x # Initial guess is 1/2 of x oldGuess = 0.0 # initializes oldGuess # While consistant guesses have yet to be reached # (to prevent against tolerance bounds which are too small) # AND outside the tolerance bound... while guess != oldGuess and -tolerance <= guess*guess-x and tolerance > guess*guess-x: # Iterate based on Newton's/the Babylonian Method: oldGuess = guess guess = (guess + x/guess)/2.0 # After it's finished, if within the tolerance bound, but not yet consistant guessing... iterator = 0 iteratorLimit = 10 # guess 10 more times to attempt to achieve consistant guessing without looping to infinity # if the most precise guess oscillates while iterator < iteratorLimit and guess != oldGuess: oldGuess=guess guess=(guess+x/guess)/2.0 # Return the most precise guess found return guess

Looking for something else?

Not the answer you are looking for? Search for more explanations.