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

Je dois 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, de sorte que je ne peux utiliser que des opérations mathématiques de base.

Et non, je ne peux pas utiliser de 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 une sorte d’algorithme pour générer des nombres aléatoires?

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

Un générateur de nombres aléatoires est fondamentalement une fonction spéciale * de hachage qui s’exécute de manière récursive à partir d’une graine de départ.

J’ai utilisé à bon escient l’algorithme MurmurHash2 dans mon code C #. Extrêmement simple et rapide à mettre en œuvre, il a été testé pour être très bien dissortingbué avec un faible taux de collision. Le projet a plusieurs fonctions de hachage open source é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 de modèle. En outre, la dissortingbution de la valeur renvoyée doit avoir une dissortingbution uniforme.

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

Détachez simplement l’article de Park et Miller dans le numéro d’octobre 88 du CACM.

L’algorithme général proposé est le suivant:

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

Bien que l’article comporte plusieurs améliorations.

Vous pouvez essayer Multiply-with-carry de George Marsaglia.

Code de Wikipedia:

 #include  #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 de la bibliothèque gsl , quelques algorithmes bien testés y sont implémentés.

Vous voudrez peut-être chercher Mersenne Twister. Il y a beaucoup d’algorithmes de qualité supérieure. Un bon article avec un aperçu que vous trouverez ici:

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

Vous pouvez essayer Isaac qui est également disponible dans CCAN ici