All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Root Route (Posted on 2004-06-29) Difficulty: 3 of 5
Develop an efficient algorithm to find the square root of a positive real number.

No Solution Yet Submitted by Gamer    
Rating: 1.7500 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
old school | Comment 5 of 7 |
We learned to find square roots in school by a method similar to long division. Unlike long division, you take TWO digits at a time (because  10^2=100, so to find the next digit in the root you need two digits from the number). At each stage you multiply the last digit of the "multiplier" by 2 (to get the 2ab in  (a+b)^2 = a^2 + b^2 + 2ab), and only then add another digit.

Hmmm... an example, perhaps, square root of 200:

stage I: Start with the 2. A 1 digit root is the largest that is less than 2 when squared, that's 1, so multiplier = 1, and 1*1=1, so the root so far = 1. Remainder = 2-1 = 1.

stage 2: Take down two digits: remainder = 100. Double last digit of multiplier multiplier = 2. Now, find the next digit, that's  the largest digit x for which (20 + x)*x<100. It's 4, because 24*4<100, but 25*5>100. Add the 4 to the root. root so far = 14. multiplier = 24. Remainder = 100 - 4*24 = 4.

stage 3: another 2 digits: remainder = 400 (4.00 actually). Double last digit of multiplier, multiplier = 28. Now find the next digit: 281*1 < 400, but 282*2>400, so it's 1. root so far = 14.1. remainder = 400-281=119.

stage 4: remainder = 11900. multiplier = 282. next digit = 4. root so far = 14.14. multiplier = 2824. remainder = 11900 - 2824*4 = 604. etc.

So square root of 200 = 14.14...



  Posted by pleasance on 2004-06-30 09:34:12
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information