Implementing Complex Numbers and FFT with Just Datatypes (No Floats)

This article presents a method for implementing complex numbers and Fast Fourier Transform (FFT) using only algebraic datatypes, without relying on floating-point numbers. The author begins by explaining the advantages of using algebraic datatypes for numerical representation and highlights inefficiencies in traditional FFT implementations. A concise and elegant implementation of integers and complex numbers using only algebraic datatypes is then demonstrated. Finally, a purely functional implementation of complex FFT, also without floats, is derived. This is achieved by using balanced ternary representation for integers and extending Gaussian integers to represent complex numbers, cleverly circumventing the fusion-hindering effects of floating-point arithmetic, thereby improving algorithm efficiency.