Ensemencer un générateur de nombres aléatoires en Javascript

Question

Est-il possible de générer un générateur de nombres aléatoires (Math.random) en JavaScript ?

Answer 1

Non, il n'est pas possible de semer des graines Math.random(). La spécification ECMAScript est intentionnellement vague sur le sujet, ne fournissant aucune méthode d'amorçage ou obligeant les navigateurs à utiliser le même algorithme. Cette fonctionnalité doit donc être fournie en externe, ce qui, heureusement, n'est pas trop difficile.

J'ai implémenté un certain nombre de fonctions Pseudo-Random Number Generator (PRNG) agréables, courtes et rapides en JavaScript pur. Tous ces éléments peuvent être générés et fournir des numéros de haute qualité. Ce n'est pas à des fins de sécurité - si vous avez besoin d'un CSPRNG amorçable, consultez ISAAC.

Tout d’abord, veillez à initialiser correctement votre PRNG. Pour plus de simplicité, le générateur ci-dessous n'a pas de processus de génération de graine intégré, mais accepte un ou plusieurs nombres de 32 bits comme état de graine initial du PRNG. Les graines similaires ou clairsemées (par exemple, les graines simples de 1 et 2) ont une faible entropie et peuvent provoquer des problèmes de corrélation ou d'autres problèmes de qualité aléatoire, entraînant parfois des résultats avec des propriétés similaires (par exemple, les niveaux générés aléatoirement sont similaires). Pour éviter cela, la meilleure pratique consiste à initialiser le PRNG avec une graine à haute entropie uniformément distribuée et/ou à avancer au-delà des 15 premiers nombres environ.

Il existe de nombreuses façons de procéder, mais en voici deux. Premièrement, les fonctions de hachage sont très efficaces pour générer des graines à partir de chaînes courtes. Même si deux chaînes sont similaires, une bonne fonction de hachage produira des résultats très différents, vous n'aurez donc pas à trop réfléchir aux chaînes. Voici un exemple de fonction de hachage :

function cyrb128(str) {
    let h1 = 1779033703, h2 = 3144134277,
        h3 = 1013904242, h4 = 2773480762;
    for (let i = 0, k; i < str.length; i++) {
        k = str.charCodeAt(i);
        h1 = h2 ^ Math.imul(h1 ^ k, 597399067);
        h2 = h3 ^ Math.imul(h2 ^ k, 2869860233);
        h3 = h4 ^ Math.imul(h3 ^ k, 951274213);
        h4 = h1 ^ Math.imul(h4 ^ k, 2716044179);
    }
    h1 = Math.imul(h3 ^ (h1 >>> 18), 597399067);
    h2 = Math.imul(h4 ^ (h2 >>> 22), 2869860233);
    h3 = Math.imul(h1 ^ (h3 >>> 17), 951274213);
    h4 = Math.imul(h2 ^ (h4 >>> 19), 2716044179);
    h1 ^= (h2 ^ h3 ^ h4), h2 ^= h1, h3 ^= h1, h4 ^= h1;
    return [h1>>>0, h2>>>0, h3>>>0, h4>>>0];
}

Call cyrb128 générera une valeur de hachage de 128 bits à partir de la chaîne, qui peut être utilisée pour amorcer le PRNG. Voici comment vous pouvez l'utiliser :

// Create cyrb128 state:
var seed = cyrb128("apples");
// Four 32-bit component hashes provide the seed for sfc32.
var rand = sfc32(seed[0], seed[1], seed[2], seed[3]);

// Only one 32-bit component hash is needed for mulberry32.
var rand = mulberry32(seed[0]);

// Obtain sequential random numbers like so:
rand();
rand();

Remarque : si vous souhaitez un hachage de 128 bits légèrement plus puissant, pensez à MurmurHash3_x86_128, qui est plus complet mais conçu pour fonctionner avec de grands tableaux.

Vous pouvez également choisir simplement des données factices pour remplir la graine et faire avancer le générateur plusieurs fois (12 à 20 itérations) au préalable pour bien mélanger l'état initial. Cela a l'avantage d'être plus simple et est souvent utilisé dans les implémentations de référence de PRNG, mais cela limite le nombre d'états initiaux :

var seed = 1337 ^ 0xDEADBEEF; // 32-bit seed with optional XOR value
// Pad seed with Phi, Pi and E.
// https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
var rand = sfc32(0x9E3779B9, 0x243F6A88, 0xB7E15162, seed);
for (var i = 0; i < 15; i++) rand();

Remarque : La sortie de ces fonctions PRNG génère un nombre positif de 32 bits (0 à 2³²-1), qui est ensuite converti en un nombre à virgule flottante compris entre 0 et 1 (0 inclus, 1 exclu) équivalent à Math.random() , si vous souhaitez une plage spécifique de nombres aléatoires, lisez cet article sur MDN. Si vous voulez juste les bits d'origine, supprimez simplement la dernière opération de division.

Les nombres JavaScript ne peuvent représenter que des entiers d’une résolution maximale de 53 bits. Lorsque des opérations au niveau du bit sont utilisées, cette valeur est réduite à 32. Les PRNG modernes dans d'autres langages utilisent souvent des opérations 64 bits, ce qui nécessite des cales lors du portage vers JS, ce qui peut considérablement dégrader les performances. L'algorithme utilise ici uniquement des opérations 32 bits puisqu'il est directement compatible avec JS.

---

sfc32 (compteur rapide simple)

sfc32 fait partie de la suite de tests de nombres aléatoires PractRand (ça réussit bien sûr). sfc32 a un état de 128 bits et est très rapide en JS.

function sfc32(a, b, c, d) {
    return function() {
      a >>>= 0; b >>>= 0; c >>>= 0; d >>>= 0; 
      var t = (a + b) | 0;
      a = b ^ b >>> 9;
      b = c + (c << 3) | 0;
      c = (c << 21 | c >>> 11);
      d = d + 1 | 0;
      t = t + d | 0;
      c = c + t | 0;
      return (t >>> 0) / 4294967296;
    }
}

Vous vous demandez peut-être | 是什么？ 0 和 >>>= 0 是用于。这些本质上是 32 位整数转换，用于性能优化。 JS 中的 Number Fondamentalement, ce sont tous des nombres à virgule flottante, mais lorsque vous effectuez des opérations au niveau du bit, ils passent en mode entier 32 bits. Ce mode est traité plus rapidement par l'interpréteur JS, mais toute multiplication ou ajout le fera revenir en virgule flottante, entraînant une baisse de performances.

Mûrier 32

Mulberry32 est un générateur simple avec un état 32 bits, mais il est extrêmement rapide et a un bon caractère aléatoire (l'auteur dit qu'il réussit la suite de tests gjrand avec un cycle complet de 2³², mais je ne l'ai pas encore vérifié) .

function mulberry32(a) {
    return function() {
      var t = a += 0x6D2B79F5;
      t = Math.imul(t ^ t >>> 15, t | 1);
      t ^= t + Math.imul(t ^ t >>> 7, t | 61);
      return ((t ^ t >>> 14) >>> 0) / 4294967296;
    }
}

Je le recommanderais si vous avez juste besoin d'un PRNG simple mais décent et que vous n'avez pas besoin de milliards de nombres aléatoires (voir question d'anniversaire).

xoshiro128**

Depuis mai 2018, xoshiro128** est un nouveau membre de la famille Xorshift , développée par Vigna et Blackman (le professeur Vigna est également responsable de l'algorithme Xorshift128+, qui alimente la plupart des Math.random implémentations). C'est le générateur le plus rapide fournissant un état de 128 bits.

function xoshiro128ss(a, b, c, d) {
    return function() {
        var t = b << 9, r = b * 5; r = (r << 7 | r >>> 25) * 9;
        c ^= a; d ^= b;
        b ^= c; a ^= d; c ^= t;
        d = d << 11 | d >>> 21;
        return (r >>> 0) / 4294967296;
    }
}

L'auteur affirme qu'il réussit très bien le test du caractère aléatoire (malgré les mises en garde). D'autres chercheurs ont noté qu'il avait échoué à certains tests de TestU01 (notamment LinearComp et BinaryRank). En pratique, cela ne devrait pas poser de problèmes lorsque l'on travaille avec des nombres à virgule flottante (comme dans ces implémentations), mais cela pourrait se produire si l'on s'appuie sur le bit d'origine de poids le plus bas.

JSF (Jenkins Fast)

Il s'agit du premier JSF ou "smallprng" de Bob Jenkins (2007). et Ghost Hash. Il réussit les tests PractRand et devrait être raisonnablement rapide, mais pas aussi rapide que sfc32.

function jsf32(a, b, c, d) {
    return function() {
        a |= 0; b |= 0; c |= 0; d |= 0;
        var t = a - (b << 27 | b >>> 5) | 0;
        a = b ^ (c << 17 | c >>> 15);
        b = c + d | 0;
        c = d + t | 0;
        d = a + t | 0;
        return (d >>> 0) / 4294967296;
    }
}

Answer 2

Non, il n'est pas possible de seeder Math.random(), mais il est assez simple d'écrire votre propre générateur, ou mieux encore, d'en utiliser un existant.

Voir : Cette question connexe.

Voir également le blog de David Bau pour plus d'informations sur le semis.