Created
November 1, 2011 09:55
-
-
Save miguel-negrao/1330241 to your computer and use it in GitHub Desktop.
Newton-Raphson Square Roots
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* | |
* Newton-Raphson Square Roots | |
* as is shown in "why functional programming matters" | |
* http://www.cs.utexas.edu/~shmat/courses/cs345/whyfp.pdf | |
*/ | |
object NewtonRoots { | |
//algorithm to approach the square root of n | |
def next(n:Double)(x:Double) = (x + n/x)/2 | |
//create a stream composed of repeatedly applying f | |
def repeat(f:Double=>Double, a:Double):Stream[Double] = a #:: repeat(f,f(a)) | |
//look for a good enough match in the stream | |
def within(eps:Double, s:Stream[Double]):Double = s match { | |
case a #:: b #:: rest => if( (a-b).abs < eps) b else within(eps, b#::rest) | |
} | |
//look for a good enough match in the stream. | |
// A better way is to see how close a/b is to 1, | |
// to avoid the rounding errors | |
def relative(eps:Double, s:Stream[Double]):Double = s match { | |
case a #:: b #:: rest => if( (a/b -1).abs < eps) b else within(eps, b#::rest) | |
} | |
//find the square root of 3 starting from the approximation | |
// value 1, until approximations are within 0.01 | |
def main(args: Array[String]) { | |
println( within(0.01, repeat( next(3), 1 ) ) ) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment