This is how the DFT may be computed efficiently.

**1D Case**

has to be evaluated for *N* values of *u*, which if done in the
obvious way clearly takes multiplications.

It is possible to calculate the DFT more efficiently than this, using the **fast
Fourier transform** or FFT algorithm, which reduces the number of operations to
.

We shall assume for simplicity that *N* is a power of 2, .

If we define to be the root of unity given
by , and set *M*=*N*/2, we have

This can be split apart into two separate sums of alternate terms
from the original sum,

Now, since the square of a root of unity is an
root of unity, we have that

and hence

If we call the two sums demarcated above and
respectively, then we have

Note that each of and for is in itself a
discrete Fourier transform over *N*/2=*M* points.

How does this help us?

Thus, we can compute an *N*-point DFT by dividing it into two parts:

- The first half of
*F*(*u*) for can be found from Eqn. 28, - The second half for can be found simply be reusing the same terms differently as shown by Eqn. 30.
- This is obviously a divide and conquer method.

To show how many operations this requires, let *T*(*n*) be the time taken to perform a
transform of size , measured by the number of multiplications performed. The
above analysis shows that

the first term on the right hand side coming from the two transforms
of half the original size, and the second term coming from the multiplications of
by . Induction can be used to prove that

A similar argument can also be applied to the number of additions required, to show that the algorithm as a whole takes time .

Also Note that the same algorithm can be used with a little
modification to perform the inverse DFT too. Going back to the definitions of the
DFT and its inverse,

and

If we take the complex conjugate of the second equation, we have that

This now looks (apart from a factor of 1/*N*) like a forward DFT,
rather than an inverse DFT.

Thus to compute an inverse DFT,

- take the conjugate of the Fourier space data,
- put conjugate through a forward DFT algorithm,
- take the
conjugate of the result, at the same time multiplying each value by
*N*.

**2D Case**

The same fast Fourier transform algorithm can be used -- applying the separability property of the 2D transform.

Rewrite the 2D DFT
as

The right hand sum is basically just a one-dimensional DFT if *x* is
held constant. The left hand sum is then another one-dimensional DFT performed with
the numbers that come out of the first set of sums.

So we can compute a two-dimensional DFT by

- performing a one-dimensional DFT for each value of
*x*,*i.e.*for each column of*f*(*x*,*y*), then - performing a one-dimensional DFT in the opposite direction (for each row) on the resulting values.

This requires a total of 2 *N* one dimensional transforms, so the overall process
takes time .