|Perl: the Markov chain saw|
computing square root by hand -- no sqrt (golf, beginner)by boo_radley (Parson)
|on May 09, 2002 at 18:05 UTC||Need Help??|
I ran across this Dr. Math faq and thought it would make a nifty intro to perl golf( in that the algorithm is pretty simple).
your script should take 2 inputs on the command line, the first being the number we're looking for the root of, and a first 'best guess' Again, don't use sqrt in your code. Stop guessing when you have a reasonable idea of what the answer is, and print it out.
Your code isn't responsible for error checking or verifying that the output's correct (verify it with a calculator if you like).
here's an outline of the algorithm described in the first section of the above url:
First, start by guessing a square root value. It helps if
your guess is a good one but it will work even if it is a
terrible guess. We will guess that 2 is the square root of 12.
In step two, we divide 12 by our guess of 2 and we get 6.
In step three, we average 6 and 2: (6+2)/2 = 4
Now we repeat step two with the new guess of 4. So 12/4 = 3
Now average 4 and 3: (4+3)/2 = 3.5
Repeat step two: 12/3.5 = 3.43
Average: (3.5 + 3.43)/2 = 3.465
some sample input/output :
All of these have have a precision of 3 digits.
my answer, at 66 characters, below :