Fast fourier transform operation with reduced cache penalty

The method of performing an N-point radix-R Fast Fourier Transform in a data processing apparatus having a data cache comprising the steps of:

• comparing the data set of input data and twiddle factors with the size of the data cache;
• if said data set is smaller than said data cache, performing said Fast Fourier Transform in logRN stages on all the data set in one pass;
• and
• if said data set is larger than said data cache but smaller than R times the data cache
• dividing said input data into R continuous data sets where each of said R continuous data sets fit within the data cache;
• disposing said input data into memory, each R continuous data set in continuous memory locations with a space in memory locations from an end of one continuous data set to a beginning of a next continuous data set equal to the size of a cache line;
• separately and independently performing a first stage radix-R butterfly computations on all the R continuous data sets thereby producing R independent intermediate data sets in a first pass each of which fits within the data cache;
• and
• successively performing second and all subsequent stage butterfly computations on each independent intermediate data set in turn producing corresponding output data in second passes.