fft_iterative.h

#ifndef ITERATIVE_FFT_H
#define ITERATIVE_FFT_H
 
#include <complex>
#include <cstddef>  // for size_t
#include <vector>
 
namespace fft {
using cd = std::complex<double>;
 
// Check if an integer is a power of two.
bool is_power_of_two(size_t n);
 
// Return the next power of two >= n.
size_t next_power_of_two(size_t n);
 
// In-place bit-reversal permutation of vector a (length must be power of two).
void bit_reverse_permute(std::vector<cd> &a);
 
void pad_to_pow_two(std::vector<cd> &a, size_t &N);
 
// Iterative in-place FFT.
// Parameters:
//  - a: input/output buffer (modified in-place).
//  - inverse: false for forward FFT, true for inverse FFT.
void iterative_fft(std::vector<cd> &a, bool inverse = false);
 
// Convenience wrapper: return FFT result as a new vector.
// Parameters:
//  - input: const input vector.
//  - inverse: false for forward FFT, true for inverse FFT.
std::vector<cd> fft_copy(const std::vector<cd> &input, bool inverse = false);
 
// Iterative in-place 2D FFT.
// Parameters:
//  - data: input/output buffer (modified in-place).
//  - inverse: false for forward FFT, true for inverse FFT.
void iterative_fft_2d(std::vector<cd> &a, size_t width, size_t height, bool inverse = false);
 
// Convenience wrapper: return 2D FFT result as a new vector.
// Parameters:
//  - input: const input vector.
//  - inverse: false for forward FFT, true for inverse FFT.
std::vector<cd> iterative_fft_2d_copy(const std::vector<cd> &input, size_t width, size_t height,
                                      bool inverse = false);
}  // namespace fft
 
#endif  // ITERATIVE_FFT_H