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:

Post a Comment