1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Is this question basically asking if it is possible to have an FFT that doesn't shuffle the data (?). $\endgroup$
    – A_A
    Commented Apr 9, 2020 at 8:29
  • $\begingroup$ 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. $\endgroup$
    – Partha
    Commented Apr 11, 2020 at 18:14
  • $\begingroup$ 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. $\endgroup$
    – TimWescott
    Commented Feb 2 at 20:45

1 Answer 1

Reset to default
1
$\begingroup$

An in-place NTT is one where the butterflies operate on the data and return it to the place it was. A constant-geometry NTT is one where the butterflies access data in the same pattern and then the output is permuted in the same way. In this sense, an in-place NTT is one where the butterflies might have a variable pattern of access, but the permutation is the identity, or no-op; a constant-geometry NTT is one where the butterflies have identical inputs every time.

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]$

If you are doing this in software, you should use the in-place method. If you're doing it in hardware, you should probably use the constant-geometry scheme. If you're fighting the end of the vectorized Cooley-Tukey NTT loop in a highly vectored machine, you may just have to do some kind of transpose operation; you won't have a way around doing some kind of data movement. An in-place NTT has to follow the same pattern of butterfly geometries.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.