SplitMix64

components/splitmix64.hpp · GitHub で見る

共通ページ

#include "lib/components/splitmix64.hpp"

SplitMix64 rng(123);
auto random = rng();
auto hash = splitmix64(42);

操作	内容・返り値	計算量
SplitMix64(seed = 0)	64 bit 乱数生成器を構築	\(O(1)\)
rng()	次の uint64_t 乱数を返す	\(O(1)\)
splitmix64(x)	64 bit 整数を混合して返す	\(O(1)\)

SplitMix64(seed = 0) は 64 bit 乱数生成器です。splitmix64(x) は加算前処理を含まない 64 bit のミキサーです。

生成・混合は時間・空間ともに \(O(1)\) です。

検証コード

• test/data_dependent_tree.test.cpp
• test/discrete_log.test.cpp
• test/dynamic_connectivity.test.cpp
• test/factorize.test.cpp
• test/geometry_closest_pair.test.cpp
• test/geometry_convex_hull.test.cpp
• test/geometry_furthest_pair.test.cpp
• test/lazy_reversible_treap_affine.test.cpp
• test/lazy_reversible_treap_reverse.test.cpp
• test/mod_pow_log.test.cpp
• test/mod_sqrt.test.cpp
• test/multiplicative_convolution.test.cpp
• test/partially_retroactive_priority_queue.test.cpp
• test/rolling_hash.test.cpp
• test/rooted_tree_hash.test.cpp

コード

#ifndef SPLITMIX64_HPP
#define SPLITMIX64_HPP

#include <cstdint>

inline std::uint64_t splitmix64(std::uint64_t x) {
	x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
	x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
	return x ^ (x >> 31);
}
class SplitMix64 {
	std::uint64_t state;

  public:
	explicit SplitMix64(std::uint64_t seed = 0) : state(seed) {}
	std::uint64_t operator()() { return splitmix64(state += 0x9e3779b97f4a7c15ULL); }
};

#endif

Back to top page