# Muller's Recurrence - roundoff gone wrong

A while back I came upon a seemingly not-too-difficult programming exercise:

Define a recurrence $x_n$ by

$f(y, z) = 108 - \frac{815 - 1500/z}{y}$
$x_0 = 4$
$x_1 = 4.25$
$x_i = f(x_{i-1}, x_{i-2})$

Compute $x_{30}$.

This isn't too hard to code up, using perhaps a recursive function to represent $x_i$. With normal double-precision floats, as $i$ increases, the result converges neatly toward 100. Super!

Unfortunately, 100 is not even close to the right answer. This recurrence actually converges to 5. Continue reading

# A simple benchmark of various math operations

How computationally expensive are various fundamental floating point mathematical operations?  Here's a quick and dirty benchmark, which, although surely quite naive, seems to capture the rough relative cost of a few operations.

# Response to "Little Performance Explorations: F#"

I recently saw a tweet from Ryan Riley linking to an article exploring F# performance and floating point processing:

I poked around the code and tested it a bit myself, and figured I would take up the author's  call for feedback. Comments on the original blog are locked down, so I've written up my results here, instead. Continue reading

# An elliptical pool

@StevenStrogatz posed a fun question this evening:

People quickly realized the answer is "no," but how to show it? Continue reading

# F# extension methods in Roslyn

If you scan the source code for the Roslyn project, the platform on which the next-gen C# and VB compilers are based, you might stumble across an interesting special behavior that was added in for the sole purpose of preserving backward-compatibility with F#.

From [roslyn]\Src\Compilers\CSharp\Source\Symbols\Metadata\PE\PEAssemblySymbol.cs (as of commit dc3171c8a878):

public override bool MightContainExtensionMethods
{
get
{
if (!this.lazyContainsExtensionMethods.HasValue())
{
var moduleSymbol = this.PrimaryModule;
var module = moduleSymbol.Module;
// The F# compiler may not emit an assembly-level ExtensionAttribute, and previous versions of C# never checked for it.
// In order to avoid a breaking change (while preserving the perceived performance benefits of not looking for extension
// methods in assemblies that don't contain them), we'll also look for FSharpInterfaceDataVersionAttribute.
var mightContainExtensionMethods = module.HasExtensionAttribute(this.assembly.Handle, ignoreCase: false) ||
module.HasFSharpInterfaceDataVersionAttribute(this.assembly.Handle);

this.lazyContainsExtensionMethods = mightContainExtensionMethods.ToThreeState();
}

return this.lazyContainsExtensionMethods.Value();
}
}


The comment does a nice job of summing up the issue, but allow me to provide some additional context. Continue reading

# Project Euler visualizations - problem 144

Here's another nifty Project Euler visualization, one I put together while solving problem 144 a while ago. Continue reading

# Project Euler visualizations - problem 431

I recently solved Project Euler problem 431, which (through a bizarre and unnecessarily confusing back-story) requires one to calculate the volume trapped above a cone, inside a cylinder.  The point of the cone is taken to be level with the top of the cylinder, but the cone angle and its horizontal offset compared to the cylinder are variable.

I solved this one with Mathematica, and along the way I cobbled together a little visualization that allows one to easily see the curve of intersection where the cone and the cylinder join together.  Why not take this opportunity to share the visualization via an embedded CDF?  I've been wanting to try this for a while. Continue reading

# Selecting a random element from a linked list - 3 approaches in F#

You have a linked list (i.e. no random access) with an unknown number of elements and a standard random number generator. Write an algorithm that selects a random element from the list, going for best O(N) performance and memory usage. Continue reading

# A Twitter search client in 10 lines of code with F# and the JSON type provider

Twitter's basic search API is pretty simple to use, and returns JSON back to you with tweets matching your search parameters.

JSON, eh?  "There's an app a type provider for that." I wonder if I could cook something up... Continue reading

# Tracking a new year's resolution with F# and FSharpChart

This year, I have a goal of running 500 miles.  That's not a crazy-ambitious goal, but between work, school, hobbies, friends, and (occasional) downtime, I think it's plenty for me.  In contrast, the CEO of RunKeeper is planning to run 1,500 miles this year!  That's an admirable goal, and I hope he succeeds (though I would prefer that he focus on releasing a Windows Phone app, instead.  Ah well...).

In order to stay motivated (and because it's cool) I have decided to track my runs and chart my progress throughout the year.  Excel works just fine for this, but I want to try something a little different.  Why not use this as an opportunity to use FSharpChart? Continue reading