Created
May 31, 2016 03:40
-
-
Save anujku/a09bcbd276fbd133f26fa14e0d4f1653 to your computer and use it in GitHub Desktop.
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
| // sqrt(x) = y = x / y | |
| // sqrt(x) -> fixed point of function (y => x/y) | |
| // with damping => sqrt(x) = ( y = (((y + x) / y) / 2) (1.0) | |
| // def sqrt(x : Double) = fixedPoint(y => ((y + x) / 2)) (1.0) | |
| import math.abs | |
| val tolerance = 0.0001 | |
| def isCloseEnough(a: Double, b: Double): Boolean = { | |
| abs((a - b) / a) / a < tolerance | |
| } | |
| def fixedPoint(func: Double => Double)(firstGuess: Double) = { | |
| def iterate(guess: Double): Double = { | |
| val next = func(guess) | |
| if (isCloseEnough(guess, next)) next | |
| else iterate(next) | |
| } | |
| iterate(firstGuess) | |
| } | |
| fixedPoint(x => 1 + x / 2)(1) | |
| def avgDump(func: Double => Double)(x: Double): Double = { | |
| (x + func(x)) / 2 | |
| } | |
| def sqrt(x: Double) = fixedPoint(avgDump(y => x / y))(1.0) | |
| sqrt(2) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment