FPS の結果配列への一括変換

components/fps_output.hpp · GitHub で見る

共通ページ

Linux x86_64 / GCC 用の内部部品です。呼び出し側が AVX2 対応を実行時に確認します。

操作	内容・返り値	計算量
prepare_fps_output(out,total)	出力配列に total 個分の領域を予約	再確保なし: \(O(1)\)、再確保時: 既存要素数に比例＋確保時間
append_fps_words<montgomery>(out,in,n)	内部ワードを係数へ変換して追加	予約済み: \(O(n)\)、再確保時: 既存要素数＋n に比例

fps_detail::prepare_fps_output(out,total) は結果の最終サイズ total を収容する容量を確保します。既に容量が十分なら何もしません。新しく容量を増やし、これから書く範囲が 131072 語以上の場合、その範囲に完全に含まれる 2 MiB ページへ MADV_HUGEPAGE、4 KiB ページへ MADV_POPULATE_WRITE を指定します。既存の要素は変更せず、サイズも増やしません。これは OS のページ配置・事前準備の助言であり、オブジェクトの生成・書き換えは行いません。未対応の定数はコンパイル時に省略し、システムコールが失敗した場合は通常の割り当てのまま進みます。

大きな結果を複数回に分けて追加する呼び出し側は、追加の前に最終サイズで一度呼びます。append_fps_words 自身も、容量を増やす必要がある場合にこの処理を使います。

fps_detail::append_fps_words<montgomery>(out,in,n) は、in の \(n\) 個の unsigned ワードを std::vector<Mint> の末尾へ追加します。montgomery=true なら入力は内部 Montgomery 表現 \([0,2p)\)、偽なら通常の剰余 \([0,p)\) とし、後者は Montgomery 表現へ変換します。ここで \(p=998244353\) です。

入力は出力と重ねません。入力にはちょうど \(n\) 個の要素があればよく、アラインメントや padding は要求しません。\(n=0\) なら何もせず、入力が null でも構いません。結果の長さが out.max_size() を超える場合は std::length_error を送出します。

64 個の生存する Mint オブジェクトへコピー・変換してから、vector の通常の insert で追加します。vector のサイズを超えた領域への書き込みや、オブジェクトの寿命を省く操作は行いません。

追加処理の時間は \(O(n)\)、変換バッファは \(O(1)\) 空間です。容量の増加と OS の事前ページ準備は、新しい総容量を \(N\) として \(O(N)\) 時間・追加空間を使います。既存の \(m\) 要素を移す再確保には追加で \(O(m)\) 時間が必要です。

依存ライブラリ

• modint998244353 の共通剰余演算
• modint998244353

検証コード

• test/convolution.test.cpp
• test/cyclic_convolution.test.cpp
• test/fps_bostan_mori.test.cpp
• test/fps_compose.test.cpp
• test/fps_compose_large.test.cpp
• test/fps_compositional_inverse.test.cpp
• test/fps_compositional_inverse_large.test.cpp
• test/fps_divmod.test.cpp
• test/fps_divmod.test.cpp
• test/fps_exp.test.cpp
• test/fps_exp.test.cpp
• test/fps_exp_sparse.test.cpp
• test/fps_exp_sparse.test.cpp
• test/fps_interpolate.test.cpp
• test/fps_inv.test.cpp
• test/fps_inv.test.cpp
• test/fps_inv_sparse.test.cpp
• test/fps_inv_sparse.test.cpp
• test/fps_linear_recurrence.test.cpp
• test/fps_linear_recurrence.test.cpp
• test/fps_log.test.cpp
• test/fps_log.test.cpp
• test/fps_log_sparse.test.cpp
• test/fps_log_sparse.test.cpp
• test/fps_pow.test.cpp
• test/fps_pow.test.cpp
• test/fps_pow_sparse.test.cpp
• test/fps_pow_sparse.test.cpp
• test/fps_rational_coefficients.test.cpp
• test/fps_rational_coefficients.test.cpp
• test/fps_sqrt.test.cpp
• test/fps_sqrt.test.cpp
• test/fps_sqrt_sparse.test.cpp
• test/fps_sqrt_sparse.test.cpp
• test/fps_taylor_shift.test.cpp
• test/fps_taylor_shift.test.cpp
• test/multiplicative_convolution.test.cpp
• test/multipoint_eval.test.cpp
• test/multivariate_convolution.test.cpp
• test/ordered_convolution.test.cpp
• test/polynomial_inv_mod.test.cpp
• test/power_projection.test.cpp

コード

#ifndef CP_COMPONENTS_FPS_OUTPUT_HPP
#define CP_COMPONENTS_FPS_OUTPUT_HPP

#include "mint_arithmetic.hpp"
#include <array>
#include <cstring>
#include <cstdint>
#include <stdexcept>
#include <type_traits>
#include <vector>

#if defined(__linux__) && defined(__x86_64__) && defined(__GNUC__) && !defined(__clang__)
#include <immintrin.h>
#include <sys/mman.h>
#pragma GCC push_options
_Pragma("GCC target(\"avx2\")")
#pragma GCC optimize("O3")

namespace fps_detail {

inline void prepare_fps_output(std::vector<mint> &out, std::size_t n) {
	if (n <= out.capacity()) return;
	out.reserve(n);
	if (n - out.size() < (1u << 17)) return;
	const auto first = reinterpret_cast<std::uintptr_t>(out.data() + out.size());
	const auto end = reinterpret_cast<std::uintptr_t>(out.data() + n);
	[[maybe_unused]] const auto advise = [first, end](std::uintptr_t alignment, int advice) {
		const auto lo = (first + alignment - 1) & ~(alignment - 1), hi = end & ~(alignment - 1);
		if (lo < hi) static_cast<void>(madvise(reinterpret_cast<void *>(lo), hi - lo, advice));
	};
#if defined(MADV_HUGEPAGE)
	advise(2u * 1024 * 1024, MADV_HUGEPAGE);
#endif
#if defined(MADV_POPULATE_WRITE)
	advise(4096, MADV_POPULATE_WRITE);
#endif
}

template <bool montgomery>
inline void append_fps_words(std::vector<mint> &out, const unsigned *in, std::size_t n) {
	static_assert(sizeof(mint) == sizeof(unsigned) && std::is_trivially_copyable_v<mint>);
	if (n == 0) return;
	if (n > out.max_size() - out.size()) throw std::length_error("fps output");
	prepare_fps_output(out, out.size() + n);
	std::array<mint, 64> batch;
	std::size_t i = 0;
	for (; i + 64 <= n; i += 64) {
		if constexpr (montgomery) std::memcpy(static_cast<void *>(batch.data()), in + i, sizeof(batch));
		else {
#pragma GCC unroll 8
			for (int j = 0; j < 64; j += 8) {
				const auto x = mint_detail::Ops::mul8(_mm256_loadu_si256(reinterpret_cast<const __m256i *>(in + i + j)), _mm256_set1_epi32(932051910u));
				std::memcpy(static_cast<void *>(batch.data() + j), &x, sizeof(x));
			}
		}
		out.insert(out.end(), batch.begin(), batch.end());
	}
	for (; i < n; ++i) {
		if constexpr (montgomery) out.emplace_back(mint::word(in[i]));
		else out.emplace_back(mint::raw(in[i]));
	}
}
}
#pragma GCC pop_options
#endif
#endif

Back to top page