# Is there a FFT algorithm which is both in-place and constant geometry?

I work in crypto where the NTT (Number Theoretical Transform) which is just a FFT in finite fields is used. I wanted to know if there exists an implementation of the FFT which is both in-place and constant geometry? I will explain the terms below.

An in-place algorithm will not need more space than the space used to store the array. In FFT algorithms, this means the two indices accessed in the innermost loop are also the two indices where the output is written.

A constant geometry algorithm will always use the same pair of indices, at all different stages of the algorithm. For an intuitive explanation, take a look at this.

As much as I have seen, there seems to not be an algorithm which is both. I would like to know if one exists. Or if there is a reason if it doesn't exist.

• Is this question basically asking if it is possible to have an FFT that doesn't shuffle the data (?).
– A_A
Apr 9, 2020 at 8:29
• Perhaps by shuffle, you mean the bit reversal permutation? That is not what Im asking. In fact, in the link given, the array gets shuffled although it is still a constant geometry problem. Apr 11, 2020 at 18:14
• This looks like an XY question. Perhaps you should edit your question -- or ask another one -- that's based on what you're really trying to do that you think might be aided by an in-place constant geometry NTT. I.e., are you trying to perform large NTTs on magnetic tape (which is where I've seen in-place FFT's cited), on processors with deeply cached memory, on GPUs, in an FPGA or ASIC, or what? If you do that, and state the constraints on your computational environment, then people will be able to do a better job helping you. Feb 2 at 20:45

If you hold both of these to be true, you have a butterfly that operates on two input values (let's look at 1 and N/2 + 1, as our example), and then writes the output to the same slots, 1 and N/2 + 1. Then, you run it again, the butterfly again operates on the same data, and you write the output to the same place. Therefore, each value of the output of an in-place, constant-geometry NTT would only depend on two of the inputs, and at least half the outputs of the NTT depend on all of the inputs. In particular, the evaluation of the polynomial at any primitive Nth root of unity changes when you change any of the inputs, since the evaluation is $$[\omega^i] \cdot [a_i]$$