C ++ 11 — Как улучшить этот код генератора случайных чисел в C ++?
Я студент C ++ и работаю над созданием генератора случайных чисел.
На самом деле я должен сказать, что мой алгоритм выбирает число в пределах определенного диапазона.
Я пишу это только из-за моего любопытства.
Я не оспариваю существующие библиотечные функции.
Я всегда использую библиотечные функции при написании приложений, основанных на случайности, но я снова заявляю, что просто хочу сделать это из-за своего любопытства.
Я также хотел бы знать, если что-то не так с моим алгоритмом или с моим подходом.
Поскольку я гуглил, как работают PRNG, и на некоторых сайтах они сказали, что есть математический алгоритм, и предопределенная серия чисел и начальное число просто устанавливают указатель на другую точку в серии, и через некоторые интервалы последовательность повторяется.
Мой алгоритм только начинает перемещаться туда-сюда в массиве возможных значений, и начальное число разрывает цикл с разными значениями каждый раз. Я не считаю этот подход неправильным. Я получил ответы, предлагающие другой алгоритм, но они не объяснили Что не так с моим текущим алгоритмом?
Да, была проблема с моим семенем, поскольку оно не было точным и сделало результаты мало предсказуемыми, как здесь: —
соиЬ<
<
р-н (50100);
Результаты в беге четыре раза — 74,93,56,79.
Смотрите шаблон «увеличения порядка».
И для больших диапазонов можно было легко увидеть шаблоны. Я получил ответ о получении хороших семян, но он также рекомендовал новый алгоритм (но не сказал почему?).
Альтернативный способ может состоять в том, чтобы каждый раз случайным образом перемешивать мой массив, генерируя новую последовательность. И шаблон возрастающего порядка сработает. Любая помощь с этой перестановкой также будет хорошей. Вот код ниже. И если моя функция не Возможно, пожалуйста, сообщите мне.
Благодарим вас заранее.
int rn(int lowerlt, int upperlt)
{
/* Over short ranges, results are satisfactory.
* I want to make it effective for big ranges.
*/
const int size = upperlt - lowerlt; // Constant size of the integer array.
int ar[size]; // Array to store all possible values within defined range.
int i, x, ret; // Variables to control loops and return value.
long pointer = 0; //pointer variable. The one which breaks the main loop.// Loop to initialize the array with possible values..
for (i=0, x=lowerlt; x <= upperlt; i++, x++)
ar[i]=x;
long seed = time(0);
//Main loop . To find the random number.
for (i=0; pointer <= seed; i++, pointer++)
{
ret = ar[i];
if (i == size-1)
{
// Reverse loop.
for (; i >= 0; i--)
{
ret=ar[i];
}
}
}
return ret;
}
Решение
Предостережение: Из вашего поста, помимо вашего алгоритма случайного генератора, одной из ваших проблем является получение хорошего начального значения, поэтому я рассмотрю эту часть.
Вы могли бы использовать /dev/random чтобы получить начальное значение. Это было бы отличным местом для начала [и было бы достаточно само по себе], но с некоторой точки зрения его можно считать «обманом».
Итак, вот некоторые другие источники «энтропии»:
Используйте источник с более высоким разрешением времени суток: gettimeofday или же clock_gettime(CLOCK_REALTIME,...) назовите это «cur_time». Используйте только микросекундную или наносекундную часть соответственно, назовите ее «cur_nano». Обратите внимание, что cur_nano обычно довольно случайный.
Сделать getpid(2), У этого есть несколько непредсказуемых битов, потому что между вызовами запускаются другие программы, и мы не знаем, сколько.
Создайте новый временный файл и получите номер инода файла [затем удалите его]. Это меняется медленно с течением времени. Может быть одинаковым при каждом вызове [или нет]
Получите значение высокого разрешения для часового времени системы, когда система загружалась, назовите его «sysboot».
Получите значение высокого разрешения для времени начала вашей «сессии». Когда родительская оболочка вашей программы была запущена, назовите ее «shell_start».
Если бы вы использовали Linux, вы могли бы вычислить контрольную сумму /proc/interrupts как это всегда меняется. Для других систем получите некоторый хеш числа прерываний различных типов [должен быть доступен из некоторого типа системного вызова].
Теперь создайте некоторый хэш всего вышеперечисленного (например,):
dev_random * cur_nano * (cur_time - sysboot) * (cur_time - shell_start) *
getpid * inode_number * interrupt_count
Это простое уравнение. Вы могли бы улучшить это с некоторыми XOR и / или sum операции. Экспериментируйте, пока не получите тот, который работает на вас.
Примечание: это только дает вам начальное значение для вашего PRNG. Вам нужно будет создать свой PRNG из чего-то другого (например, линейный алгоритм Эрла)
Другие решения
unsigned int Random::next() {
s = (1664525 * s + 1013904223);
return s;
}
‘s’ растет с каждым вызовом этой функции.
Правильный
unsigned int Random::next() {
s = (1664525 * s + 1013904223) % xxxxxx;
return s;
}
Может быть, использовать эту функцию
long long Factor = 279470273LL, Divisor = 4294967291LL;
long long seed;
next()
{
seed = (seed * Factor) % Divisor;
}