What is the efficient way to perform FFT for large set of Samples?

I'm trying to perform FFT for large set of samples,

Sampling Rate : 1 MHZ

No. of Samples Captured : 1 Million (1 sec duration)

currently what I'm doing is, I've added zero padding so that it matches to 2^n, and now the total number of samples are 1048576 (2^20) and then I perform FFT. This approach seemed to take long.

I'm just wondering if there's any efficient way to do this? (Please note that at this stage, I'm not particular about the frequency resolution)

-
Break the sample data into smaller chunks and process them individually. Average the rsults together if you like, or just keep them separate so you can see how the spectrum varies with time. – Dave Tweed Feb 20 '14 at 14:36
Thanks Dave, I'll try that approach.! – SanVEE Feb 20 '14 at 14:43

The basic physics of the Cooley-Tukey radix-2 Fast Fourier Transform are well-known.

It does log2 N "layers" of butterfly operations. Each layer does N/2 butterflies. Each butterfly does 2 multiplications and 2 additions.

For a binary million (2^20) point sample, that's 20 million multiplications and 20 million additions.

You also need a million-point (maybe half a million, I'm not absolutel certain) twiddle factor table, which you precalculate.

On a DSP, to run in real-time, that's about 40 million operations/second, which is not at all unreasonable today. A modern x86 should have no problem with this, PROVIDED OF COURSE that you are doing compiled machine code and hardware arithemtic, and that your FFT code is properly optimized for your particular hardware.