We started this series of posts by using Newton's method to find square roots. Now we're going to use Newton's method to find the root of any function (section 1.3.4). Newton showed that for a function f and its derivative f', we can find a value x where f(x) = 0, by starting with a guess y, and using y - f(y) / f'(y) to get a better guess. As before, we calculate better guesses until the difference between guesses becomes very small. We can find the square root of a number a with this method by using the function f(x) = x**2 - a.
We already have some code that computes guesses repeatedly for square roots. Let's extract a function that does this for any guess calculation. (In math jargon, this is called finding the fixed point.) Here's the F# version:
module Newton =
let rec findFixedPoint improveGuess guess =
let newGuess = improveGuess guess
let goodEnough = abs((guess - newGuess) / guess) < 0.000001
if goodEnough then newGuess else findFixedPoint improveGuess newGuess
let squareRoot input =
let squareRootFromGuess = findFixedPoint (fun guess -> (guess + input / guess) / 2.0)
match input with
| 0.0 -> 0.0
| input when input < 0.0 -> raise (new System.ArgumentOutOfRangeException())
| input -> squareRootFromGuess 1.0
Notice how we define a function
squareRootFromGuess by calling findFixedPoint with the guess calculation function we want to use. This is called partial application, because findFixedPoint takes two arguments and we're only providing the first. The second argument is supplied when we call squareRootFromGuess.
Now we can use this function with Newton's general guess calculation. This time, let's write NUnit tests in F#, that we can use for both F# and C# versions of production code. F# has all the object-oriented features we need to define abstract classes and methods, inheritance and method overrides. We can even use method names with embedded spaces to get a nice readable test results report from NUnit. Here's a couple of tests and a test fixture class:
open NUnit.Framework
open Exploring.Net.FSharp.Newton
[<AbstractClass>]
type NewtonTest() =
abstract member FindSquareRoot: float -> float
[<Test>]
member this.``initial guess is correct``() =
Assert.AreEqual(1.0, this.FindSquareRoot(1.0))
[<Test>]
member this.``result gets close enough``() =
Assert.AreEqual(2.0, this.FindSquareRoot(4.0), 1E-10);
[<TestFixture>]
type NewtonTestFSharp() =
inherit NewtonTest()
override this.FindSquareRoot input = squareRoot2 input
Here's some F# code to pass the tests. We define a derivative function as (f(x+dx) - f(x)) / dx, where dx is a small amount. We define Newton's function to transform a guess into a better guess. We've defined a constant for our small amount, and added checks for floating point overflow.
open System
module Newton =
let smallAmount = 1E-6
let rec findFixedPoint improveGuess guess =
let newGuess = improveGuess guess
if Double.IsNaN newGuess || Double.IsInfinity newGuess
then newGuess
else
let goodEnough = abs((guess - newGuess) / guess) < smallAmount
if goodEnough then newGuess else findFixedPoint improveGuess newGuess
let squareRoot input = ...
let findRoot aFunction firstGuess =
let derivative = fun x -> (aFunction (x + smallAmount) - aFunction x) / smallAmount
let newtonsTransform = fun x -> x - (aFunction x) / (derivative x)
findFixedPoint newtonsTransform firstGuess
let squareRoot2 input = findRoot (fun x -> x*x - input) 1.0
Now the same in C#. We add a test fixture class to our F# tests.
[<TestFixture>]
type NewtonTestCSharp() =
inherit NewtonTest()
override this.FindSquareRoot input = Newton.SquareRoot2 input
Now refactor the C# square root calculation to extract the
FindFixedPoint function and use it to implement the general Newton's method calculation.public static class Newton {
public static double SquareRoot(this double input) {
if (input < 0.0) throw new ArgumentOutOfRangeException();
if (input == 0.0) return input;
return FindFixedPoint(guess => (guess + input / guess) / 2.0, 1.0);
}
public static double SquareRoot2(double input) {
return FindRoot(x => x * x - input, 1.0);
}
public static double FindRoot(Func function, double guess) {
Func newtonsTransform = x => x - function(x) / Derivative(function)(x);
return FindFixedPoint(newtonsTransform, guess);
}
static Func Derivative(Func function) {
return x => (function(x + smallAmount) - function(x)) / smallAmount;
}
static double FindFixedPoint(Func improveGuess, double initialGuess) {
var guess = initialGuess;
while (true) {
var newGuess = improveGuess(guess);
if (double.IsNaN(newGuess) || double.IsInfinity(newGuess)) return newGuess;
if (CloseEnough(guess, newGuess)) return newGuess;
guess = newGuess;
}
}
static bool CloseEnough(double guess, double newGuess) {
return Math.Abs((guess - newGuess) / guess) < smallAmount;
}
const double smallAmount = 0.000001;
}
We've seen how F# lets us pass functions as parameters, assign functions to identifiers, create new functions from existing functions, in fact, do practically anything with functions that we're used to doing with simple data types. But we're also able to do much of the same things in C#. And we've seen a few of the object-oriented features of F# that are comparable to C#. So with two hybrid languages with a combination of object-oriented and functional features, how would we determine which is more suited to a particular problem? I'm not ready to answer that yet, but I'll close with some interesting comments I came across: The myths about the risks of introducing F# in your development team.
