Amorçage du générateur de nombres aléatoires en Javascript

Est-il possible de semer le générateur de nombres aléatoires (Math.random) en Javascript?

Non, ce n'est pas le cas, mais il est assez facile d'écrire votre propre générateur, ou mieux d'utiliser un générateur existant. Découvrez: cette question connexe .

Consultez également le blog de David Bau pour plus d'informations sur l'ensemencement .

REMARQUE: Malgré (ou plutôt à cause de) la concision et l'élégance apparente, cet algorithme n'est en aucun cas de haute qualité en termes de caractère aléatoire. Recherchez par exemple ceux répertoriés dans cette réponse pour de meilleurs résultats.

(Adapté à l'origine d'une idée intelligente présentée dans un commentaire à une autre réponse.)

var seed = 1;
function random() {
    var x = Math.sin(seed++) * 10000;
    return x - Math.floor(x);
}

Vous pouvez définir seedn'importe quel nombre, évitez simplement zéro (ou tout multiple de Math.PI).

L'élégance de cette solution, à mon avis, vient de l'absence de nombres "magiques" (en plus de 10000, ce qui représente environ le nombre minimum de chiffres que vous devez jeter pour éviter les motifs étranges - voir les résultats avec les valeurs 10 , 100 , 1000 ). La concision est également agréable.

C'est un peu plus lent que Math.random () (d'un facteur 2 ou 3), mais je pense que c'est à peu près aussi rapide que n'importe quelle autre solution écrite en JavaScript.

J'ai implémenté un certain nombre de bonnes fonctions de générateur de nombres pseudo-aléatoires (PRNG) en JavaScript simple. Tous peuvent être ensemencés et fournir des chiffres de bonne qualité.

Tout d'abord, veillez à initialiser correctement vos PRNG. La plupart des générateurs ci-dessous n'ont pas de procédure de génération de graine intégrée (par souci de simplicité), mais acceptent une ou plusieurs valeurs 32 bits comme état initial du PRNG. Des graines similaires (par exemple une simple graine de 1 et 2) peuvent provoquer des corrélations dans des PRNG plus faibles, résultant en une sortie ayant des propriétés similaires (telles que des niveaux générés aléatoirement étant similaires). Pour éviter cela, il est préférable d'initialiser les PRNG avec une graine bien distribuée.

Heureusement, les fonctions de hachage sont très efficaces pour générer des graines pour les PRNG à partir de chaînes courtes. Une bonne fonction de hachage génèrera des résultats très différents même lorsque deux chaînes sont similaires. Voici un exemple basé sur la fonction de mixage de MurmurHash3:

function xmur3(str) {
    for(var i = 0, h = 1779033703 ^ str.length; i < str.length; i++)
        h = Math.imul(h ^ str.charCodeAt(i), 3432918353),
        h = h << 13 | h >>> 19;
    return function() {
        h = Math.imul(h ^ h >>> 16, 2246822507);
        h = Math.imul(h ^ h >>> 13, 3266489909);
        return (h ^= h >>> 16) >>> 0;
    }
}

Chaque appel ultérieur à la fonction de retour de xmur3produit une nouvelle valeur de hachage 32 bits "aléatoire" à utiliser comme valeur de départ dans un PRNG. Voici comment vous pouvez l'utiliser:

// Create xmur3 state:
var seed = xmur3("apples");
// Output four 32-bit hashes to provide the seed for sfc32.
var rand = sfc32(seed(), seed(), seed(), seed());

// Output one 32-bit hash to provide the seed for mulberry32.
var rand = mulberry32(seed());

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

Alternativement, choisissez simplement des données fictives avec lesquelles remplir la graine et avancez le générateur plusieurs fois (12-20 itérations) pour mélanger complètement l'état initial. Cela se voit souvent dans les implémentations de référence des 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();

La sortie de ces fonctions PRNG produit un nombre positif de 32 bits (0 à 2 ³² -1) qui est ensuite converti en un nombre à virgule flottante entre 0-1 (0 inclus, 1 exclusif) équivalent à Math.random(), si vous voulez des nombres aléatoires d'une gamme spécifique, lisez cet article sur MDN . Si vous ne voulez que les bits bruts, supprimez simplement l'opération de division finale.

Une autre chose à noter est les limitations de JS. Les nombres ne peuvent représenter que des entiers entiers jusqu'à une résolution de 53 bits. Et lorsque vous utilisez des opérations au niveau du bit, ce nombre est réduit à 32. Cela rend difficile l'implémentation d'algorithmes écrits en C ou C ++, qui utilisent des nombres 64 bits. Le portage de code 64 bits nécessite des shims qui peuvent réduire considérablement les performances. Donc, pour des raisons de simplicité et d'efficacité, je n'ai considéré que des algorithmes qui utilisent des mathématiques 32 bits, car il est directement compatible avec JS.

Passons maintenant aux générateurs. (Je maintiens la liste complète avec des références ici )

sfc32 (compteur rapide simple)

sfc32 fait partie de la suite de tests de nombres aléatoires PractRand (qu'il réussit bien sûr). sfc32 a un état de 128 bits et est très rapide dans 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;
    }
}

Mulberry32

Mulberry32 est un générateur simple avec un état 32 bits, mais il est extrêmement rapide et de bonne qualité (l'auteur déclare qu'il passe tous les tests de la suite de tests gjrand et a une période complète de 2 ³² , mais je n'ai pas 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 recommanderais ceci si vous avez juste besoin d'un PRNG simple mais décent et n'avez pas besoin de milliards de nombres aléatoires (voir problème d'anniversaire ).

xoshiro128 **

Depuis mai 2018, xoshiro128 ** est le nouveau membre de la famille Xorshift , par Vigna / Blackman (qui a également écrit xoroshiro, qui est utilisé dans Chrome). C'est le générateur le plus rapide qui offre un état 128 bits.

function xoshiro128ss(a, b, c, d) {
    return function() {
        var t = b << 9, r = a * 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;
    }
}

Les auteurs affirment qu'il réussit bien les tests de hasard ( bien qu'avec des mises en garde ). D'autres chercheurs ont souligné l'échec de certains tests dans TestU01 (en particulier LinearComp et BinaryRank). En pratique, cela ne devrait pas causer de problèmes lorsque des flottants sont utilisés (tels que ces implémentations), mais peut provoquer des problèmes si vous comptez sur les bits bas bruts.

JSF (petit jeûne de Jenkins)

C'est JSF ou 'smallprng' de Bob Jenkins (2007), le gars qui a fait ISAAC et SpookyHash . Il passe les tests PractRand et devrait être assez rapide, mais pas aussi rapide que SFC.

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

LCG (alias Lehmer / Park-Miller RNG ou MCG)

LCG est extrêmement rapide et simple, mais la qualité de son caractère aléatoire est si faible, qu'une mauvaise utilisation peut en fait provoquer des bugs dans votre programme! Néanmoins, c'est nettement mieux que certaines réponses suggérant d'utiliser Math.sinou Math.PI! C'est un monoplace, ce qui est bien :).

var LCG=s=>()=>(2**31-1&(s=Math.imul(48271,s)))/2**31;

Cette implémentation est appelée le RNG standard minimal tel que proposé par Park – Miller en 1988 et 1993 et implémenté en C ++ 11 as minstd_rand. Gardez à l'esprit que l'état est 31 bits (31 bits donnent 2 milliards d'états possibles, 32 bits le double). C'est le type même de PRNG que d'autres essaient de remplacer!

Cela fonctionnera, mais je ne l'utiliserais pas sauf si vous avez vraiment besoin de vitesse et que vous ne vous souciez pas de la qualité du hasard (qu'est-ce qui est aléatoire de toute façon?). Idéal pour un jeu jam ou une démo ou quelque chose. Les LCG souffrent de corrélations de graines, il est donc préférable de jeter le premier résultat d'un LCG. Et si vous insistez pour utiliser un LCG, l'ajout d'une valeur d'incrémentation peut améliorer les résultats, mais c'est probablement un exercice futile lorsque de bien meilleures options existent.

Il semble y avoir d'autres multiplicateurs offrant un état 32 bits (espace d'état accru):

var LCG=s=>()=>(s=Math.imul(741103597,s)>>>0)/2**32;
var LCG=s=>()=>(s=Math.imul(1597334677,s)>>>0)/2**32;

Ces valeurs LCG proviennent de: P. L'Ecuyer: Tableau des générateurs linéaires congruentiels de différentes tailles et bonne structure de réseau, 30 avril 1997.

Non, mais voici un simple générateur pseudo-aléatoire, une implémentation de Multiply-with-carry que j'ai adaptée de Wikipédia (a été supprimée depuis):

var m_w = 123456789;
var m_z = 987654321;
var mask = 0xffffffff;

// Takes any integer
function seed(i) {
    m_w = (123456789 + i) & mask;
    m_z = (987654321 - i) & mask;
}

// Returns number between 0 (inclusive) and 1.0 (exclusive),
// just like Math.random().
function random()
{
    m_z = (36969 * (m_z & 65535) + (m_z >> 16)) & mask;
    m_w = (18000 * (m_w & 65535) + (m_w >> 16)) & mask;
    var result = ((m_z << 16) + (m_w & 65535)) >>> 0;
    result /= 4294967296;
    return result;
}

EDIT: correction de la fonction de départ en la réinitialisant m_z
EDIT2: de graves failles d'implémentation ont été corrigées

L'algorithme d'Anti Sykäri est agréable et court. J'ai initialement fait une variation qui a remplacé Math.random de Javascript lorsque vous appelez Math.seed (s), mais Jason a ensuite commenté que le retour de la fonction serait mieux:

Math.seed = function(s) {
    return function() {
        s = Math.sin(s) * 10000; return s - Math.floor(s);
    };
};

// usage:
var random1 = Math.seed(42);
var random2 = Math.seed(random1());
Math.random = Math.seed(random2());

Cela vous donne une autre fonctionnalité que Javascript n'a pas: plusieurs générateurs aléatoires indépendants. Cela est particulièrement important si vous souhaitez que plusieurs simulations répétables s'exécutent en même temps.

Veuillez voir le travail de Pierre L'Ecuyer remontant à la fin des années 1980 et au début des années 1990. Il y a d'autres aussi. Créer un générateur de nombres (pseudo) aléatoires par vous-même, si vous n'êtes pas un expert, est assez dangereux, car il y a une forte probabilité que les résultats ne soient pas statistiquement aléatoires ou qu'ils aient une petite période. Pierre (et d'autres) ont mis en place de bons (pseudo) générateurs de nombres aléatoires faciles à implémenter. J'utilise l'un de ses générateurs LFSR.

https://www.iro.umontreal.ca/~lecuyer/myftp/papers/handstat.pdf

Phil Troy

En combinant certaines des réponses précédentes, voici la fonction aléatoire que vous recherchez:

Math.seed = function(s) {
    var mask = 0xffffffff;
    var m_w  = (123456789 + s) & mask;
    var m_z  = (987654321 - s) & mask;

    return function() {
      m_z = (36969 * (m_z & 65535) + (m_z >>> 16)) & mask;
      m_w = (18000 * (m_w & 65535) + (m_w >>> 16)) & mask;

      var result = ((m_z << 16) + (m_w & 65535)) >>> 0;
      result /= 4294967296;
      return result;
    }
}

var myRandomFunction = Math.seed(1234);
var randomNumber = myRandomFunction();

Écrire votre propre générateur pseudo-aléatoire est assez simple.

La suggestion de Dave Scotese est utile mais, comme l'ont souligné d'autres personnes, elle n'est pas distribuée de manière tout à fait uniforme.

Cependant, ce n'est pas à cause des arguments entiers du péché. C'est simplement à cause de l'étendue du péché, qui se trouve être une projection unidimensionnelle d'un cercle. Si vous preniez plutôt l'angle du cercle, ce serait uniforme.

Donc, au lieu de sin (x), utilisez arg (exp (i * x)) / (2 * PI).

Si vous n'aimez pas l'ordre linéaire, mélangez-le un peu avec xor. Le facteur réel n'a pas beaucoup d'importance non plus.

Pour générer n nombres pseudo aléatoires, on pourrait utiliser le code:

function psora(k, n) {
  var r = Math.PI * (k ^ n)
  return r - Math.floor(r)
}
n = 42; for(k = 0; k < n; k++) console.log(psora(k, n))

Veuillez également noter que vous ne pouvez pas utiliser de séquences pseudo-aléatoires lorsqu'une véritable entropie est nécessaire.

Beaucoup de gens qui ont besoin d'un générateur de nombres aléatoires semable en Javascript ces jours-ci utilisent le module seedrandom de David Bau .

Math.randomnon, mais la RAN bibliothèque résout ce. Il a presque toutes les distributions que vous pouvez imaginer et prend en charge la génération de nombres aléatoires prédéfinis. Exemple:

ran.core.seed(0)
myDist = new ran.Dist.Uniform(0, 1)
samples = myDist.sample(1000)

J'ai écrit une fonction qui renvoie un nombre aléatoire prédéfini, elle utilise Math.sin pour avoir un nombre aléatoire long et utilise la graine pour choisir des nombres à partir de cela.

Utilisation :

seedRandom("k9]:2@", 15)

il renverra votre nombre prédéfini le premier paramètre est une valeur de chaîne; votre graine. le deuxième paramètre est le nombre de chiffres qui reviendront.

     function seedRandom(inputSeed, lengthOfNumber){

           var output = "";
           var seed = inputSeed.toString();
           var newSeed = 0;
           var characterArray = ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','y','x','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','U','R','S','T','U','V','W','X','Y','Z','!','@','#','$','%','^','&','*','(',')',' ','[','{',']','}','|',';',':',"'",',','<','.','>','/','?','`','~','-','_','=','+'];
           var longNum = "";
           var counter = 0;
           var accumulator = 0;

           for(var i = 0; i < seed.length; i++){
                var a = seed.length - (i+1);
                for(var x = 0; x < characterArray.length; x++){
                     var tempX = x.toString();
                     var lastDigit = tempX.charAt(tempX.length-1);
                     var xOutput = parseInt(lastDigit);
                     addToSeed(characterArray[x], xOutput, a, i); 
                }                  
           }

                function addToSeed(character, value, a, i){
                     if(seed.charAt(i) === character){newSeed = newSeed + value * Math.pow(10, a)}
                }
                newSeed = newSeed.toString();

                var copy = newSeed;
           for(var i=0; i<lengthOfNumber*9; i++){
                newSeed = newSeed + copy;
                var x = Math.sin(20982+(i)) * 10000;
                var y = Math.floor((x - Math.floor(x))*10);
                longNum = longNum + y.toString()
           }

           for(var i=0; i<lengthOfNumber; i++){
                output = output + longNum.charAt(accumulator);
                counter++;
                accumulator = accumulator + parseInt(newSeed.charAt(counter));
           }
           return(output)
      }

Une approche simple pour une graine fixe:

function fixedrandom(p){
    const seed = 43758.5453123;
    return (Math.abs(Math.sin(p)) * seed)%1;
}

Pour un nombre compris entre 0 et 100.

Number.parseInt(Math.floor(Math.random() * 100))