Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

dhemmy

how to find the square root of a number in java without using the squrt function

  • 10 months ago
  • 10 months ago

  • This Question is Closed
  1. blurbendy
    Best Response
    You've already chosen the best response.
    Medals 0

    you'd probably have to write your own method to do it

    • 10 months ago
  2. whpalmer4
    Best Response
    You've already chosen the best response.
    Medals 1

    The Babylonian method is one you could easily do. https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method

    • 10 months ago
  3. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    http://dpaste.com/1259775/

    • 10 months ago
  4. eSpeX
    Best Response
    You've already chosen the best response.
    Medals 0

    You could also try the Newtonian method. https://en.wikipedia.org/wiki/Newton%27s_method

    • 10 months ago
  5. whpalmer4
    Best Response
    You've already chosen the best response.
    Medals 1

    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

    • 10 months ago
  6. kkleidal
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • 10 months ago
  7. kkleidal
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • 10 months ago
  8. whpalmer4
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

    • 10 months ago
  9. kkleidal
    Best Response
    You've already chosen the best response.
    Medals 0

    ....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.

    • 10 months ago
  10. whpalmer4
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

    • 10 months ago
  11. kkleidal
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 10 months ago
  12. kkleidal
    Best Response
    You've already chosen the best response.
    Medals 0

    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?

    • 10 months ago
  13. kkleidal
    Best Response
    You've already chosen the best response.
    Medals 0

    @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

    • 10 months ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.