Quel meilleur problème pour PCG.SE que d'implémenter PCG, un meilleur générateur de nombres aléatoires ? Ce nouvel article prétend présenter un générateur de nombres aléatoires rapide, difficile à prévoir, petit et statistiquement optimal.
Son implémentation minimale en C est d'environ neuf lignes:
// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)
typedef struct { uint64_t state; uint64_t inc; } pcg32_random_t;
uint32_t pcg32_random_r(pcg32_random_t* rng)
{
uint64_t oldstate = rng->state;
// Advance internal state
rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
// Calculate output function (XSH RR), uses old state for max ILP
uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
uint32_t rot = oldstate >> 59u;
return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}
(sur: http://www.pcg-random.org/download.html )
La question est: pouvez-vous faire mieux?
Règles
Écrivez un programme ou définissez une fonction qui implémente PCG sur des entiers non signés 32 bits. C'est assez large: vous pouvez imprimer une séquence infinie, définir une pcg32_random_rfonction et une structure correspondante, etc.
Vous devez être en mesure d'amorcer votre générateur de nombres aléatoires de manière équivalente à la fonction C suivante:
// pcg32_srandom(initstate, initseq)
// pcg32_srandom_r(rng, initstate, initseq):
// Seed the rng. Specified in two parts, state initializer and a
// sequence selection constant (a.k.a. stream id)
void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq)
{
rng->state = 0U;
rng->inc = (initseq << 1u) | 1u;
pcg32_random_r(rng);
rng->state += initstate;
pcg32_random_r(rng);
}
( à partir de : pcg_basic.c:37)
Appeler le générateur de nombres aléatoires sans l'amorcer au préalable est un comportement indéfini.
Pour vérifier facilement votre soumission, assurez-vous que, une fois amorcé avec initstate = 42et initseq = 52, le résultat est 2380307335:
$ tail -n 8 pcg.c
int main()
{
pcg32_random_t pcg;
pcg32_srandom_r(&pcg, 42u, 52u);
printf("%u\n", pcg32_random_r(&pcg));
return 0;
}
$ gcc pcg.c
$ ./a.out
2380307335
Notation
Score standard. Mesuré en octets. Le plus bas est le meilleur. En cas d'égalité, la soumission antérieure l'emporte. Les failles standard s'appliquent.
Exemple de solution
Compile sous gcc -W -Wallproprement (version 4.8.2).
Comparez votre soumission à celle-ci pour vous assurer d'obtenir la même séquence.
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
typedef struct { uint64_t state; uint64_t inc; } pcg32_random_t;
uint32_t pcg32_random_r(pcg32_random_t* rng)
{
uint64_t oldstate = rng->state;
// Advance internal state
rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
// Calculate output function (XSH RR), uses old state for max ILP
uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
uint32_t rot = oldstate >> 59u;
return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}
void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq)
{
rng->state = 0U;
rng->inc = (initseq << 1u) | 1u;
pcg32_random_r(rng);
rng->state += initstate;
pcg32_random_r(rng);
}
int main()
{
size_t i;
pcg32_random_t pcg;
pcg32_srandom_r(&pcg, 42u, 52u);
for (i = 0; i < 16; i++)
{
printf("%u\n", pcg32_random_r(&pcg));
}
return 0;
}
Séquence:
2380307335
948027835
187788573
3952545547
2315139320
3279422313
2401519167
2248674523
3148099331
3383824018
2720691756
2668542805
2457340157
3945009091
1614694131
4292140870
Réponses:
CJAM,
1091071049891 octetsCela utilise certains caractères en dehors de la plage ASCII, mais ils sont tous en ASCII étendu, donc je compte chaque caractère comme un octet (au lieu de compter comme UTF-8).
Il s'agit essentiellement d'un port exact du code C.
La fonction de départ est un bloc stocké dans
S, et la fonction aléatoire est un bloc stocké dansR.Sattendinitstateetinitseqsur la pile et ensemencer le PRNG.Rn'attend rien sur la pile et laisse le prochain nombre aléatoire dessus.Étant donné qu'appeler
Ravant d'appelerSest un comportement indéfini, je définis en fait à l'RintérieurS, donc jusqu'à ce que vous utilisiez le bloc de départ,Rc'est juste une chaîne vide et inutile.Le
stateest stocké dans une variableAet leincest stocké dansB.Explication:
Et voici l'équivalent du harnais de test dans l'OP:
qui imprime exactement les mêmes nombres.
Testez-le ici. Stack Exchange supprime les deux caractères non imprimables, donc cela ne fonctionnera pas si vous copiez l'extrait ci-dessus. Copiez plutôt le code du compteur de caractères .
la source
C, 195
J'ai pensé que quelqu'un devrait publier une implémentation C plus compacte, même si elle n'a aucune chance de gagner. La troisième ligne contient deux fonctions:
r()(équivalent àpcg32_random_r()) ets()(équivalent àpcg32_srandom_r()). La dernière ligne est lamain()fonction, qui est exclue du nombre de caractères.Bien que le compilateur se plaindra, cela devrait fonctionner correctement sur une machine 64 bits. Sur une machine 32 bits , vous devrez ajouter 5 autres octets au changement
#define L longà#define L long long( comme dans cette démo ideone ).la source
srandomfonction fait partie de votre soumission et devrait être incluse dans le nombre de caractères. (Après tout, vous pourriez peut-être penser à un moyen intelligent d'optimiser cela.) Cela porterait votre score actuel à 197, d'après mon compte.Julia,
218199191 octetsRenommer les types de données et quelques autres petites astuces m'a aidé à réduire la longueur de 19 octets supplémentaires. Principalement en omettant deux affectations de type :: Int64 .
Explication des noms (avec les noms correspondants dans la version non golfée ci-dessous):
Initialisez la graine avec l'état 42 et la séquence 52. En raison du programme plus petit, vous devez indiquer le type de données de manière explicite lors de l'initialisation maintenant (14 octets de code enregistrés environ). Vous pouvez omettre l'attribution de type explicite sur les systèmes 64 bits:
Produisez le premier ensemble de nombres aléatoires:
Résultat:
J'ai été vraiment surpris que même ma version Julia non golfée ci-dessous soit tellement plus petite (543 octets) que l'exemple de solution en C (958 octets).
Version non golfée, 543 octets
Vous initialisez la graine (état initial = 42, séquence initiale = 52) avec:
Ensuite, vous pouvez créer des nombres aléatoires avec:
Voici le résultat d'un script de test:
Comme je suis un mauvais programmeur, il m'a fallu presque un jour pour le faire fonctionner. La dernière fois que j'ai essayé de coder quelque chose en C (en fait C ++), c'était il y a presque 18 ans, mais beaucoup de google-fu m'ont finalement aidé à créer une version Julia fonctionnelle. Je dois dire que j'ai beaucoup appris en quelques jours sur codegolf. Maintenant, je peux commencer à travailler sur une version Piet. Ça va être beaucoup de travail, mais je veux vraiment, vraiment un (bon) générateur de nombres aléatoires pour Piet;)
la source