random.hpp

• View this file on GitHub
• Last update: 2025-01-19 15:28:01+08:00
• Include: #include "random.hpp"

Depends on

• rng.hpp

Required by

• basis.hpp
• frobenius.hpp
• mat_basic.hpp
• mat_extra.hpp
• mat_sparse.hpp

Verified with

• test/convolution/2d_convolution.0.test.cpp
• test/formal_power_series/multivariate_power_series.0.test.cpp
• test/matrix/adjugate_matrix.0.test.cpp
• test/matrix/characteristic_polynomial.0.test.cpp
• test/matrix/characteristic_polynomial.1.test.cpp
• test/matrix/inverse_matrix.0.test.cpp
• test/matrix/matrix_det.0.test.cpp
• test/matrix/matrix_product.0.test.cpp
• test/matrix/pow_of_matrix.0.test.cpp
• test/matrix/sparse_matrix_det.0.test.cpp

Code

#pragma once

#include "rng.hpp"
#include <random>
#include <vector>

template<typename Tp> inline std::vector<Tp> random_vector(int n) {
    std::vector<Tp> res(n);
    xoshiro256starstar rng(std::random_device{}());
    std::uniform_int_distribution<decltype(Tp::mod())> dis(0, Tp::mod() - 1);
    for (int i = 0; i < n; ++i) res[i] = dis(rng);
    return res;
}

template<typename Tp> inline std::vector<Tp> random_vector_without_zero(int n) {
    std::vector<Tp> res(n);
    xoshiro256starstar rng(std::random_device{}());
    std::uniform_int_distribution<decltype(Tp::mod())> dis(1, Tp::mod() - 1);
    for (int i = 0; i < n; ++i) res[i] = dis(rng);
    return res;
}

#line 2 "random.hpp"

#line 2 "rng.hpp"

#include <cstdint>
#include <limits>

// see: https://prng.di.unimi.it/xoshiro256starstar.c
// original license CC0 1.0
class xoshiro256starstar {
    using u64 = std::uint64_t;

    static inline u64 rotl(const u64 x, int k) { return (x << k) | (x >> (64 - k)); }

    u64 s_[4];

    u64 next() {
        const u64 res = rotl(s_[1] * 5, 7) * 9;
        const u64 t   = s_[1] << 17;
        s_[2] ^= s_[0];
        s_[3] ^= s_[1];
        s_[1] ^= s_[2];
        s_[0] ^= s_[3];
        s_[2] ^= t;
        s_[3] = rotl(s_[3], 45);
        return res;
    }

public:
    // see: https://prng.di.unimi.it/splitmix64.c
    // original license CC0 1.0
    explicit xoshiro256starstar(u64 seed) {
        for (int i = 0; i < 4; ++i) {
            u64 z = (seed += 0x9e3779b97f4a7c15);
            z     = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
            z     = (z ^ (z >> 27)) * 0x94d049bb133111eb;
            s_[i] = z ^ (z >> 31);
        }
    }
    // see: https://en.cppreference.com/w/cpp/named_req/UniformRandomBitGenerator
    using result_type = u64;
    static constexpr u64 min() { return std::numeric_limits<u64>::min(); }
    static constexpr u64 max() { return std::numeric_limits<u64>::max(); }
    u64 operator()() { return next(); }
};
#line 4 "random.hpp"
#include <random>
#include <vector>

template<typename Tp> inline std::vector<Tp> random_vector(int n) {
    std::vector<Tp> res(n);
    xoshiro256starstar rng(std::random_device{}());
    std::uniform_int_distribution<decltype(Tp::mod())> dis(0, Tp::mod() - 1);
    for (int i = 0; i < n; ++i) res[i] = dis(rng);
    return res;
}

template<typename Tp> inline std::vector<Tp> random_vector_without_zero(int n) {
    std::vector<Tp> res(n);
    xoshiro256starstar rng(std::random_device{}());
    std::uniform_int_distribution<decltype(Tp::mod())> dis(1, Tp::mod() - 1);
    for (int i = 0; i < n; ++i) res[i] = dis(rng);
    return res;
}

Back to top page