32 bit Barrett 演算

components/barrett32.hpp · GitHub で見る

共通ページ

#include "lib/components/barrett32.hpp"

Barrett32 m(1000000007);
auto x = m.mul(123, 456);

関数・メンバ	内容・返り値	計算量
Barrett32(mod)	\(1\leq\mathrm{mod}<2^{32}\) の法で初期化	\(O(1)\)
reduce(x)	uint64_t の x の非負の剰余	\(O(1)\)
mul(a,b)	uint32_t の a * b の非負の剰余	\(O(1)\)
pow(a,e)	uint32_t の底と uint64_t の指数から累乗の非負の剰余	\(O(\log e)\)
mod	法	\(O(1)\)
reciprocal	剰余計算用の定数	\(O(1)\)

構築後にメンバを書き換えないでください。法が 1 の場合は全ての演算が 0 を返します。

構築・reduce・mul は \(O(1)\) 時間、pow は \(O(\log e)\) 時間です。追加空間は \(O(1)\) です。

検証コード

• test/binomial_mod.test.cpp
• test/binomial_prefix_sum_light.test.cpp
• test/binomial_prefix_sum_online_light.test.cpp
• test/comb.test.cpp
• test/comb_light.test.cpp
• test/comb_prime_mod.test.cpp
• test/comb_prime_mod_light.test.cpp
• test/discrete_log.test.cpp
• test/multiplicative_convolution.test.cpp
• test/multiplicative_convolution_light.test.cpp

コード

#ifndef BARRETT32_HPP
#define BARRETT32_HPP

#include <cassert>
#include <cstdint>

struct Barrett32 {
	std::uint32_t mod;
	std::uint64_t reciprocal;
	explicit Barrett32(std::uint32_t m) : mod(m), reciprocal(m > 1 ? std::uint64_t((__uint128_t(1) << 64) / m) : 0) {
		assert(m > 0);
	}
	std::uint32_t reduce(std::uint64_t x) const {
		if (mod == 1) return 0;
		std::uint64_t q = (__uint128_t(x) * reciprocal) >> 64, r = x - q * mod;
		return r < mod ? r : r - mod;
	}
	std::uint32_t mul(std::uint32_t a, std::uint32_t b) const { return reduce(std::uint64_t(a) * b); }
	std::uint32_t pow(std::uint32_t a, std::uint64_t e) const {
		std::uint32_t r = mod == 1 ? 0 : 1;
		for (; e; e >>= 1, a = mul(a, a)) if (e & 1) r = mul(r, a);
		return r;
	}
};

#endif

Back to top page