Простая функция для генерации последовательности случайных чисел, не зная предыдущего числа, но знает текущий индекс (без присвоения переменной)?

Question

Существует ли какая-либо (простая) функция генерации случайных чисел, которая может работать без назначения переменных?Большинство функций, которые я читаю, выглядят так: current = next(current).Однако в настоящее время у меня есть ограничение (из SQLite), что я вообще не могу использовать никакие переменные.

Есть ли способ генерировать числовую последовательность (например, от 1 до max) только с n(текущий порядковый номер в последовательности) и seed?

В настоящее время я использую это:

cast(((1103515245 * Seed * ROWID + 12345) % 2147483648) / 2147483648.0 * Max as int) + 1

с max, равным 47, ROWIDбыть n.Однако для некоторых семян частота повторения слишком высока (3 уникальных из 47).

В моих требованиях повторение в порядке, пока оно не слишком много (<50%).Есть ли лучшая функция, которая отвечает моим потребностям? </p>

Вопрос имеет тег sqlite, но любой язык / псевдокод в порядке.

Ps: я пытался использовать Линейные конгруэнтные генераторы с некоторыми а / с / м триплетами и Seed * ROWID как Seed, но это не работает хорошо, это даже хуже.

РЕДАКТИРОВАТЬ: Я в настоящее время использую этот, но я не знаю, гдеэто из.Курс выглядит лучше моего:

((((Seed * ROWID) % 79) * 53) % "Max") + 1

Answer 1

Как насчет использования хорошей хеш-функции и результата отображения в диапазон [1 ... max]?

Вдоль линий (в псевдокоде).sha1 был добавлен в SQLite 3.17.

sha1(ROWID) % Max + 1

Или используйте любой внешний C-код для хэша (ропот, chacha, ...), как показано здесь

Answer 2

A линейный конгруэнтный генератор с соответствующим образом выбранными параметрами ( a , c и модулем m ) будет генератором полного периода , так что он будет циклически псевдослучайно проходить через каждое целое число в своем периоде перед повторением.Хотя вы, возможно, пробовали эту идею раньше, считали ли вы, что m эквивалентно max в вашем случае?Список выбора параметров для таких генераторов см. В L'Ecuyer, P. "Таблицы линейных конгруэнтных генераторов разных размеров и хорошей структуры решетки", Математика вычислений 68 (225), январь 1999 г.

Обратите внимание, что существуют некоторые практические проблемы для реализации этого в SQLite, особенно если ваша версия SQLite поддерживает только 32-разрядные целые и 64-разрядные числа с плавающей точкой (с точностью до 52 бит).А именно, может существовать риск переполнения

• , если промежуточное умножение превышает 32 бита для целых чисел, и потери точности
• , если промежуточное умножение приводит к значению, превышающему 52-битное число.

Кроме того, подумайте, почему вы создаете последовательность случайных чисел:

• Является ли последовательность непредсказуемой?В этом случае одного линейного конгруэнтного генератора недостаточно, и вы должны генерировать уникальные идентификаторы другими способами, например, путем объединения уникальных чисел с криптографически случайными числами .
• Будут ли сгенерированные числатаким образом подвергаться каким-либо образом конечным пользователям?В противном случае нет необходимости запутывать их, «перетасовывая» их.

Кроме того, в зависимости от используемого вами API-интерфейса SQLite (для вашего языка программирования), может быть способ написатьпользовательская функция для преобразования начального числа и ROWID в случайное уникальное число.Детали, однако, сильно зависят от конкретного API SQLite. Другой ответ показывает пример для Perl.