# When I ask Matlab for a zero-padded FFT, does it (or FFTW) ever explicitly create a zero-padded input vector?

If I have a length $N$ signal and ask Matlab for an $M$-point FFT, $M \gg N$, of course the computer has to allocate memory for $M$ output samples, but my question is if it ever has to allocate memory for $M$ input and fill it with the input vector along with zeros? Or are FFT algorithms capable of generating the $M$-point result without having to explicitly store the $M$-length padded input?

(Motivation I have a library that can automatically give me zero-padded data (or unpadded data), which I then perform FFTs on. Assume everything before the result of this library call has already happened, and we only care about what we do once those results (padded or unpadded) are available. If Matlab or FFTW don't need to explicitly allocate $M$-long zero-padded inputs to the FFT, then I'd be wasting memory by asking the library to zero-pad for me, and should just ask it for unpadded data.)

There is an FFT trick to perform a $2N$-point FFT on $2N$ real-only input samples using a single complex $N$-point FFT operation. But I've never heard of performing an $M$-point FFT on $N$ input samples without zero padding the input sequence out to length $M$. Ahmed, if you can develop a way to do that you would become famous and someone would write a song about you.
• I am honored to have my silly question answered by Rick Lyons! No, I grok that an $M$-point FFT on $N$ input samples implicitly requires zero-padding the input to $M$-length. But I guess I'm asking if implementations explicitly construct this $M$-long padded input, or if they could construct the $M$ output samples without first allocating space for $M$ input samples, writing zeros to it, and copying the original $N$ samples to the first $N$ slots in the array. – Ahmed Fasih Dec 19 '15 at 16:04
• Thanks! From this line of reasoning, assuming the input was copied to a newly-allocated $M$-long block of memory which becomes the output after the FFT, the answer would be, no, an implementation doesn't need to allocate an intermediate $M$-long array: the only array it allocates becomes the output! – Ahmed Fasih Dec 21 '15 at 2:33