Tuesday, January 15, 2008

Deriving Miss Daisy

As I've mentioned previously, I'm slowly reading through SICP - it's an amazing book and reading it has been a humbling experience.

'Geeking' Out

I completely geeked out reading one example on functional derivatives.  (Take a math expression as a parameter and return the derivative as an expression)

It's in the first chapter, and they use this to implement Newton's Method -> to then implement a Sqrt function!

Approximate Derivative

After I picked my brain off the floor, I decided to have a crack at implementing derivatives in C# using lambda expressions:


Using the formula of a derivative (above), we can simply code an approximate derivative (below):

Func<double, double> Approximate(Func<double, double> f)
var h = 0.0001;
return a => ((f(a + h) - f(a)) / h);

Symbolic Derivation

Easy huh!  So for fun I decided to use linq expression trees to derive algebraically.

It's easy to get an expression tree in C# - simply use the Expression<> type.
Func<double, double> Derive(Expression<Func<double, double>> e)
var lambda = new Derivative().Eval(e) as LambdaExpression;
return (Func<double, double>) lambda.Compile();

I parse the expression tree using Matt Warren's ExpressionVisitor class - and using the basic rules of Derivation (Constant, Product and Quotient rules) we get:
class Derivative : ExpressionVisitor
public Expression Eval(Expression exp)
return this.Visit(Evaluator.PartialEval(exp));

protected override Expression VisitBinary(BinaryExpression b)
// Product Rule: (fg)' = f'g + fg'
if (b.NodeType == ExpressionType.Multiply)
return Expression.Add(
Expression.Multiply(Eval(b.Left), b.Right),
Expression.Multiply(b.Left, Eval(b.Right)));

// Quotient Rule: (f/g)' = (f'g - fg') / (g*g)
if (b.NodeType == ExpressionType.Divide)
return Expression.Divide(
Expression.Multiply(Eval(b.Left), b.Right),
Expression.Multiply(b.Left, Eval(b.Right))),
Expression.Multiply(b.Right, b.Right));

return base.VisitBinary(b);

// Parameter Derivation: f(x)' = 1
protected override Expression VisitParameter(ParameterExpression p)
return Expression.Constant(1.0);

// Constant Rule f(a)' = 0
protected override Expression VisitConstant(ConstantExpression c)
return Expression.Constant(0.0);

Wrapping it up

To quickly finish this long blog post, here's the usage code:
// f(x * x * x)' = 3 * x * x
var approx = Approximate(x => x * x * x);
var derive = Derive(x => x * x * x);

var y1 = approx(1); // 3.0000300001109532
var y2 = derive(1); // 3.0

And there it is!  Useful? maybe not.  Fun? Definitely!

Monday, January 7, 2008

The 'Y' in Blog

It's quite demoralizing when you consider how much you don't know. I am continually reminded that I underestimate it's sheer quantity... it's a sad realization.

Since there is so much already written by people more knowledgeable and intelligent than myself, why do I write?

Well, I started this blog to show my appreciation, and hopefully to contribute something back to the development community.

So kudos to all of you... keep sharing the love (of maths & programming)!

Associate with people who are searching for answers, avoid those who have found them.

Happy New Year!