Генератор простых простых случайных чисел

Question

Как создать функцию, которая на каждом вызове генерирует случайное целое число? Это число должно быть максимально вероятным (согласно uniform distribution). Это разрешено только использовать одну статическую переменную и не более 3 элементарных шагов, где каждый шаг состоит только из одной основной арифметической операции arity 1 или 2.

Пример:

int myrandom(void){ 
    static int x; 
    x = some_step1; 
    x = some_step2; 
    x = some_step3; 
    return x; 
} 

Основные арифметические операции + , -,%, и не, xor, или, сдвиг влево, сдвиг вправо, умножение и деление. Конечно, никаких рандов(), random() или подобных материалов не допускается.

Answer 1

линейного конгруэнтного генератора является одним из старейших и простейших метода:

int seed = 123456789; 

int rand() 
{ 
    seed = (a * seed + c) % m; 
    return seed; 
} 

Ony несколько инструкций с основными арифметическими операциями, это то, что вам нужно.

ум, что этот алгоритм работает отлично только если a, c и m выбираются особым образом!

Для того, чтобы гарантировать максимально возможный период этой последовательности с и м должны быть взаимно просты, а-1 должно быть делится на все простые множители м, а также для 4, если м является делится на 4.

некоторые примеры значений приведены в Wikipedia: например, ANSI C для некоторых составителей предлагает m = 2^32, a = 1103515245 и c = 12345

Answer 2

Возможно, вы найдете this. Это далеко не идеальный генератор случайных чисел, но он действительно соответствует вашим требованиям, насколько я могу видеть.

Here вы можете найти дополнительную информацию о генерации случайных чисел.

Answer 3

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

Answer 4

Вот функция равномерного распределения по всему диапазону междунар:

int rand() 
{ 
    static int random = 0; 
    return random++; 
} 

Answer 5

Если я пишу man rand, я могу прочитать возможный пример, приведены в POSIX.1-2001, для реализации RAND() и srand(). См. here. Если вам нужно что-то более сложное, взгляните на GNU Scientific Library; вы можете, конечно, загрузить код и увидеть реализацию (и).

Answer 6

Я использую это

SUBROUTINE GNA(iiseed) 
    USE Variaveis 
    parameter (ia=843314861,ib=453816693,m=1073741824, r231=1./2147483648.) 
    INTEGER :: iiseed 

    iiseed = ib + ia*iiseed 
    if (iiseed.lt.0) iiseed = (iiseed+m) + m 
    RndNum = iiseed*r231 

END SUBROUTINE GNA 

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

Это очень хороший трюк!

Answer 7

public long randomLong() { 
    x ^= (x << 21); 
    x ^= (x >>> 35); 
    x ^= (x << 4); 
    return x; 
} 

Семя не может быть 0. Источник: http://www.javamex.com/tutorials/random_numbers/xorshift.shtml#.VlcaYzKwEV8

Дополнительная информация в вики: https://en.wikipedia.org/wiki/Xorshift