  We consider finite approximations of a fractal generated by an iterated
function system of affine transformations on $\mathbb{R}^d$ as a discrete set
of data points. Considering a signal supported on this finite approximation, we
propose a Fast (Fractal) Fourier Transform by choosing appropriately a second
iterated function system to generate a set of frequencies for a collection of
exponential functions supported on this finite approximation. Since both the
data points of the fractal approximation and the frequencies of the exponential
functions are generated by iterated function systems, the matrix representing
the Discrete Fourier Transform (DFT) satisfies certain recursion relations,
which we describe in terms of Di\c{t}\v{a}'s construction for large Hadamard
matrices. These recursion relations allow for the DFT matrix calculation to be
reduced in complexity to O(N log N ), as in the case of the classical FFT.
