Well, FFT ... and Excel, hm ... Excel has one build in, but it is a mess:
it is given through strings and slow and ugly.

I build some based on procedures from Maple 8 - even if this is almost
not documented it gives a cross reference for testing. They are not the
fastest, but reasonable and for serious applications with large datasets
anybody would choose a more appropriate environment. This here works up
to 2^14 data as input.

To step in: just view at FFT and inverse FFT as a black box technique to
compute certain sums which come from discretization Fourier transforms.
So consider them as discrete Fourier transforms DFT and inverse DFT:

Let z(k) = x(k) + y(k)*I be a sequence of complex numbers, I = sqrt(-1).

One wants to compute the following sums (for any k, 0 <= k <= N-1)

                N - 1
                -----
                 \                                -2 I Pi j k
    DFT(z(k)) =   )   (x[j + 1] + y[j + 1] I) exp(-----------)
                 /                                     N
                -----
                j = 0

and

                 N - 1
                 -----
                  \                                2 I Pi j k
  invDFT(z(k)) =   )   (x[j + 1] + y[j + 1] I) exp(----------)
                  /                                    N
                 -----
                 j = 0


For example z(k) = f(t(k)) for a complex valued function in several points
t(k) and one wants to evaluate the (inverse) Fourier integral.

If N becomes large there is a better way than just simply summing up: split
the sum in 2 equal halves and doing that recursively one can save lots of
time. For this N has to be a power of 2 (if not: just fill up the z's with
zeros) and fast Fourier is 'just to do it this way'.

Thus view FFT as a special technique of fast summation.

Another advantage of this technique: summing gives it for just one k. While
FFT (or its inverse) do it for all k at once. Which is a great computational
saving. And explains why inputs and outputs are vectors/arrays/lists ...

For notational convenience the resultings for all k are considered as a
sequence Z(k) - so it is a discretization for the Fourier transform F.

There is no general rule for FFT and its inverse, several conventions are
around.

The one used here is 

       FFT = DFT, invFFT = 1/N * iDFT

Thus they are pure summations, the inverse being devided by N. Nothing more
needed to apply it but this. Then both are inverse to each other, i.e 

       FFT( invFFT( Z(k) ) ) = Z(k), invFFT( FFT( z(k) ) ) = z(k)

The Excel workbook contains functions to compute that FFT and invFFT in VBA. 

Inputs are columns for the real and imaginary parts of z(k) = x(k) + y(k)*I
and returns are colums/arrays of Z(k) = X(k) + Y(k)*I. Provide m with N = 2^m
as well to give the length N, see examples.

As the inputs are not checked in the code please make sure that the length
of the columns and m fit together. Or modify the code to ensure it (kicking
out m as input).

Staring at the summations and at the code it would become clear that both
transforms differ only by a sign switch, but I have not implemented that.

The examples are entered as array formulae (pressinging <controll>+<shift> at
enter), so they have to be handled as such (consult Excel's help).

To cross-check results for any k use the 'dumb addition' included (which are
slow if being used for any k in question). Due to starting sums at 0 a shift
by -1 is needed to get the correct position for the index k, cf the code.
That functions are named FFT_check and invFFT_check.

Note that Excel seems to dislike matrices greater than 4096 outputs. So if
more than 2^11 inputs are needed, then either work only within VBA. Or code
some procedure calling the functions and write results to worksheets (Excel
does not allow writing to sheets in functions, one has to use a sub, cf *)).

Types for countings are 'integer' as for huge data it is not the right setting.

Note that beyond version 8 Maple uses a different approach which for N=1000000
handles problems below 1 sec even for that non-numerical environment.

------------------------------------------------------------------------------

*) it may look like this:

Sub post_FFT()
Dim i As Integer, m As Integer, N As Integer
Dim z
Dim remCalc

m = 13
N = 2 ^ m
z = FFT(m, _
    Worksheets("Tabelle1").Range("C1:C8192"), _
    Worksheets("Tabelle1").Range("D1:D8192"))

remCalc = Application.Calculation
Application.Calculation = xlManual
Application.ScreenUpdating = False

For i = 1 To N
  Worksheets("Tabelle1").Range("F1:F8192").Cells(i, 1).Value = z(i, 1)
  Worksheets("Tabelle1").Range("G1:G8192").Cells(i, 1).Value = z(i, 2)
Next i

Application.Calculation = remCalc
Application.ScreenUpdating = True

End Sub