I need fft?

Notice that these expressions are arranged so that we need to combine the various DFT outputs by pairs of additions and subtractions, which are known as butterflies. In order to obtain the minimal operation count for this algorithm, one needs to take into account special cases for k = 0 (where the twiddle factors are unity) and for k = N / 8 (where the twiddle factors are and can be multiplied more quickly). Multiplications by and are ordinarily counted as free (all negations can be absorbed by converting additions into subtractions or vice versa).