генерировать любое случайное целое число
Заранее прошу прощения, так как я не очень разбираюсь в формальных представлениях о случайности.
Заголовок говорит большую часть этого: я хочу сгенерировать случайное целое число за разумное время, где может появляться каждое целое число, независимо от того, с одинаковой частотой или нет, не важно. В качестве дополнения, компьютерная память не является проблемой, поскольку даже с бесконечным пространством памяти для хранения этих сгенерированных чисел не очевидно, как это можно сделать. Я не добился никакого прогресса в поиске правильного алгоритма, но вот мои наблюдения.
Если вы можете случайным образом сгенерировать любое действительное число, вы можете использовать такие функции, как функция пола, для генерации любого целого числа. Если бы вы могли случайным образом сгенерировать любое действительное число между любым интервалом$[a,b]$, то вы можете использовать асимптотические функции, такие как $\tan$ для генерации любого действительного числа.
В общем, если у меня есть набор S, который имеет большую или равную мощность целым числам, и я могу случайным образом сгенерировать элемент внутри S, то я могу случайным образом сгенерировать любое целое число, сопоставив элементы S с целыми числами.
Я знаю, что есть последовательности, такие как последовательность простых пробелов, которые случайны и содержат сколь угодно большие целые числа, но их нелегко вычислить.
Однако это все, о чем я могу думать. Я бы не удивился, если бы не было простого решения проблемы, но если у кого-то есть причина, почему это невозможно, я бы тоже хотел услышать.
Ответы
Произвольный размер не имеет значения, поскольку вычисление не может остановиться!
Представьте, что вы подбрасываете монету за каждый бит случайного целого числа, тогда вы можете увидеть, что подбрасывание монеты бесконечное.
При игре с произвольным размером нужно быть осторожным. Математически вы можете сказать, что пусть$x$ быть случайным целым числом, т.е. $x \stackrel{R}{\leftarrow} \mathbb Z$однако, когда вы попытаетесь найти значение этого, вы столкнетесь с его порождением. Если вам нужно равномерное случайное целое число, очевидно, что это не удастся!
Теперь предположим, что у вас есть ограничение вроде $0\color{red}{<} x \leq 2^L$тогда вы можете использовать LFSR для генерации случайных чисел в диапазоне. Если LFSR с размером$L$ максимален, то периодичен и имеет период $2^L-1$. В этот период он посещает все возможные$L$-битовые числа, за исключением состояния "все нули". Вы можете получить семя со времени и начать его использовать.
Обратите внимание, что LFSR далек от того, чтобы быть криптографически безопасным генератором случайных псевдогенераторов (CSPRNG). Имея только$2L$ битового вывода из LFSR достаточно для определения следующих битов из-за алгоритма Берлакэмпа-Массая - и фактически, исключения Гаусса достаточно, однако BM намного быстрее -.