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

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

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

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

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

Я сделал коллекцию генераторов случайных чисел «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, который является общим периодом этого генератора.

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

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

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

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

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

• Он был разработан с периодом 2 ¹⁹⁹³⁷ - 1 (это свойство доказали создатели алгоритма). На практике нет особых причин использовать больший период, так как большинству приложений не требуется 2 ¹⁹⁹³⁷ уникальных комбинаций (2 ¹⁹⁹³⁷ примерно 4,3 × 10 ^{6001 < / sup>; это на много порядков больше, чем предполагаемое количество частиц в наблюдаемой Вселенной, которое составляет 10 80).}
• Он имеет очень высокий порядок размерного равнораспределения (см. Линейный конгруэнтный генератор). Это означает, что существует незначительная последовательная корреляция между последовательными значениями в выходной последовательности.

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

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

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

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

Я нашел это: Генерация простых случайных чисел, автор: Джон Д. Готовьте.

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

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

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

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

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

Существует один простой ГСЧ с именем 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.