Square root by Newton's method

This well known method to calculate square roots by successive approximations is one of the first examples that Martin Odersky uses in its Scala by example booklet freely available online. You'll find it in section 4 of chapter 4.

The idea of this method is that we guess what could be the result, and then iteratively improve our guess, until we reach a good enough approximation.

It doesn't matter much which is our initial guess, we could simply default it to one, more interesting is deciding when we should stop to iterate. In some way it should be dependent on the input value itself. Here we are going to consider ourself happy when the difference between our guess squared and the input, divided by the input itself is less than one thousandth:

def isGoodEnough(guess: Double, x: Double) = math.abs(guess * guess - x) / x < 0.001

So, we are going to accept 8.003 as approximation for the 64 square root, but we'll reject 8.004. To improve our guess we'll apply this algorithm:

def improve(guess: Double, x: Double) = (guess + x / guess ) / 2

Now we are ready to write the requested function:

def sqrtIter(guess: Double, x: Double): Double =
  if (isGoodEnough(guess, x)) guess
  else sqrtIter(improve(guess, x), x)

If the guess is good enough, we are done. Otherwise iterate again with an improved guess. Likely we don't want the user having the nuisance of providing an initial guess:

def sqrt(x: Double) = sqrtIter(1.0, x)

We can compare the result to call to the Scala library function:

println(sqrt(2) - math.sqrt(2))
println(sqrt(4) - math.sqrt(4))
println(sqrt(1e-6) - math.sqrt(1e-6))
println(sqrt(1e60) - math.sqrt(1e60))

We can, and usually want to, hide the implementation details, making them local to our function. A side effect is that we don't need anymore to pass around the x value, being that visible to all the local functions, too.

def sqrt(x: Double) = {
  def isGoodEnough(guess: Double) = math.abs(guess * guess - x) / x < 0.001
  def improve(guess: Double) = (guess + x / guess ) / 2
  def sqrtIter(guess: Double): Double =
    if (isGoodEnough(guess)) guess
    else sqrtIter(improve(guess))
  
  sqrtIter(1.0, x)
}