Straightforward implementation of 1D DFT transform of arbitrary length. Uses passed-in start index and stride to gather inputs from the data vector into the preallocated buffer, computes the result, and writes it back to the same locations in the data vector. Runs in O(length^2) time. Parameters contract_output and expand_input are used to avoid unnecessary calculations. When contract_output is s
| 846 | // of size 'length', on which the transform is then performed. |
| 847 | // |
| 848 | void NaiveDft1D(int64 length, int64 start, int64 stride, bool inverse, |
| 849 | bool contract_output, bool expand_input, |
| 850 | absl::Span<complex128> data, absl::Span<complex128> buffer) { |
| 851 | const bool input_is_zero = |
| 852 | GatherToBuffer(data, length, start, stride, expand_input, buffer); |
| 853 | |
| 854 | if (!input_is_zero) { |
| 855 | const int64 ub = contract_output ? length / 2 + 1 : length; |
| 856 | for (int64 k = 0; k < ub; k++) { |
| 857 | complex128 value = complex128(0.0, 0.0); |
| 858 | for (int n = 0; n < length; n++) { |
| 859 | value += buffer[n] * Twiddle(n * k, length, inverse); |
| 860 | } |
| 861 | data[start + k * stride] = |
| 862 | inverse ? value / complex128(length, 0.0) : value; |
| 863 | } |
| 864 | } |
| 865 | } |
| 866 | |
| 867 | // Non-recursive implementation of the Cooley-Tukey radix-2 decimation in time. |
| 868 | // Performs 1D FFT transform for the lengths, which are powers of 2. Runs in |
no test coverage detected