Генерация случайных чисел C (чистый код C, без библиотек и функций)

Question

Мне нужно сгенерировать несколько случайных чисел в C для тестирования и отладки системы. Система представляет собой специальное аппаратное обеспечение (SoC) с ограниченным набором функций, поэтому я могу использовать только основные математические операции.

И нет, я не могу использовать генераторы случайных чисел в stdlib или math.h. Я должен написать это сам. Так есть ли какой-нибудь алгоритм генерации случайных чисел?

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

Answer 1

Генератор случайных чисел - это, по сути, специальная хэш-функция ^*, которая рекурсивно запускается из начального начального числа.

Я использовал MurmurHash2 алгоритм в моем коде C # для хорошего эффекта. Он чрезвычайно быстр и прост в реализации и был протестирован, чтобы быть очень хорошо распределенным с низкой частотой столкновений. В проекте есть несколько различных хеш-функций с открытым исходным кодом, написанных на C ++, которые должны быть легко преобразованы в C.

---

^{* Под специальным пониманием я подразумеваю, что выполнение хэш-функции для значения должно возвращать другое, казалось бы, случайное (но определенное) значение, чтобы выходные данные не формировали шаблоны. Кроме того, распределение возвращаемого значения должно иметь равномерное распределение.}

Answer 2

A линейный конгруэнтный генератор был бы прост в реализации.Хорошая реализация в чистом C доступна здесь .

Answer 3

Просто откопайте статью Парк и Миллер в выпуске CACM за октябрь 88.

Общий алгоритм, который они предлагают:

a = 16807;
m = 2147483647;
seed = (a * seed) mod m;
random = seed / m;

Хотя статья содержит несколько уточнений.

Answer 4

Вы можете попробовать Исаака , который также доступен как часть CCAN здесь

Answer 5

Возможно, вы захотите найти Мерсенна Твистера. Есть много алгоритмов более высокого качества. Хорошую статью с обзором вы найдете здесь:

http://en.wikipedia.org/wiki/Pseudorandom_number_generator

Answer 6

Проверьте исходный код библиотеки gsl , в ней реализована пара хорошо протестированных алгоритмов.

Answer 7

Вы можете попробовать Multiply-with-carry от George Marsaglia.

Код из Википедии:

#include <stdint.h>

#define PHI 0x9e3779b9

static uint32_t Q[4096], c = 362436;

void init_rand(uint32_t x)
{
    int i;

    Q[0] = x;
    Q[1] = x + PHI;
    Q[2] = x + PHI + PHI;

    for (i = 3; i < 4096; i++)
            Q[i] = Q[i - 3] ^ Q[i - 2] ^ PHI ^ i;
}

uint32_t rand_cmwc(void)
{
    uint64_t t, a = 18782LL;
    static uint32_t i = 4095;
    uint32_t x, r = 0xfffffffe;
    i = (i + 1) & 4095;
    t = a * Q[i] + c;
    c = (t >> 32);
    x = t + c;
    if (x < c) {
            x++;
            c++;
    }
    return (Q[i] = r - x);
}