Thursday, 20 September 2007

Implementing the FFT

The F#.NET Journal just published an article describing how a simple but efficient FFT algorithm may be implemented in F#:

"Writing an implementation of the Fourier transform is an excellent lesson in algorithm design and optimization. Moreover, the Fourier transform is one of the most essential tools in numerical computing, with applications ranging from spectral analysis to the multiplication of large integers. This article describes the design and implementation of a simple but efficient FFT..."

To read this article and more, subscribe to The F#.NET Journal today!

Saturday, 15 September 2007

High performance numerics with F#

We stumbled upon an interesting result recently whilst toying with numerical benchmarks ported from OCaml. Typically, OCaml programs are very easy to port but run more slowly under F# because the performance characteristics of the languages are different. However, we recently observed that some benchmarks optimized for OCaml actually run substantially faster in F# without having to make even a single change.

Specifically, the OCaml implementations of the numerically-intensive spectral-norm and n-body benchmarks from the Computer Language Shootout run more quickly in F#. We believe the reason is essentially that Microsoft's .NET compiler is much better at optimizing simple numerical algorithms, particularly loops over floating point arrays. Indeed, the results are all the more compelling because F# on vanilla 32-bit Windows XP Pro outperforms a longer, hand-optimized OCaml implementation running on OCaml's best-case platform for numerical programs, 64-bit Linux. In particular, bounds checking incurs a significant overhead in the spectral-norm benchmark and, we believe, the bounds checks are automatically hoisted from the inner loop in F# but this must be done manually in OCaml.


OCamlF#
Spectral-Norm14.3539.374
N-Body9.4696.933

This clearly shows that F# can achieve excellent performance on common machines for an important class of numerical algorithms.

For detailed articles covering all aspects of the F# programming language from Microsoft, subscribe to The F#.NET Journal today!

Thursday, 13 September 2007

Combinator Heaven

The F#.NET Journal published an article discussing the unique way that functions may be composed in functional languages using combinators:

"The ability to write higher-order functions that compose other functions in interesting ways is one of the most powerful forms of abstraction provided by the functional programming paradigm. Such functions are known as combinators . This article describes the basic concepts behind combinators with a variety of examples to demonstrate how practically useful this form of functional abstraction can be..."

To read this article and more, subscribe to The F#.NET Journal today!