Square root by Newton’s method

Medium TimeO(log n) SpaceO(1)

Given a number n, approximate its square root without calling Math.sqrt. The answer is an approximation rather than the root itself: it is accepted as soon as its square is within 0.0001 of n, so even a perfect square comes back a little off. n is never negative, and the square root of 0 is 0.

Examples

Example 1

Input
n = 2
Output
1.4142156862745097
Its square is 2.0000060…, inside the 0.0001 allowed.

Example 2

Input
n = 16
Output
4.000000636692939
Not 4: its square is 16.0000051…, which is already close enough.

The Code

function newtonSqrt(n) {
  if (n === 0) return 0;
  let guess = n;
  let steps = 0;
  while (Math.abs(guess * guess - n) > 0.0001 && steps < 50) {
    guess = (guess + n / guess) / 2;
    steps++;
  }
  return guess;
}
newtonSqrt(2);
Done
Step through newtonSqrt(2) call by call

More like this

All math & numbers examples (8) →