23 std::vector<std::complex<T> >
24 dft(
const std::vector<T> & inputData) {
25 const size_t length = inputData.size();
26 std::vector<std::complex<T> >
toRet(length, std::complex<T>(0.0, 0.0));
27 for (
size_t k = 0;
k < length;
k++) {
28 for (
size_t n = 0; n < length; n++) {
29 toRet[
k] += inputData[n] * nthRootOfUnity<T>(
k * n, length);
36 std::vector<std::complex<T> >
37 idft(
const std::vector<std::complex<T> > & inputData) {
38 std::vector<std::complex<T> >
toRet;
39 const size_t length = inputData.size();
41 for (
size_t n = 0; n < length; n++) {
42 for (
size_t k = 0;
k < length;
k++) {
44 nthRootOfUnity<T>(-
static_cast<int>(
k * n), length);
53 std::vector<std::complex<T> >
54 fft(
const std::vector<T> & inputData) {
55 std::vector<std::complex<T> > result(inputData.size(), std::complex<T>(0, 0));
56 std::vector<std::complex<T> > scratch(inputData.size(), std::complex<T>(0, 0));
62 std::vector<std::complex<T> >
63 ifft(
const std::vector<std::complex<T> > & inputData) {
64 std::vector<std::complex<T> > result(inputData.size(), std::complex<T>(0, 0));
65 std::vector<std::complex<T> > scratch(inputData.size(), std::complex<T>(0, 0));
66 _fftHelperRadix2<std::complex<T>, decltype(result.begin()), T,
67 -1>(inputData, result.begin(), scratch.begin(), 0, 0);
68 for (
auto & num : result) {
74 template<
typename T,
typename Iter,
typename U = T,
int dir = 1>
77 size_t offset,
size_t stride) {
78 const size_t len = (inputData.size() >> stride);
80 _fftHelperRadix2<T, Iter, U, dir>(inputData, scratch, result,
offset,
83 _fftHelperRadix2<T, Iter, U, dir>(inputData, scratch + (len / 2),
84 result + (len / 2),
offset + (1 << stride),
87 for (
size_t i = 0;
i < len / 2;
i++) {
88 result[
i] = scratch[
i] +
89 nthRootOfUnity<U>(dir *
i, len) * scratch[
i + len / 2];
90 result[
i + len / 2] = scratch[
i] - nthRootOfUnity<U>(dir *
i, len) *
94 result[0] = inputData[
offset] + inputData[
offset + (1 << stride)];
95 result[1] = inputData[
offset] - inputData[
offset + (1 << stride)];
std::vector< std::complex< T > > ifft(const std::vector< std::complex< T > > &inputData)
void _fftHelperRadix2(const std::vector< T > &inputData, Iter result, Iter scratch, size_t offset, size_t stride)
std::vector< std::complex< T > > fft(const std::vector< T > &inputData)
std::vector< std::complex< T > > dft(const std::vector< T > &inputData)
std::vector< std::complex< T > > idft(const std::vector< std::complex< T > > &inputData)
std::complex< T > nthRootOfUnity(T fraction)