Coarse-grained reconfigurable architectures, like the Montium, have proven to be a successful approach for low-power and high-performance computation of regular DSP algorithms. The main research question posed in this paper is: Can such architectures also take over less regular algorithms from general purpose processors? This paper presents the implementation of non-power-of-two fast Fourier transforms (FFT) to discover the limitations and flexibility of the Montium. The results of the implementation show a order of magnitude reduction of the processing time and energy consumption compared to an ARM processor. Furthermore, we show the accuracy and flexibility of the implementation