Method and apparatus for reduced memory footprint fast fourier transforms

A method comprising:

• generating an intermediate factors vector comprising a number of intermediate factors in response to a request to FFT circuitry to generate a fast Fourier transform (FFT) of an N-point input data set, N composite, wherein N is equal to a product of a number of nonunity integer factors, the number of intermediate factors is related to the nonunity integer factors of N and the number of intermediate factors is less than N;
• storing the intermediate factors vector in contiguous memory locations in memory circuitry;
• and
• reconstructing a subset of twiddle factors based at least in part on an element by element product of a first subset of the intermediate factors vector and a complex conjugate of a second subset of the intermediate factors vector, each of the first subset and the second subset loaded from the contiguous memory locations in the memory circuitry, wherein the twiddle factors are complex roots of unity configured to be used in generating the FFT.

A system comprising one or more storage mediums having stored thereon, individually or in combination, instructions that when executed by one or more processors result in the following operations comprising:

• generating an intermediate factors vector comprising a number of intermediate factors in response to a request to FFT circuitry to generate a fast Fourier transform (FFT) of an N-point input data set, N composite, wherein N is equal to a product of a number of nonunity integer factors, the number of intermediate factors is related to the nonunity integer factors of N and the number of intermediate factors is less than N;
• storing the intermediate factors vector in contiguous memory locations in memory circuitry;
• and
• reconstructing a subset of twiddle factors based at least in part on an element by element product of a first subset of the intermediate factors vector and a complex conjugate of a second subset of the intermediate factors vector, each of the first subset and the second subset loaded from the contiguous memory locations in the memory circuitry, wherein the twiddle factors are complex roots of unity configured to be used in generating the FIT.