A functional program for the Fast Fourier Transform

Abstract

This paper is written as a contribution to the Parallel Reduction Machine Project. Its purpose is to present a functional program for a well-known application of the fundamental algorithmic method Fast Fourier Transform for multiplication of polynomials. This in order to verify experimentally two claims by functional programmers [BvL]: (i) functional programming is good for writing structured software; better so than the so-called imperative von Neumann-languages. (ii) functional programming allows for a parallel evaluation of subexpressions, provided a proper implementation.