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 = 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/


.

No comments: