Простой псевдослучайный алгоритм

Мне нужен псевдослучайный генератор, который принимает число в качестве входных данных и возвращает другое число, которое воспроизводимо и кажется случайным.

  • Каждый входной номер должен соответствовать ровно одному выходному номеру и наоборот
  • одинаковые входные номера всегда приводят к одинаковым выходным номерам
  • последовательные входные числа, которые расположены близко друг к другу (например, 1 и 2), должны давать совершенно разные выходные номера (например, 1 => 9783526, 2 => 283)

Это не должно быть идеально, это просто для создания случайных, но воспроизводимых тестовых данных.

Я использую C #.


Я написал этот забавный кусок кода некоторое время назад, который произвел что-то случайное.

  public static long Scramble(long number, long max) 
  {
    // some random values 
    long[] scramblers = { 3, 5, 7, 31, 343, 2348, 89897 };
    number += (max / 7) + 6;
    number %= max;
    // shuffle according to divisibility
    foreach (long scrambler in scramblers) 
    {
      if (scrambler >= max / 3) break;
      number = ((number * scrambler) % max) 
        + ((number * scrambler) / max);
    }

    return number % max;
  }

Я хотел бы иметь что-то лучше, надежнее, работающее с любым размером числа (без аргументов max).

Возможно ли это решить с помощью алгоритма CRC? Или что-то вроде тасования.

8.10.2009 13:50:08
Это похоже на обман этого SO поста - псевдослучайного генератора с тем же выходом .
48klocs 8.10.2009 13:55:45
sbi 8.10.2009 13:58:53
@sbi: не уверен, что это точный дубликат, учитывая требование исключительного соответствия между входом и выходом. Смотрите tanasciusкомментарий к моему ответу ниже.
MusiGenesis 8.10.2009 14:02:30
Из принятого ответа на вопрос, который я связал с: «В функциях PRNG вывод функции зависит от значения« seed », так что такой же вывод будет получен при последовательных вызовах при одинаковом значении seed». Так уже там объяснено. Вот почему это дубликат.
sbi 8.10.2009 14:18:52
@phoku: может быть, глупый вопрос, но ... КАК я хэш семя?
Stefan Steinegger 8.10.2009 14:31:43
4 ОТВЕТА
РЕШЕНИЕ

Вы (возможно) можете легко сделать это в C #, используя класс Random:

public int GetPseudoRandomNumber(int input)
{
    Random random = new Random(input);
    return random.Next();
}

Поскольку вы явно заполняете значение Random входными данными, вы будете получать один и тот же вывод каждый раз при задании одного и того же входного значения.

3
8.10.2009 14:00:22
Но его первое требование - «Каждое входное число должно соответствовать ровно одному выходному номеру и наоборот» - и наоборот, не будет работать с вашим решением.
tanascius 8.10.2009 13:57:04
@tanascius: на самом деле, я не уверен, что это не будет соответствовать этому требованию, но я не знаю, как работает Random под капотом, так что вы можете быть правы.
MusiGenesis 8.10.2009 13:59:58
Ну, я проверил на входах от 1 до 10 млн. ... вы никогда не получите один и тот же выход дважды ... так что это может действительно работать. Но это все еще зависит от реализации и может измениться в будущем.
tanascius 8.10.2009 14:08:54
Я должен признать, что часть «совпадение - и наоборот» не является слишком строгим требованием, поскольку мне не нужны все числа входного значения. Он просто не должен производить одни и те же числа снова и снова, и при этом никогда не производить других.
Stefan Steinegger 8.10.2009 14:10:29
@tanascius: быстрый тест, спасибо. Я подозреваю, что MS вряд ли изменит реализацию в ближайшее время. В конце концов, «случайность слишком важна, чтобы оставлять ее на волю случая». :)
MusiGenesis 8.10.2009 14:11:28

Я удаляю код Microsoft из этого ответа, файл кода GNU намного длиннее, но в основном он содержит его из http://cs.uccs.edu/~cs591/bufferOverflow/glibc-2.2.4/stdlib/random_r.c :

int32_t val = state[0];
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
state[0] = val;
*result = val;

для вашей цели семя - это состояние [0], поэтому оно будет выглядеть как

int getRand(int val)
{
    return ((val * 1103515245) + 12345) & 0x7fffffff;
}
4
8.10.2009 15:20:38
Хм, это уведомление об авторском праве вонзается мне в глаза. Как вы думаете, вы можете просто вставить этот код здесь?
sbi 8.10.2009 14:15:49
Ну, я не юрист, но это всего лишь фрагмент из файла, а также авторское право 1985 - 2001 (сейчас 2009). Он также доступен онлайн в других местах, и я оставил текст об авторских правах в файле. Если у кого-то есть проблема с этим, я могу удалить ответ и заменить его на GNU.
John Boker 8.10.2009 15:11:52
@MusiGenesis как Стив Балмер, я могу просто отправить вам все мои проблемы с окнами, и вы их исправите?
John Boker 8.10.2009 19:19:25
@Джон: да, после того, как я тебя раздавлю, как виноград! Bwahahahaha!
MusiGenesis 8.10.2009 19:56:42

Первые два правила предполагают фиксированную или посеянную входную перестановку ввода, но третье правило требует дальнейшего преобразования.

Существуют ли какие-либо дополнительные ограничения на то, какими должны быть выходные данные, чтобы управлять этим преобразованием? Например, есть ли входной набор выходных значений на выбор?

Если единственное руководство - "нет макс", я бы использовал следующее ...

  1. Примените алгоритм хеширования ко всему входу, чтобы получить первый элемент вывода. CRC может работать, но для более «случайных» результатов используйте алгоритм криптохеша, такой как MD5.

  2. Используйте следующий алгоритм перестановки (множество ссылок в Google) на входе.

  3. Повторите hash-then-next-permutation до тех пор, пока не будут найдены все необходимые выходные данные.

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

Для хеширования в крипто-стиле вам понадобится ключ - просто извлеките что-то из ввода перед началом.

1
8.10.2009 14:39:19

Генератор таусворт прост в реализации и довольно быстр. Следующая реализация псевдокода имеет полный цикл (2 ** 31 - 1, потому что ноль является фиксированной точкой):

def tausworthe(seed)
  seed ^= seed >> 13
  seed ^= seed << 18
  return seed & 0x7fffffff

Я не знаю C #, но я предполагаю, что в нем есть операторы XOR ( ^) и bit shift ( <<, >>), как в C.

Установите начальное начальное значение и вызовите с помощью seed = tausworthe(seed).

2
26.05.2014 17:42:25
Это удивительно простое решение и работает очень хорошо. Но чтобы избежать нулевой фиксированной точки (нулевой начальный всегда приведет к нулю), вы можете добавить первую строку, которая делает XOR с фиксированным числом, например: seed ^ = 0x60d6c57.
bitagoras 7.11.2019 16:01:22