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

Question

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

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

Answer 1

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

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

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

Answer 2

я удалить майкрософт код из этого ответа, файл кода 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; 
} 

Answer 3

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

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

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

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

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

3. Повторяйте хеш-затем-следующую-перестановку до тех пор, пока не будут найдены все требуемые выходы.

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

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

Answer 4

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

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

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

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