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

Question

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

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

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

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

5

c random system-on-chip

Источник

user416044 29 фев '12 в 02:02

7 ответов

Решение

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

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

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

Хотя статья включает в себя несколько уточнений.

8

Источник

user581994 29 фев '12 в 02:18

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

4

Источник

user287586 29 фев '12 в 02:13

Вы можете попробовать Multiply-with-carry от Джорджа Марсалья.

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

#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);
}

1

Источник

user473719 29 фев '12 в 02:11

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

0

Источник

user1038318 29 фев '12 в 10:37

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

0

Источник

user150577 29 фев '12 в 20:39

Вы можете искать Mersenne Twister. Есть много алгоритмов более высокого качества. Хорошая статья с обзором вы найдете здесь:

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

0

Источник

29 фев '12 в 10:41

Другие вопросы по тегам c random system-on-chip

user343238 29 фев '12 в 02:08 2012-02-29 02:08 · Accepted Answer · 2012-02-29 02:08

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

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

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