Нужен быстрый генератор случайных чисел для c ++

Я пытаюсь сделать некоторую замену opt-3 на моем генераторе TSP для эвклидовых расстояний, и поскольку во многих случаях у меня больше, чем ~ 500 узлов, мне нужно случайным образом выбрать хотя бы один из трех узлов, которые я хочу попробовать поменять местами ,

Поэтому в основном мне нужна функция случайного числа, которая быстрая . (нормальный rand () слишком медленный). Это не должно быть потрясающим, достаточно хорошим.

EDIT: Я забыл упомянуть, я сижу в среде, где я не могу добавить никаких библиотек, кроме стандартной языковой библиотеки (например, STL, iostream и т. Д.). Поэтому никакого повышения = /

В другой теме упоминается генератор xorshf Marsaglia, но никто не отправил код.

static unsigned long x=123456789, y=362436069, z=521288629; unsigned long xorshf96(void) { //period 2^96-1 unsigned long t; x ^= x << 16; x ^= x >> 5; x ^= x << 1; t = x; x = y; y = z; z = t ^ x ^ y; return z; } 

Я использовал это по всему месту. Единственное, что не удалось, было, когда я пытался создавать случайные двоичные матрицы. Прошлое около 95x95 матриц, оно начинает генерировать слишком мало или слишком много сингулярных матриц (я забываю, что). Было показано, что этот генератор эквивалентен регистру обратной связи с линейным сдвигом. Но если вы не делаете криптографию или серьезную работу монте-карло, этот генератор скалывает.

Две хорошие альтернативы с сайта Intel:

1) fastrand – на 2.01 X быстрее, чем std rand (). Процедура возвращает одно целое число, аналогичное диапазону выходных значений, как C lib.

 inline int fastrand() { g_seed = (214013*g_seed+2531011); return (g_seed>>16)&0x7FFF; } 

2) версия SSE (см. Ссылку ниже) составляет около 5,5 X так же быстро, как и std rand (), однако она генерирует 4 случайных значения за раз, требует обработчика с sse (почти все) и сложнее.

http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/

См. Эти генераторы от генератора случайных чисел генерала Джорджа Марсалья. Они реализованы как macros C, и они молниеносно, всего несколько операций на число сгенерировано.

У Mersenne Twister есть несколько быстрых реализаций.

Начиная с архитектуры Ivy Bridge, Intel добавила инструкцию RdRand CPU, а AMD добавила ее позже в июне 2015 года. Поэтому, если вы нацеливаете процессор, который является достаточно новым и не против использования (встроенной) сборки, самый быстрый способ генерации случайных чисел должен быть при вызове команды RdRand CPU получить 16- или 32- или 64-разрядное случайное число, как описано здесь . Прокрутите до середины страницы примеры кода. На этой ссылке есть также пример кода для проверки текущего процессора для поддержки команды RdRand, а также см. Также Википедию для объяснения того, как это сделать с инструкцией CPUID.

Связанный вопрос: Использование аппаратного генератора случайных чисел из песчаного моста? (хотя, согласно Википедии, команда RdRand впервые появилась в Ivy Bridge, но не в архитектуре Sandy Bridge, как говорит этот вопрос)

Пример кода C ++ на основе _rdrand64_step () :

 #include  uint64_t randVal; if(!_rdrand64_step(&randVal)) { // Report an error here: random number generation has failed! } // If no error occured, randVal contains a random 64-bit number 

rand () на самом деле проклят быстро, и я не думаю, что вы найдете гораздо быстрее.

Если это на самом деле замедляет вас (что я сомневаюсь), вам нужно изменить архитектуру.

Я рекомендую предварительно заполнять длинный список случайными числами , а затем, когда вам это нужно, просто возьмите один из списка, а не создайте его. Возможно, вы сможете повторно заполнить список фоновым streamом.

Даже в этот пост лет, он появился, когда я искал аналогичный ответ, и ответ, который я использовал, даже не в нем. Поэтому я добавляю тот, который я нашел;

#include msdn entry

Этот подход будет строить автономный генератор случайных чисел, и я нашел его намного более случайным, чем rand()%x ; более нескольких сотен тысяч итераций. rand()% никогда не будет бросать 16+ голов / хвостов подряд, когда он должен делать все 65K попыток. Этот не только делает это, но и делает это через четверть времени.

Вот как я сам реализую #include :

 //create rng_gen, using mt technique, with range 0,1 (coin) and 1,6(dice); std::random_device rd; //seed std::mt19937 gen(rd()); //seed for rd(merzenne twister) std::uniform_int_distribution<> rng_coin(0, 1); //rng1 range std::uniform_int_distribution<> rng_dice(1, 6); ///rng2 range rng_coin(gen); //will apply rng1 range on (gen) object. Is very fast rng_dice(gen); //will apply rng2 range, returns int. //will output 1000 cointosses to console for (int i=0;i<1000;++i)std::cout< 

вы можете заранее создать кучу случайных бит и очистить их по 2 за раз (так как вам нужно только случайное число от 1 до 3)?

Библиотека Boost имеет набор случайных генераторов. Здесь можно найти график производительности.

EDIT: Этот ответ был здесь до редактирования исходного вопроса. Но я надеюсь, что это может быть полезно, поэтому я оставляю его здесь.

Я думаю, что WELL очень хорош, а WELL512a довольно короткий. http://www.iro.umontreal.ca/~panneton/WELLRNG.html WELL44497a является сложным в то же время. Однако WELL генерирует число от 0 до 1.