Простой псевдослучайный алгоритм - PullRequest
Новая
       16

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

5 голосов
/ 08 октября 2009

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

  • Каждый входной номер должен соответствовать ровно одному выходному номеру, и наоборот
  • одинаковые входные номера всегда приводят к одинаковым выходным номерам
  • номера последовательных входов, которые расположены близко друг к другу (например, 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? Или что-то вроде тасования.

Ответы [ 4 ]

4 голосов
/ 08 октября 2009

Я удаляю код 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;
}
3 голосов
/ 08 октября 2009

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

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

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

1 голос
/ 26 мая 2014

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

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

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

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

1 голос
/ 08 октября 2009

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

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

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

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

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

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

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

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

...