実数・複素数の畳み込み

convolution/convolution_fft.hpp · GitHub で見る

共通ページ

#include "lib/convolution/convolution_fft.hpp"

std::vector<double> a{1, 2, 3}, b{4, 5};
auto c = convolution_fft(a, b); // 約 {4,13,22,15}

操作	内容・返り値	計算量
convolution_fft(a,b)	実数または複素数の通常の畳み込みを近似計算	\(O(L\log L)\)

\(\displaystyle c_k = \sum_{i+j=k} a_i b_j\)。係数は浮動小数点型、またはその std::complex です。浮動小数点による近似計算です。

返り値は入力と同じ型の vector です。両方が非空なら長さは a.size()+b.size()-1、どちらかが空なら空配列です。入力は変更しません。整数の厳密な答えが必要な場合は、整数型の配列で convolution_integer を使えます。

\(L = \lvert a\rvert + \lvert b\rvert\) として、時間 \(O(L \log L)\)、追加空間 \(O(L)\) です。

依存ライブラリ

• FFT

検証コード

• test/convolution.test.cpp
• test/convolution_fft.test.cpp
• test/convolution_light.test.cpp
• test/cyclic_convolution.test.cpp
• test/cyclic_convolution_light.test.cpp
• test/multiplicative_convolution.test.cpp
• test/multiplicative_convolution_light.test.cpp
• test/multivariate_convolution.test.cpp
• test/multivariate_convolution_light.test.cpp
• test/ordered_convolution.test.cpp
• test/ordered_convolution_light.test.cpp

コード

#ifndef CONVOLUTION_FFT_HPP
#define CONVOLUTION_FFT_HPP

#include "../components/fft.hpp"
#include <algorithm>
#include <bit>
#include <complex>
#include <cstddef>
#include <type_traits>
#include <vector>

template <class Real>
std::vector<std::complex<Real>> convolution_fft(const std::vector<std::complex<Real>> &a, const std::vector<std::complex<Real>> &b) {
	if (a.empty() || b.empty()) return {};
	std::size_t length = a.size() + b.size() - 1, n = std::bit_ceil(length);
	std::vector<std::complex<Real>> x(a.begin(), a.end()), y(b.begin(), b.end());
	x.resize(n);
	y.resize(n);
	fft(x, false);
	if (&a == &b) y = x;
	else fft(y, false);
	for (std::size_t i = 0; i < n; ++i) x[i] *= y[i];
	fft(x, true);
	x.resize(length);
	return x;
}
template <class Real>
	requires std::is_floating_point_v<Real>
std::vector<Real> convolution_fft(const std::vector<Real> &a, const std::vector<Real> &b) {
	std::vector<std::complex<Real>> x(a.begin(), a.end()), y(b.begin(), b.end());
	auto values = &a == &b ? convolution_fft(x, x) : convolution_fft(x, y);
	std::vector<Real> result;
	result.reserve(values.size());
	for (const auto &x : values) result.push_back(x.real());
	return result;
}

#endif

Back to top page