C Génération de nombres aléatoires (code C pur, pas de bibliothèques ou de fonctions)

StackOverflow https://stackoverflow.com/questions/9492581

  •  14-11-2019
  •  | 
  •  

Question

J'ai besoin de générer des nombres aléatoires en C pour tester et déboguer le système. Le système est un matériel personnalisé (SOC) avec un ensemble limité de fonctions afin que je ne puisse utiliser que des opérations mathématiques de base.

Et non, je ne peux pas utiliser des générateurs de nombres aléatoires dans STDLIB ou MATH.H. J'ai besoin de l'écrire moi-même. Y a-t-il donc une sorte d'algorithme pour générer des nombres aléatoires?

Je sais qu'une solution simple consiste à générer les chiffres ici sur mon poste de travail et à les intégrer dans le module, mais je ne veux pas le faire.

Était-ce utile?

La solution

Un générateur de nombres aléatoires est essentiellement un spécial* Fonction de hachage qui s'étend récursivement à partir d'une graine de départ.

J'ai utilisé le Algorithme Murmurhash2 dans mon code C # à bon escient. Il est extrêmement rapide et simple à mettre en œuvre et a été testé pour être très bien distribué avec de faibles taux de collision. Le projet a plusieurs fonctions de hachage open source différentes écrites en C ++ qui devraient être facilement convertibles en C.

* Par spécial, je veux dire que l'exécution de la fonction de hachage sur une valeur doit renvoyer une autre valeur apparemment aléatoire (mais déterminée), de sorte que la sortie ne semble pas former des modèles. De plus, la distribution de la valeur retournée devrait avoir une distribution uniforme.

Autres conseils

Il suffit de déterrer l'article par Park et Miller dans le numéro d'octobre 88 de CACM.

L'algorithme général qu'ils proposent est:

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

Bien que l'article comprenne plusieurs raffinements.

UN générateur congruentiel linéaire serait simple à mettre en œuvre. Une belle implémentation dans Pure C est disponible ici.

Tu peux essayer Se multiplier par George Marsaglia.

Code de Wikipedia:

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

Vérifiez le code source du bibliothèque GSL, quelques algorithmes bien testés y sont implémentés.

Vous voudrez peut-être chercher Mersenne Twister. Il existe de nombreux algorithmes de meilleure qualité. Un bon article avec un aperçu que vous trouvez ici:

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

Tu pourrais essayer Isaac qui est également disponible dans le CCAN ici

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top