Мне надо сделать генератор псевдослучайных целых чисел из диапазона [0, N], где N - очень большое число, порядка сотен и тысяч бит. Причём каждый раз при генерации очередного числа значение N может существенно меняться. Числа используются в моделировании, поэтому криптографическая стойкость не требуется. Как правильней решить эту задачу? Можно ли, например, "слеплять" большие числа из нескольких 32-битных или из их младших/старших битов?
Можно и сцеплять, хоть генерируй случайный бит, и добавляй его к итоговому. IMHO главное чтобы при этом получилась равная вероятность появления чисел, вот сишной rnd по всей видимости долеко до этого.
Quantum Есть еще по круче, не помню в какой ветке, но есть еще круче точно! Так вот если поискать по форуму можно наткнуться на исходник в котором генератор с еще большим периодом, чем ты предложил!
Вот в этом-то как раз и вопрос: а получится ли в этом случае "равная вероятность"? Quantum,EvilsInterrupt Это, конечно, хорошо, что у MT очень большой период, но на выходе он даёт всё-таки маленькие числа (32 или 53 бита). И вопрос в том, можно ли "слеплять" эти числа в одну длинную последовательность?
Artem А что если сделать так: К примеру надо 1024 бит, для нас к примеру это много. Тогда: 1. Генерим число по хорошем алгоритму ГПСЧ от заданного зерна для него. Рузультат 1е 32 битное. - Повторяя п.1 до тех пор пока все результаты не дадут нам 128 битное. 2. Полученное 128 битное пропускаем через известный алгоритм хэширования получем 512 битное 3. Повторив п.1 и п.2 получим еще один 512 битный блок 4. Еще одна конкатенация даст нам 1024 битный блок. Нюансы: - ГПСЧ должен обладать хорошим периодом - Алгоритм хэширования должен быть сильным
Artem Не можно, а нужно. Равномерность сохранится, т.к. в хорошем генераторе нет зависимости одного числа от предыдущего(их). Хороший генератор характеризуется бесконечным периодом. В данном случае период конечен, но очень велик.
Artem Вопрос ёще тот. Ведь даже NASA на этом прокололась. Запускали какой то спутник, и из-за неравномерности генератора произошла ошибка в траектории. Миллиарды баксов на ветер. Я тоже как-то вычислял Pi с помощью сишной rnd, таже история. А для твоего случая период должен быть очень большой, уж лучше наверное было-бы использовать аппаратный генератор.
Artem Есть схема, основанная на регистре сдвига (число ячеек которого > числа бит в твоих числах). Надо взять функцию обратной связи, реализующую полный цикл, а в качестве значений числа брать содержимое регистра, либо многозначную функцию от каких-то его точек. Ну и реализовать различные режимы прокрутки регистра (например, число сдвигов между генерацией чисел одинаковое или зависит от состояния регистра сдвига). Возможны различные варианты данной схемы.
Спасибо за ответы. Я, пожалуй, остановлюсь на объединении чисел, получаемых с помощью MT. Хотя буду рад, если кто-то даст ссылку на авторитетную статью по ГПСЧ, рассматриваемым в нужном мне ключе.
Можно использовать один или несколько обычных генераторов на 32бит, циклически повторяя их столько раз, сколько нужно. Разумеется, заполнение у каждого свое. Нужно сцепить их наподобие колесиков в счетчике электроэнергии, чтобы при появлении какого-нить события (ноль, единица) возникал перенос на следующее колесико. Лично я предпочитаю перенос по нечетности. Если период датчика 2^32-1, то должно сработать. Если период ровно 2^32 - то тогда можно по нулю или единице, но такой перенос будет осуществляться крайне редко, что может быть плохо.
Quantum Ссылку не знаю. По ящику слышал. Долго смеялся. Для америкосов миллиарды баксов ерунда, ещё напечатают. Может эти балбесы в расчётах rnd и использовали.
h**p://virlib.eunnet.net/books/numbers/text/0.html Источник не выглядит авторитетным, но ничего другого по теме не попадалось.
persicum Перенос можно делать каждый такт, а значение переносимого бита (байта) определять с помощью равноверятной булевской функции. Я об этом выше упоминал.
Если генератор дает серию случайных чисел за исключением нуля, то используя перенос по нечетности можно соединить несколько таких генераторов, или в крайнем случае повторить один такой генератор, чтобы период был максимально возможным. Пример. Один (младший) генератор циклически дает числа 2 1 3 5 4 А второй (старший) 5 2 1 4 3 При начальном заполнении, скажем, 1 1 и сцеплении по нечетности получим 3 3 2 5 1 4 4 2 5 1 .... и т.д. период будет 25. Так можно соединить сколько угодно колесиков и получить максимально возможный период. Для переноса N-ного колесика нужно, чтобы бит нечетности был установлен у ВСЕХ предыдущих.
Имхо всё просто - разбиваешь свой диапазон [0, N], скажем на 1000 ячеек, округляешь полученные с генератора числа до попадания в соответсвующую ячейку и кидаешь в неё +1. После прогона твоей модели выводишь этот график на экран и если при моделировании возникла существенная неравномерность, то это будет сразу заметно ЗЫ: Это не вариант генератора, а способ подстраховаться от падения спутников
Мне когда-то требовалось нечто бодобное. Тогда я заюзал microtime(). Например, на выходе имеем результат: 0.57970800 хххххххххх, берём, 57970800 и возводим в степень первой цифры(т.е. 5), получаем 654706222349629566992930887680000000000 далее обрезаем до нужного значения... далее возможны варианты. Если нужна ссылка на авторитетную статью, то в книге "Искусство программирования" есть целая глава посвященная вопросу ГСЧ.
