Как можно реализовать генерацию больших случайных чисел?
С помощью встроенных функций rand и srand генерируются значения только до 32 тысяч.
Я бы хотел сгенерировать числа вплоть до миллиардов.
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуВсего лишь?
Миллиард вполне влазит в int
. В long long
поместится несколько миллиардов миллиардов - для стандартной библиотеки это нормальная штатная работа...
Стандартная библиотека <random>
вам в помощь.
Но даже если вы не хотите пользоваться стандартом C++11, то на помощь вам придет Кнут - вот пара генераторов, которые я писал давно-давно (когда библиотека давала только rand()
) по Кнуту (простите, алгоритм переписывать не буду, смотрите в книгах):
class Random
{
public:
typedef int RandomValue;
Random& operator = (int seed) { X = seed; return *this; }
Random(int seed = 1):X(seed){};
int operator()(int seed = 0)
{
const int MM = 2147483647;
const int AA = 48271;
const int QQ = 44488;
const int RR = 3399;
if (seed != 0) X = seed;
X = AA*(X%QQ)-RR*(X/QQ);
if (X < 0) X += MM;
return X-1;
}
// Не включая max
int operator()(int min, int max)
{
return (*this)()%(max-min) + min;
}
private:
int X;
};
class Random64
{
typedef unsigned long long uint64;
public:
typedef uint64 RandomValue;
Random64& operator = (uint64 seed) { X = seed; return *this; }
Random64(uint64 seed = 0):X(seed){};
uint64 operator()(uint64 seed = uint64(-1))
{
const uint64 a = 3202034522624059733ULL;
const uint64 c = 1ULL;
if (seed != uint64(-1)) X = seed;
uint64 Y = a * X + c;
X = a * Y + c;
Y = (Y&0xFFFFFFFF00000000ULL) | (X >> 32);
return Y;
}
// Не включая max
uint64 operator()(uint64 min, uint64 max)
{
return (*this)()%(max-min) + min;
}
private:
uint64 X;
};
Вот пример работы.
Random64 r;
Если хочется - Random64 r(time(0));
И все. Дальше случайное число - r()
. Или число в диапазоне от 0 до 100 - r(0,100)
. Зачем что-то сокращать? Сам алгоритм - так точно не надо :)
rand()
запускаете - то же самое, если только srand()
не выполните. Здесь srand()
по сути внесен в конструктор - создавайте генератор, например, как я написал, как Random64 r(time(0));
Если у вас есть готовый генератор чисел длиной n
битов, то получить из него генератор более длинных чисел вы можете обычной конкатенацией битовых последовательностей, полученных из последовательных вызовов имеющегося генератора.
В своем вопросе вы упомянули генератор, генерирующий 15 псевдослучайных битов. Пять вызовов такого генератора дадут вам 64-битное псевдослучайное число
uint64_t rand64 = ((((((((uint64_t) rand() << 15) + rand()) << 15) + rand()) << 15) + rand()) << 15) + rand();
"Лишние" биты, если таковые имеются, вы можете просто выбросить (как я сделал выше), а можете сохранить для следующего длинного числа.
Разумеется, бесплатных завтраков не бывает. Раз размер внутреннего состояния генератора остался неизменным, а генерируемые числа стали длиннее, значит где-то в другом месте что-то стало "короче". А именно: короче в соответствующее количество раз стал период такого генератора. Критично вам это или не критично - зависит от вашего приложения.
rand()
, а rand()&15
.
Вот пример генерации для unsigned long long
//Источник
std::random_device rd;
//Генератор
std::default_random_engine generator(rd());
// Распределение
std::uniform_int_distribution<long long unsigned> distribution(0,0xFFFFFFFFFFFFFFFF);
//Десять длинных случайных чисел
for (int i = 0; i < 10; i++) {
std::cout << distribution(generator) << std::endl;
}
Также вы можете посмотреть на клеточный автомат Стивена Вольфрама, который позволяет получать сколь угодно большие собственно случайные последовательности нулей и единиц и используется в Wolfram Mathematica для генерации случайных чисел.
Он не сложный и можно пробовать его реализовать.
Если у Вас Linux читайте /dev/urandom нормальный такой ПДСЧ
Если win юзайте mt
Вот пример 4 перегрузок функции для генерации данный с ПДСЧ
#include <iostream>
#include <string>
#include <fstream>
#include <iterator>
#include <random>
#include <functional>
#include <vector>
template<typename T>
void get_entropy(T* ptr, const std::size_t size) {
if (ptr == nullptr || size == 0) {
return;
}
#ifdef __linux__
static std::string urandom_path{ "/dev/urandom" };
std::fstream urandom_stream(urandom_path.c_str(), std::fstream::in | std::ios::binary);
if (!urandom_stream.is_open()) {
throw std::runtime_error{ "Error : Cannot open file " + urandom_path };
}
urandom_stream.read(reinterpret_cast<char*>(ptr), sizeof(T)* size);
urandom_stream.close();
#endif // __linux__
#ifdef _WIN32
static std::random_device rand_dev{};
static std::mt19937_64 generator(rand_dev());
auto data_size{sizeof(T) * size};
uint64_t rand_value{0};
while (data_size) {
auto step_copy_size{data_size <= sizeof(rand_value) ? data_size
: sizeof(uint64_t)};
rand_value = generator();
std::memcpy(ptr, &rand_value, step_copy_size);
++ptr;
data_size -= step_copy_size;
}
#endif // _WIN32
}
template<typename T>
T get_entropy() {
T ret{};
get_entropy<T>(&ret, 1);
return ret;
}
template<typename T>
void get_entropy(T* ptr) {
if (ptr == nullptr) {
return;
}
get_entropy<T>(ptr, sizeof(T));
}
template<typename T>
void get_entropy(T* begin_ptr, T* end_ptr) {
if (begin_ptr == nullptr || end_ptr == 0) {
return;
}
auto size{ end_ptr - begin_ptr };
if (!size) {
return;
}
if (size < 0) {
get_entropy<T>(end_ptr, std::abs(size));
return;
}
get_entropy<T>(begin_ptr, size);
}
template<typename T>
T entripy_distribution(T val, T low, T height) {
low = std::min(low, height);
height = std::max(low, height);
++height;
--low;
T dist{ height - low - 1 };
if (val < low) {
auto x{ low - val };
x = x / (dist);
val += (x + 1) * (dist);
}
if (val > height) {
auto x{ val - height };
x = x / (dist);
val -= (x + 1) * (dist);
}
return val;
}
struct s
{
s() :a(0), b(0) {}
uint64_t a;
uint64_t b;
void print() {
std::cout << "a :" << this->a << " b : " << this->b << std::endl;
}
};
int main() {
std::ostream_iterator<uint64_t> stdout_it{ std::cout, "\n" };
std::cout << "Gen singl value v1 no args: " << std::endl;
for (auto i{ 0 }; i < 10; ++i) {
stdout_it = entripy_distribution<uint64_t>(get_entropy<uint64_t>(), 1'000'000'000, 2'000'000'000);
}
std::cout << "Gen singl value v2 ptr: " << std::endl;
uint64_t val{ 0 };
for (auto i{ 0 }; i < 10; ++i) {
get_entropy<uint64_t>(&val);
stdout_it = val;
}
std::cout << "Gen singl value v3 ptr + size: " << std::endl;
for (auto i{ 0 }; i < 10; ++i) {
get_entropy<uint64_t>(&val, sizeof(val));
stdout_it = val;
}
std::cout << "Gen singl value v4 ptr + ptr: " << std::endl;
for (auto i{ 0 }; i < 10; ++i) {
get_entropy<uint64_t>(&val, &val + sizeof(val));
stdout_it = val;
}
std::cout << "Gen array v1: no args" << std::endl;
std::vector<uint64_t> v(10);
get_entropy<uint64_t>(v.data(), v.size());
for (const auto& val : v) {
stdout_it = val;
}
std::cout << "Gen array v2: ptr " << std::endl;
std::vector<uint64_t> v2(10);
auto f{ []() {return entripy_distribution<uint64_t>(get_entropy<uint64_t>(), 0, 10); } };
std::generate(std::begin(v2), std::end(v2), f);
for (const auto& val : v2) {
stdout_it = val;
}
std::cout << "Gen array v3: ptr + size " << std::endl;
auto arr_size{ 10 };
uint64_t* arr = new uint64_t[arr_size];
get_entropy<uint64_t>(arr, arr_size);
for (auto i{ 1 }; i < arr_size; ++i) {
stdout_it = arr[i];
}
delete[] arr;
std::cout << "Gen array v4: ptr + ptr " << std::endl;
std::vector<uint64_t> v3(10);
uint64_t* arr2 = new uint64_t[arr_size];
get_entropy<uint64_t>(&(*(std::begin(v3))) + v3.size(), &(*(std::begin(v3))));
for (const auto& val : v3) {
stdout_it = val;
}
s obj{};
get_entropy<char>(reinterpret_cast<char*>(&obj), sizeof(obj));
obj.print();
return 0;
}
get_entropy_mt
генератор выполняет в 8 раз больше работы, чем нужно.
17 дек 2019 в 13:05
sizeof(T) > sizeof(uint64_t)
ничего не поменялось. :) Да и новый std::mt19937_64
создавать при каждом вызове - не комильфо.
17 дек 2019 в 14:33
((((((((unsigned long long)rand() << 15) | rand()) << 15) | rand()) << 15) | rand()) << 4) | (rand() & 15)
std::mt19937_64
генерирует 64 рандомных бита за раз. Для 128 - вызываете дважды.