Я пишу встроенный код в C и вам нужно использовать функцию rand(). К сожалению, rand() не поддерживается в библиотеке контроллера. Мне нужна простая реализация, которая быстрая, но, что более важно, имеет небольшие накладные расходы, что создает относительно качественные случайные числа. Кто-нибудь знает, какой алгоритм использовать или пример кода?
EDIT: для обработки изображений, поэтому "относительно высокое качество" означает приемлемую длину цикла и хорошие однородные свойства.
Ознакомьтесь с этой коллекцией генераторов случайных чисел от Джорджа Марсалья. Он ведущий специалист по генерации случайных чисел, поэтому я уверен, что буду использовать все, что он рекомендует. Генераторы в этом списке крошечные, некоторые требуют только пары беззнаковых длин в качестве состояния.
Генераторы 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, и я попытался исправить/улучшить все эти проблемы. Эти проблемы были:
Я обнаружил несколько проблем с посевкой и попытался сделать надежные процедуры семян (инициализации), поэтому они не сломаются, если вы дадите им "плохое" начальное значение.
Немного из Википедии:
Проходит множество тестов для статистической случайности, включая тесты Дихарда. Он передает большинство, но не все, еще более строгие тесты случайности TestU01 Crush.
исходный код для многих языков, доступных по ссылке.
Я рекомендую академическую статью Два быстрых варианта создания генератора случайных чисел с минимальным стандартным показателем Дэвида Карты. Вы можете найти бесплатный PDF через Google. Также стоит прочитать оригинальную статью о генераторе минимальных стандартных случайных чисел.
Карточный код дает быстрые высококачественные случайные числа на 32-битных машинах. Более подробную оценку см. В документе.
Я бы взял один из библиотеки 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;
}
Стандартное решение - использовать линейный регистр сдвига .
Существует один простой 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