Реализация rand()

Question

Я пишу некоторый встроенный код на C и мне нужно использовать функцию rand(). К сожалению, rand() не поддерживается в библиотеке для контроллера. Мне нужна простая реализация, которая быстра, но, что еще важнее, не требует много места и дает случайные числа относительно высокого качества. Кто-нибудь знает, какой алгоритм использовать или пример кода?

РЕДАКТИРОВАТЬ: Это для обработки изображений, так что "относительно высокое качество" означает приличную длину цикла и хорошие однородные свойства.

Answer 1

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

Генераторы Marsaglia определенно "высокого качества" по вашим меркам длительного периода и хорошего равномерного распределения. Они проходят строгие статистические тесты, но не подходят для криптографии.

Answer 2

Используйте код C для LFSR113 от L'écuyer:

unsigned int lfsr113_Bits (void)
{
   static unsigned int z1 = 12345, z2 = 12345, z3 = 12345, z4 = 12345;
   unsigned int b;
   b  = ((z1 << 6) ^ z1) >> 13;
   z1 = ((z1 & 4294967294U) << 18) ^ b;
   b  = ((z2 << 2) ^ z2) >> 27; 
   z2 = ((z2 & 4294967288U) << 2) ^ b;
   b  = ((z3 << 13) ^ z3) >> 21;
   z3 = ((z3 & 4294967280U) << 7) ^ b;
   b  = ((z4 << 3) ^ z4) >> 12;
   z4 = ((z4 & 4294967168U) << 13) ^ b;
   return (z1 ^ z2 ^ z3 ^ z4);
}

Очень качественно и быстро. НЕ используйте rand() ни для чего. Это хуже, чем бесполезно.

Answer 3

Вот ссылка на реализацию ANSI C нескольких генераторов случайных чисел.

Answer 4

Я сделал коллекцию генераторов случайных чисел " simplerandom", которые компактны и подходят для встроенных систем. Коллекция доступна в C и Python.

Я искал кучу простых и приличных, которые смог найти, и собрал их в небольшой пакет. Они включают в себя несколько генераторов Marsaglia (KISS, MWC, SHR3) и пару генераторов L'Ecuyer LFSR.

Все генераторы возвращают 32-разрядное целое число без знака и обычно имеют состояние от 1 до 4 32-разрядных целых чисел без знака.

Интересно, что я обнаружил несколько проблем с генераторами Marsaglia, и я попытался исправить / улучшить все эти проблемы. Эти вопросы были:

• Генератор SHR3 (компонент генератора KISS Марсальи 1999 года) был сломан.
• Младшие 16 битов MWC имеют период приблизительно 2^29,1. Таким образом, я сделал немного улучшенный MWC, который дает младшим 16 битам период 2^59,3, который является общим периодом этого генератора.

Я обнаружил несколько проблем с заполнением и попытался создать надежные процедуры заполнения (инициализации), чтобы они не сломались, если вы дадите им "плохое" начальное значение.

Answer 5

Мерсенн твистер

Немного из Википедии:

• Он был разработан, чтобы иметь период 2¹⁹⁹³⁷ - 1 (создатели алгоритма доказали это свойство). На практике нет особых причин использовать больший период, поскольку для большинства приложений не требуется 2¹⁹⁹³⁷ уникальных комбинаций (2¹⁹⁹³⁷ - это приблизительно 4,3 × 10⁶⁰⁰¹; это на много порядков больше, чем предполагаемое количество частиц в наблюдаемой вселенной, что составляет 10⁸⁰).
• Он имеет очень высокий порядок равномерного распределения (см. Линейный конгруэнтный генератор). Это подразумевает, что между последовательными значениями в выходной последовательности существует незначительная последовательная корреляция.

• Он проходит многочисленные тесты на статистическую случайность, включая тесты Диарда. Он проходит большинство, но не все, еще более строгих тестов случайности TestU01 Crush.

• Исходный код для многих языков доступен по ссылке.

Answer 6

Я рекомендую академическую статью " Две быстрые реализации генератора минимальных стандартных случайных чисел " Дэвида Карта. Вы можете найти бесплатный PDF через Google. Также стоит прочитать оригинальную статью о минимальном стандартном генераторе случайных чисел.

Код Carta дает быстрые, высококачественные случайные числа на 32-битных машинах. Для более тщательной оценки см. Статью.

Answer 7

Я нашел это: Простая генерация случайных чисел, Джон Д. Кук.

Это должно быть легко адаптироваться к C, учитывая, что это всего лишь несколько строк кода.

Изменить: и вы могли бы уточнить, что вы подразумеваете под "относительно высокого качества". Вы генерируете ключи шифрования для ядерных кодов запуска или случайные числа для игры в покер?

Answer 8

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

При условии, что sizeof(unsigned) == 4:

unsigned t1 = 0, t2 = 0;

unsigned random()
{
    unsigned b;

    b = t1 ^ (t1 >> 2) ^ (t1 >> 6) ^ (t1 >> 7);
    t1 = (t1 >> 1) | (~b << 31);

    b = (t2 << 1) ^ (t2 << 2) ^ (t1 << 3) ^ (t2 << 4);
    t2 = (t2 << 1) | (~b >> 31);

    return t1 ^ t2;
}

Answer 9

Я бы взял один из библиотеки GNU C, источник доступен для просмотра в Интернете.

http://qa.coreboot.org/docs/libpayload/rand_8c-source.html

Но если у вас есть какие-либо сомнения по поводу качества случайных чисел, вам, вероятно, стоит взглянуть на более тщательно написанные математические библиотеки. Это большой предмет и стандарт rand реализации не очень высоко оценены экспертами.

Вот еще одна возможность: http://www.boost.org/doc/libs/1_39_0/libs/random/index.html

(Если вы обнаружите, что у вас слишком много вариантов, вы всегда можете выбрать один наугад.)

Answer 10

Существует один простой RNG с именем KISS, это один генератор случайных чисел по трем числам.

/* Implementation of a 32-bit KISS generator which uses no multiply instructions */ 

static unsigned int x=123456789,y=234567891,z=345678912,w=456789123,c=0; 

unsigned int JKISS32() { 
    int t; 

    y ^= (y<<5); y ^= (y>>7); y ^= (y<<22); 

    t = z+w+c; z = w; c = t < 0; w = t&2147483647; 

    x += 1411392427; 

    return x + y + w; 
}

Также есть один веб-сайт для тестирования ГСЧ http://www.phy.duke.edu/~rgb/General/dieharder.php

Answer 11

Стандартное решение - использовать сдвиговый регистр с линейной обратной связью.