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

 Root Route (Posted on 2004-06-29)
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

 Search: Search body:
Forums (0)