疑似乱数生成器 SplitMix64 (lib/random/split_mix_64.hpp)

• View this file on GitHub
• Last update: 2025-05-22 18:39:33+09:00
• Include: #include "lib/random/split_mix_64.hpp"

Required by

• Treap (lib/binary_tree/treap.hpp)
• 動的配列 (lib/data_structure/dynamic_sequence.hpp)
• 動的ウェーブレット行列 (lib/data_structure/dynamic_wavelet_matrix.hpp)
• 動的完備辞書 (lib/internal/dynamic_bit_vector.hpp)
• 素因数分解 (lib/math/factorize.hpp)
• 疑似乱数生成器 xoroshiro128++ (lib/random/xoroshiro128.hpp)
• 疑似乱数生成器 xoshiro128++ (lib/random/xoshiro128.hpp)

Verified with

• test/aoj/challenge/1508.test.cpp
• test/aoj/course/ITP2_1_B.test.cpp
• test/yosupo/data_structure/orderd_set.test.cpp
• test/yosupo/data_structure/point_set_range_frequency.test.cpp
• test/yosupo/number_theory/factorize.test.cpp
• test/yukicoder/1611.test.cpp

Code

#pragma once
#include <array>
#include <cstdint>
#include <limits>
#include <utility>

/**
 * @brief 疑似乱数生成器 SplitMix64
 * @details 周期：$2^64-1$
 */
struct split_mix_64 {
    using state_type = std::uint64_t;
    using result_type = std::uint64_t;

    constexpr split_mix_64() noexcept : state(1234567890) {}
    constexpr split_mix_64(std::uint64_t seed) noexcept : state(seed) {}

    static constexpr result_type min() noexcept { return std::numeric_limits<result_type>::min(); }
    static constexpr result_type max() noexcept { return std::numeric_limits<result_type>::max(); }
    constexpr result_type operator()() {
        std::uint64_t z = (state += 0x9e3779b97f4a7c15);
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
        z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
        return z ^ (z >> 31);
    }

    constexpr state_type serialize() const noexcept { return state; }
    constexpr void deserialize(const state_type &data) noexcept { state = data; }
    constexpr void deserialize(state_type &&data) noexcept { state = std::move(data); }

    template <std::size_t N>
    constexpr std::array<std::uint64_t, N> generate_seed_sequence() noexcept {
        std::array<std::uint64_t, N> seeds = {};
        for (auto &seed : seeds) seed = operator()();
        return seeds;
    }

    /// @brief a以上b以下の整数を生成
    /// @return uint64_t [a, b]
    std::uint64_t rand_range(std::uint64_t a, std::uint64_t b) {
        if (a == split_mix_64::min() && b == split_mix_64::max()) return operator()();
        return a + operator()() % (b - a + 1);
    }

    /// @brief 0.0以上1.0未満の浮動小数点数を生成
    /// @return double [0, 1)
    double random() { return (double)operator()() / max(); }

  private:
    state_type state;
};

#line 2 "lib/random/split_mix_64.hpp"
#include <array>
#include <cstdint>
#include <limits>
#include <utility>

/**
 * @brief 疑似乱数生成器 SplitMix64
 * @details 周期：$2^64-1$
 */
struct split_mix_64 {
    using state_type = std::uint64_t;
    using result_type = std::uint64_t;

    constexpr split_mix_64() noexcept : state(1234567890) {}
    constexpr split_mix_64(std::uint64_t seed) noexcept : state(seed) {}

    static constexpr result_type min() noexcept { return std::numeric_limits<result_type>::min(); }
    static constexpr result_type max() noexcept { return std::numeric_limits<result_type>::max(); }
    constexpr result_type operator()() {
        std::uint64_t z = (state += 0x9e3779b97f4a7c15);
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
        z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
        return z ^ (z >> 31);
    }

    constexpr state_type serialize() const noexcept { return state; }
    constexpr void deserialize(const state_type &data) noexcept { state = data; }
    constexpr void deserialize(state_type &&data) noexcept { state = std::move(data); }

    template <std::size_t N>
    constexpr std::array<std::uint64_t, N> generate_seed_sequence() noexcept {
        std::array<std::uint64_t, N> seeds = {};
        for (auto &seed : seeds) seed = operator()();
        return seeds;
    }

    /// @brief a以上b以下の整数を生成
    /// @return uint64_t [a, b]
    std::uint64_t rand_range(std::uint64_t a, std::uint64_t b) {
        if (a == split_mix_64::min() && b == split_mix_64::max()) return operator()();
        return a + operator()() % (b - a + 1);
    }

    /// @brief 0.0以上1.0未満の浮動小数点数を生成
    /// @return double [0, 1)
    double random() { return (double)operator()() / max(); }

  private:
    state_type state;
};

Back to top page