Я хотел бы создать быструю легкую функцию на языке C, которая возвращает псевдослучайный беззнаковый символ. Сложность для меня (программиста ANSI C) заключается в том, что я не могу использовать <stdio.h> или любые другие готовые функции. Какие-либо предложения..?
под «быстрым» я имел в виду: избегать ненужного кода (например, операторы if, циклы и т. д.) под «легким» я имел в виду: использовать как можно меньше переменных
Благодарность
Используйте линейный конгруэнтный генератор
E.g.
uint32_t state = 777;
char myRand()
{
state = state * 1664525 + 1013904223;
return state >> 24;
}
Обратите внимание, что myRand возвращает старшие биты, они более псевдослучайны, чем младшие биты.
Генераторы линейных сравнений были представлены Д. Х. Лемером в 1949 г. (см. Proc. 2nd Symp. on Large-Scale Digital Calculation Machinery (Cambridge, Mass.: Harvard University Press, 1951), 141-146). Конкретные числовые константы, которые я дал, по-видимому, взяты из Press, William H.; и другие. (1992). Численные рецепты на Фортране 77: Искусство научных вычислений (2-е изд.). ISBN 978-0-521-43064-7.
Из исходного кода ядра Linux (random32.c)
значения в rnd_state должны быть инициализированы следующим образом: s1 > 1, s2 > 7, s3 > 15.
В документе утверждается, что это максимально равномерно распределенный комбинированный генератор Таусворта, основанный на коде из Научной библиотеки GNU 1.5 (30 июня 2004 г.)
struct rnd_state {
u32 s1, s2, s3;
};
static u32 __random32(struct rnd_state *state)
{
#define TAUSWORTHE(s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b)
state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12);
state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4);
state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17);
return (state->s1 ^ state->s2 ^ state->s3);
}
Академия: http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
Изобретение собственного генератора случайных чисел — плохая идея того же класса, что и изобретение собственной криптографии: легко создать что-то, что кажется способным выполнять эту работу, но на самом деле катастрофически неэффективно; построить что-то, что действительно выполняет эту работу, намного сложнее. Прочтите поучительную историю о RANDU, а затем загрузите один из вариантов Mersenne Twister и используйте его.
В Википедии есть целый список генераторов псевдослучайных чисел: http://en.wikipedia.org/wiki/List_of_pseudorandom_number_generators
