Walsh–Hadamard Transform

components/walsh_hadamard.hpp · GitHub で見る

共通ページ

#include "lib/components/walsh_hadamard.hpp"

std::vector<long long> a{1, 2, 3, 4};
walsh_hadamard(a); // {10,-2,-4,0}
walsh_hadamard(a);
for (auto &x : a) x /= 4; // {1,2,3,4}

操作	内容・返り値	計算量
walsh_hadamard(a)	その場で非正規化の Walsh–Hadamard 変換	\(O(n\log n)\)

長さは 2 の冪とします。同じ変換をもう一度適用し、各要素を長さで割ると逆変換になります。

引数は vector<T> で、戻り値は void、元の配列を直接書き換えます。要素型は加算・減算に対応させます。逆変換では長さによる除算も必要です。元に戻す場合は、例の 4 を実際の配列長に置き換えます。

長さを \(n\) として時間は \(O(n\log n)\)、追加空間は \(O(1)\) です。要素の演算は \(O(1)\) とします。

検証コード

• test/bitwise_and_convolution.test.cpp
• test/bitwise_xor_convolution.test.cpp

コード

#ifndef WALSH_HADAMARD_HPP
#define WALSH_HADAMARD_HPP

#include <bit>
#include <cassert>
#include <cstddef>
#include <vector>

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC push_options
#pragma GCC optimize("O3")
#endif

namespace walsh_hadamard_detail {
template <class T>
void stages(std::vector<T> &a, std::size_t start, std::size_t n, std::size_t half) {
	auto step = [&](std::size_t low, std::size_t high) {
		T x = a[low], y = a[high];
		a[low] = x + y;
		a[high] = x - y;
	};
	for (; half < n / 2; half *= 4)
		for (std::size_t block = start; block < start + n; block += 4 * half)
			for (std::size_t j = block; j < block + half; ++j) {
				step(j, j + half);
				step(j + 2 * half, j + 3 * half);
				step(j, j + 2 * half);
				step(j + half, j + 3 * half);
			}
	if (half < n)
		for (std::size_t j = start; j < start + half; ++j) step(j, j + half);
}
}

template <class T>
void walsh_hadamard(std::vector<T> &a) {
	assert(a.empty() || std::has_single_bit(a.size()));
	constexpr std::size_t block = 1024;
	if (a.size() <= block) walsh_hadamard_detail::stages(a, 0, a.size(), 1);
	else {
		for (std::size_t start = 0; start < a.size(); start += block)
			walsh_hadamard_detail::stages(a, start, block, 1);
		walsh_hadamard_detail::stages(a, 0, a.size(), block);
	}
}

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC pop_options
#endif

#endif

Back to top page