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

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

EDIT: для обработки изображений, поэтому "относительно высокое качество" означает приемлемую длину цикла и хорошие однородные свойства.

Ответы

Ответ 1

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

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

Ответ 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() для чего-либо. Это хуже, чем бесполезно.

Ответ 3

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

Ответ 4

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

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

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

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

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

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

Ответ 5

Mersenne twister

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

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

Ответ 6

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

Карточный код дает быстрые высококачественные случайные числа на 32-битных машинах. Более подробную оценку см. В документе.

Ответ 7

Я бы взял один из библиотеки 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

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

Ответ 8

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

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

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

Ответ 9

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

Предполагая, что 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;
}

Ответ 10

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

Ответ 11

Существует один простой 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; 
}

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