Sunday, 11 January 2009

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 = startItemfor(final T a : listOfT) { b = method(b, a);}return b;`

Example code:

`package testobject 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.0guess for x 9.0 improved to = 3.4guess for x 9.0 improved to = 3.023529411764706guess for x 9.0 improved to = 3.00009155413138guess for x 9.0 improved to = 3.000000001396984guess for x 64.0 improved to = 32.5guess for x 64.0 improved to = 17.234615384615385guess for x 64.0 improved to = 10.474036101145005guess for x 64.0 improved to = 8.292191785986859guess for x 64.0 improved to = 8.005147977880979guess for x 64.0 improved to = 8.000001655289593guess for x 64.0 improved to = 8.00000000000017guess for x 842.0 improved to = 421.5guess for x 842.0 improved to = 211.7488137603796guess for x 842.0 improved to = 107.86261164282149guess for x 842.0 improved to = 57.83441917633403guess for x 842.0 improved to = 36.19661181949908guess for x 842.0 improved to = 29.729228773452704guess for x 842.0 improved to = 29.025762097895374guess for x 842.0 improved to = 29.017237509256656guess for x 842.0 improved to = 29.017236257093842square 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 notreally a very good test. (See exercise 1.7.) The idea is to improve the answer until it is close enough so thatits 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: