Scala, Square roots, Netwon's method, closures and foldLeft

A simple Scala example. This one computes square roots by successive approximation using Newton's method, defined in a class SquareRoot. A companion object is also used to define the precision constant, the target tolerance we'll use to decide when to stop approximating.

There are two version of the function. squareRootSimple is a simple implementation. The method squareRoot improves on this by refactoring the code to use a closure to capture x, the value for which we are finding the square root. Also, the overloaded average function takes a List and uses list.foldLeft(0.0).(_ + _) which means apply x+y to list element pairs, starting with 0.0, running through all the elements in the list, thus summing all the elements.

Example of the use of foldLeft:

list.foldLeft(0.0).(_ + _)

Which could also be written as:

(start /: list)(_ + _)

• /: is the foldLeft operator, equivalent to the .foldLeft method on a list
• \: is the foldRight operator, equivalent to the .foldRight method on a list

The fold operator is like a pattern that crops up fairly often in imperative programming, it looks something like this:

B b = startItem

for(final T a : listOfT) {
 b = method(b, a);
}

return b;

Example code:

package test

object SquareRootsTest {

    def main(args : Array[String]) {

        val squareRoot = new SquareRoot()

        assert(((squareRoot.squareRoot(9) - 3) abs) < SquareRoot.precision)
        assert(((squareRoot.squareRoot(64) - 8) abs) < SquareRoot.precision)

        val res1 = squareRoot.squareRoot(842)
        println("square root of 842 = " + res1 + ", " + res1 + " squared = " + res1 * res1)
    }
}


object SquareRoot {

    val precision = 0.000001
}

class SquareRoot {

    def squareRootSimple(x : Double) : Double = (

        squareRootIter(1.0, x)
    )

    def squareRootIter(guess : Double, x : Double) : Double = {

        if (goodEnough(guess, x)) {
          guess
        }
        else {
          squareRootIter(improveGuess(guess, x), x)
        }
    }

    private def improveGuess(guess : Double, x : Double) : Double = {

        val newguess = average(guess, x / guess)
        println("guess for x " + x + " improved to = " + newguess)
        newguess
    }

    private def goodEnough(guess : Double, x : Double) = {

        (square(guess) - x).abs  < SquareRoot.precision
    }

    def squareRoot(x : Double) : Double = {

        def squareRootIter(guess : Double, x : Double) : Double = {

            if (goodEnough(guess)) {
              guess
            }
            else {
              squareRootIter(improveGuess(guess), x)
            }
        }

        def improveGuess(guess : Double) : Double = {

            val newguess = average(List(guess, x / guess))
            println("guess for x " + x + " improved to = " + newguess)
            newguess
        }

        def goodEnough(guess : Double) = {

            (square(guess) - x).abs  < SquareRoot.precision
        }

        squareRootIter(1.0, x)
    }

    private def average(x : Double, y : Double) : Double = {

        (x + y) / 2
    }

    private def average(list : List[Double]) : Double = {

        //println("value = " + list.mkString)
        //(0.0 /: list)(_ + _) / list.size
        list.foldLeft(0.0)(_ + _) / list.size
    }

    private def square(value : Double) : Double = {

        value * value
    }
}

Results:

guess for x 9.0 improved to = 5.0
guess for x 9.0 improved to = 3.4
guess for x 9.0 improved to = 3.023529411764706
guess for x 9.0 improved to = 3.00009155413138
guess for x 9.0 improved to = 3.000000001396984
guess for x 64.0 improved to = 32.5
guess for x 64.0 improved to = 17.234615384615385
guess for x 64.0 improved to = 10.474036101145005
guess for x 64.0 improved to = 8.292191785986859
guess for x 64.0 improved to = 8.005147977880979
guess for x 64.0 improved to = 8.000001655289593
guess for x 64.0 improved to = 8.00000000000017
guess for x 842.0 improved to = 421.5
guess for x 842.0 improved to = 211.7488137603796
guess for x 842.0 improved to = 107.86261164282149
guess for x 842.0 improved to = 57.83441917633403
guess for x 842.0 improved to = 36.19661181949908
guess for x 842.0 improved to = 29.729228773452704
guess for x 842.0 improved to = 29.025762097895374
guess for x 842.0 improved to = 29.017237509256656
guess for x 842.0 improved to = 29.017236257093842
square root of 842 = 29.017236257093842, 29.017236257093842 squared = 842.0000000000015

Source Scheme Code:

(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
A guess is improved by averaging it with the quotient of the radicand and the old guess:
(define (improve guess x)
(average guess (/ x guess)))
where
(define (average x y)
(/ (+ x y) 2))
We also have to say what we mean by ``good enough.'' The following will do for illustration, but it is not
really a very good test. (See exercise 1.7.) The idea is to improve the answer until it is close enough so that
its square differs from the radicand by less than a predetermined tolerance (here 0.001):22
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001)) 

References:

Blog about fold Left: http://blog.tmorris.net/scalalistfoldleft-for-java-programmers/


.