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

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

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
        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) ||

            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 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