Copyright by Jon Harrop

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

O'Reilly logo

Chapter 12. COMPLETE EXAMPLES

This chapter details several complete programs that demonstrate some of the most importants forms of scientific computing whilst also leveraging the elegance of the F# language and the power of the .NET platform.

FAST FOURIER TRANSFORM

The program developed in this section combines a core concept in scientific comput-ing with a core concept in computer science:

  • Spectral analysis: computing the Fourier transform.

  • Divide and conquer algorithms.

The Fourier transform is one of the most essential tools in scientific computing, with applications in all major branches of science and engineering as well as computer science and even mathematics. This section describes the development of an efficient implementation of the Fourier transform known as the Fast Fourier Transform (FFT).

Discrete Fourier transform

In its simplest form, the Fourier transform

Discrete Fourier transform
Discrete Fourier transform

This direct summation algorithm is referred to as the Discrete Fourier Transform (DFT) and is composed of 0(N2) operations, i.e. this algorithm has quadratic asymptotic time complexity.

This naive algorithm may be implemented as a simple F# function:

> #light;; > open System;; > open Math;; > let dft ts = let N = Array.length ts [|for k in 0 .. Array.length ts - 1 -> let mutable z = Complex.zero for n=0 to N-l do let w = 2.0 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required