3

Как можно реализовать генерацию больших случайных чисел?

С помощью встроенных функций rand и srand генерируются значения только до 32 тысяч.

Я бы хотел сгенерировать числа вплоть до миллиардов.

3
  • 3
    std::mt19937_64 генерирует 64 рандомных бита за раз. Для 128 - вызываете дважды. 17 дек 2019 в 9:46
  • @HolyBlackCat а как это реализовать?
    – David
    17 дек 2019 в 9:46
  • @David, использовать библиотеки для длинной арифметики. Либо хранить отдельно просто, в структуре запечатать можно. А вообще, если в системе есть 128 битный тип, то просто битовым сдвигом.
    – megorit
    17 дек 2019 в 11:10

5 ответов 5

6

Всего лишь?

Миллиард вполне влазит в 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;
};

Вот пример работы.

10
  • а можно этот код как - то сократить?
    – David
    17 дек 2019 в 9:52
  • 1
    А зачем? его очень просто использовать - скажем, Random64 r; Если хочется - Random64 r(time(0)); И все. Дальше случайное число - r(). Или число в диапазоне от 0 до 100 - r(0,100). Зачем что-то сокращать? Сам алгоритм - так точно не надо :)
    – Harry
    17 дек 2019 в 9:56
  • Я сейчас попытался протестировать, действительно генерируется всё, но не полностью случайные или может я что - то неправильно понял. При повторном запуске программы генерируются те же числа, что при первом запуске программы, почему так?
    – David
    17 дек 2019 в 10:09
  • Seed не используете. Вы когда rand() запускаете - то же самое, если только srand() не выполните. Здесь srand() по сути внесен в конструктор - создавайте генератор, например, как я написал, как Random64 r(time(0));
    – Harry
    17 дек 2019 в 10:11
  • 1
    Ну просто указываете при вызове r(min,max).
    – Harry
    17 дек 2019 в 10:53
4

Если у вас есть готовый генератор чисел длиной n битов, то получить из него генератор более длинных чисел вы можете обычной конкатенацией битовых последовательностей, полученных из последовательных вызовов имеющегося генератора.

В своем вопросе вы упомянули генератор, генерирующий 15 псевдослучайных битов. Пять вызовов такого генератора дадут вам 64-битное псевдослучайное число

uint64_t rand64 = ((((((((uint64_t) rand() << 15) + rand()) << 15) + rand()) << 15) + rand()) << 15) + rand();

"Лишние" биты, если таковые имеются, вы можете просто выбросить (как я сделал выше), а можете сохранить для следующего длинного числа.

Разумеется, бесплатных завтраков не бывает. Раз размер внутреннего состояния генератора остался неизменным, а генерируемые числа стали длиннее, значит где-то в другом месте что-то стало "короче". А именно: короче в соответствующее количество раз стал период такого генератора. Критично вам это или не критично - зависит от вашего приложения.

11
  • 1
    В этом случае не будет "хороших" псевдослучайных чисел, так как будет большая алгоритмическая компонента.
    – becouse
    17 дек 2019 в 9:58
  • Хм.. Я почти так же написал, но у меня последний не rand(), а rand()&15.
    – Qwertiy
    17 дек 2019 в 10:02
  • @becouse: В таком варианте числа настолько же хороши, насколько хорош сам генератор. Платите вы за это, однако, кратным сокращением периода генератора. 17 дек 2019 в 10:02
  • Кстати, тип же привести надо, а то он всё равно под 32 бита подрежется.
    – Qwertiy
    17 дек 2019 в 10:04
  • @AnT об этом и речь, что вы не получаете новую случайную последовательность из существующих, она будет все менее и менее случайной при каждой операции. Если бы этот способ работал никто бы не изобретал новые генераторы)
    – becouse
    17 дек 2019 в 10:05
3

Вот пример генерации для 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 для генерации случайных чисел.

Он не сложный и можно пробовать его реализовать.

1

Если у Вас 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;
}
6
  • В такой реализации get_entropy_mt генератор выполняет в 8 раз больше работы, чем нужно. 17 дек 2019 в 13:05
  • @HolyBlackCat Да, но я воткнул что было под рукой )))
    – Oh-Ben-Ben
    17 дек 2019 в 13:31
  • @HolyBlackCat теперь все норм)
    – Oh-Ben-Ben
    17 дек 2019 в 13:37
  • Для sizeof(T) > sizeof(uint64_t) ничего не поменялось. :) Да и новый std::mt19937_64 создавать при каждом вызове - не комильфо. 17 дек 2019 в 14:33
  • @HolyBlackCat Будет время перепишем) По поводу размера больше - тоже )))) спасибо за ревью)
    – Oh-Ben-Ben
    17 дек 2019 в 17:20
0
((((((((unsigned long long)rand() << 15) | rand()) << 15) | rand()) << 15) | rand()) << 4) | (rand() & 15)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.