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 Да, но я воткнул что было под рукой ))) 17 дек 2019 в 13:31
  • @HolyBlackCat теперь все норм) 17 дек 2019 в 13:37
  • Для sizeof(T) > sizeof(uint64_t) ничего не поменялось. :) Да и новый std::mt19937_64 создавать при каждом вызове - не комильфо. 17 дек 2019 в 14:33
  • @HolyBlackCat Будет время перепишем) По поводу размера больше - тоже )))) спасибо за ревью) 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 you have read our privacy policy.

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