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

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

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

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


c random system-on-chip
person Tring    schedule 29.02.2012    source источник

Ответы (7)


arrow_upward
5
arrow_downward

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

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

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

person dlras2    schedule 29.02.2012
comment
.. было проверено на криптологическую надежность. Точно нет! MurmurHash — это относительно новый алгоритм хэширования, который имеет множество недостатков и множество настроек — хороший признак того, что алгоритм слаб. Конечно, вы можете использовать его для генерации псевдослучайных чисел, но никто не должен использовать его для криптографических операций. - person adelphus; 29.02.2012
comment
@adelphus - я не эксперт в криптографии, поэтому я удалю это утверждение, но я думал, что криптологически обоснованное просто означает хорошее распределение, низкий уровень коллизий и низкое смещение. @ Питер О. — Хороший улов: я действительно имел в виду униформу. Упс. - person dlras2; 29.02.2012

arrow_upward
6
arrow_downward

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

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

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

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

person Hot Licks    schedule 29.02.2012
comment
Я предполагаю, что последнее деление должно использовать число с плавающей запятой, иначе random всегда равно нулю. - person Axel Bregnsbo; 04.06.2021

arrow_upward
4
arrow_downward

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

person dan04    schedule 29.02.2012

arrow_upward
0
arrow_downward

Вы можете попробовать 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);
}
person daijo    schedule 29.02.2012

arrow_upward
0
arrow_downward

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

person Bort    schedule 29.02.2012

arrow_upward
0
arrow_downward

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

http://en.wikipedia.org/wiki/Генератор_псевдорандомных_чисел

person Community    schedule 29.02.2012

arrow_upward
0
arrow_downward

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

person Spudd86    schedule 29.02.2012