генерировать случайное 64-битное целое число - PullRequest
Новая
       3

генерировать случайное 64-битное целое число

6 голосов
/ 14 ноября 2011

Мне нужна ваша помощь и, пожалуйста, дайте мне несколько советов.Из программирования жемчужин я знаю, что для генерации случайного 30-битного целого числа мы должны написать его так: 

RAND_MAX*rand()+rand()

Но что я мог бы сделать для генерации не 30, а 64-битного случайного целого числа вместо этого?Я думаю, что это очень неэффективный метод, если я умножаю два 30-битных целых числа, а затем снова умножаю 4-битное целое число, так какой метод мне следует использовать?Я использую сейчас popcount_1 другой метод для 64-битного, и я хотел бы проверить его на случайных целых числах (я также измеряю время, которое каждый из них тратит на выполнение задачи)

Ответы [ 6 ]

7 голосов
/ 14 ноября 2011

Во-первых, у меня есть сомнения относительно решения, которое вы публикуете для 30-битного целого числа.RAND_MAX само по себе может быть 31-битным значением, а RAND_MAX * rand() + rand() может переполниться, вызывая неопределенное поведение (и на практике отрицательные значения).

Если вам нужно значение, превышающее гарантированный минимум RAND_MAX, или, если на то пошло, все, что не намного меньше RAND_MAX, единственным решением будет использование последовательных вызовов к rand() и объединение значений, но вам нужно сделать это осторожно и проверить правильностьРезультаты.(В большинстве реализаций rand() используются линейные конгруэнтные генераторы, которые хотя и подходят для некоторых задач, но не особенно хороши в этом случае.) В любом случае, что-то вроде: 

unsigned 
rand256()
{
    static unsigned const limit = RAND_MAX - RAND_MAX % 256;
    unsigned result = rand();
    while ( result >= limit ) {
        result = rand();
    }
    return result % 256;
}

unsigned long long
rand64bits()
{
    unsigned long long results = 0ULL;
    for ( int count = 8; count > 0; -- count ) {
        results = 256U * results + rand256();
    }
    return results;
}

(код в rand256предназначен для устранения неизбежного смещения, которое возникает при сопоставлении значений RAND_MAX с 256 значениями.)

3 голосов
/ 14 ноября 2011

Это может быть решение без умножения: 

r30 = RAND_MAX*rand()+rand()
s30 = RAND_MAX*rand()+rand()
t4  = rand() & 0xf

res = (r30 << 34) + (s30 << 4) + t4
3 голосов
/ 14 ноября 2011

Если boost является опцией, вы можете использовать boost random .

2 голосов
/ 14 ноября 2011

Случайное 64-битное целое число - это, по сути, 64 случайных бита, интерпретируемых как целое число.

Заполните байтовый массив длиной 8 случайными байтами ( см. Здесь, как ) и интерпретируйте их как целое число ( см. Здесь, как ).

1 голос
/ 14 ноября 2011

Типовое решение: 

template <unsigned long long I> struct log2 {
  static const int result = 1 + log2<I/2>::result;
};
template <> struct log2<1> {
  static const int result = 0;
};

template <typename UINT> UINT genrand() {
  UINT result = 0;
  int bits = std::numeric_limits<UINT>::digits;
  int rand_bits = log2<RAND_MAX>::result;
  while (bits > 0) {
    int r = rand();
    while (r >= (1<<rand_bits)) r = rand(); // Retry if too big.
    result <<= rand_bits;
    result += r;
    bits -= rand_bits;
  }
  return result;
}

Использование: unsigned long long R = genrand<unsigned long long>();.

Счетчик bits отслеживает количество необходимых битов.

0 голосов
/ 31 марта 2017

'Возвращает псевдослучайное целочисленное значение между 0 и RAND_MAX (включая 0 и RAND_MAX).' - http://en.cppreference.com/w/cpp/numeric/random/rand

Таким образом, вы должны использовать RAND_MAX + 1 (это все равно, что генерировать цифру цифра за цифрой, а затем преобразовать ее в основание 10) вместо RAND_MAX. Таким образом, вы можете генерировать числа с одной, двумя, тремя и т. Д. Цифрами в базе RAND_MAX + 1 (возможно, с начальными нулями) и преобразовывать их в базу 10 и получать произвольно большие числа.

Все, что вы получаете больше, чем желаемое значение MAX_VALUE, может быть отброшено, и вы по-прежнему получаете 1 / (MAX_VALUE + 1) вероятность получения каждого числа.

Обратите внимание, что этот метод может занять некоторое время, особенно если желаемое значение MAX_VALUE намного меньше максимального значения, которое можно получить перед отбрасыванием ненужных чисел, в качестве ожидаемого количества шагов для получения случайного числа. в [0, MAX_VALUE] с этим алгоритмом: (MAX_OBTAINABLE_VALUE + 1) / (MAX_VALUE + 1)

...