Aller au contenu
Hugo Delacour
Tous les articles

Même graine, même monde : le hasard reproductible en JavaScript

Un générateur censé produire la même base partout comptait 95 037 colis dans Node et 94 849 dans Chrome. L'enquête : un dernier bit dans Math.pow, un tri tiré au sort, et ce que les normes garantissent vraiment.

14 octobre 20267 min
  • JavaScript
  • Tests
  • Architecture

Ce site construit une base de données dans le navigateur : 74 tables, 2,7 millions de lignes, générées à l'ouverture à partir d'une graine fixe. La promesse tient en une phrase : même graine, même base, pour tout le monde. Les tests la vérifiaient dans Node, et ils passaient.

Dans Chrome, la base comptait 94 849 colis. Dans Node, 95 037. Même code, même graine : deux mondes.

Un hasard qu'on peut rejouer

Math.random() ne prend pas de graine : impossible de lui faire rejouer une suite. Pour un monde reproductible, il faut son propre générateur pseudo-aléatoire. Celui de ce site s'appelle mulberry32, de Tommy Ettinger — dix lignes, un état de 32 bits :

rng.ts
export function rng(seed: number) {
  let s = seed >>> 0;
  return function next() {
    s = (s + 0x6d2b79f5) >>> 0;
    let t = s;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

Tout y est entier. >>>, ^ et Math.imul travaillent sur 32 bits, et la norme fixe leur résultat au bit près ; la division finale par 2³² est exacte. Ce générateur rend la même suite dans tous les moteurs. Ce n'était pas lui.

Le dernier bit de Math.pow

Le générateur tire des nombres entre 0 et 1 ; le reste du code les façonne. Une popularité suit une loi de puissance, Math.pow(u, 0.72). Une taille suit une loi normale, Math.sqrt(-2 * Math.log(u)) * Math.cos(2 * Math.PI * v).

Or la norme ECMAScript ne fixe pas ces résultats-là. Pour Math.pow, Math.log, Math.exp, Math.cos et leurs voisines, elle demande une valeur « approchée par l'implémentation » — implementation-approximated. Chaque moteur choisit son algorithme, et deux versions du même moteur peuvent ne pas choisir le même.

Mesuré : 200 000 appels de chaque fonction, sur les mêmes entrées, résumés par une empreinte. Node 22 et Chrome 152 — deux versions de V8 — rendent des empreintes différentes pour pow, log et cos. Identiques pour Math.sqrt : la racine carrée, elle, doit être correctement arrondie.

Les écarts sont minuscules : le dernier bit, sur quelques résultats. Mais un générateur ne regarde pas les nombres, il les arrondit. Qu'un Math.floor(n * Math.pow(u, k)) tombe pile sur une frontière, et ce dernier bit décide de l'entier. Si l'entier change le nombre de tirages qui suivent — une commande de trois lignes au lieu de deux —, toute la suite se décale.

MÊME GRAINE, MÊMES APPELS, DEUX MOTEURSNode 22V8 12.495 037COLISChrome 152V8 15.294 849COLIS=====≈≠≠≠≠≠≠≠≠Math.pow : le dernier bit diffère
Le mécanisme, schématisé : les mêmes appels donnent les mêmes tirages, jusqu'à celui où Math.pow diffère d'un bit. Après, plus rien n'est commun. Les deux totaux sont ceux des vraies bases.

Ce que la norme garantit au bit près

Il ne restait qu'à ne plus dépendre de ces fonctions. La norme IEEE 754 impose aux quatre opérations — addition, soustraction, multiplication, division — et à la racine carrée un résultat correctement arrondi : le flottant le plus proche du résultat exact. JavaScript ne s'autorise aucun raccourci : chaque opération est arrondie à son tour, sans multiplication-addition fusionnée.

Un logarithme, une exponentielle ou un cosinus écrits avec ces seules opérations rendent donc le même résultat partout. Une série suffit :

rng.ts
const LN2 = 0.6931471805599453;
 
export function ln(x: number): number {
  let e = 0;
  while (x >= 2) { x /= 2; e++; } // diviser par 2 est exact
  while (x < 1) { x *= 2; e--; }
  // x ∈ [1, 2[ : ln x = 2 atanh(z), avec z = (x − 1) / (x + 1) < 1/3
  const z = (x - 1) / (x + 1), z2 = z * z;
  let term = z, sum = 0;
  for (let k = 1; k < 64; k += 2) {
    sum += term / k;
    term *= z2;
  }
  return 2 * sum + e * LN2;
}
 
export const pow = (x: number, k: number) => (x === 0 ? 0 : exp(k * ln(x)));

L'exponentielle se ramène de même à une série de Taylor sur un petit intervalle, le cosinus aussi. Le prix : 57 ns par appel contre 24 pour Math.pow, et la construction de la base n'a pas bougé — 3,5 secondes avant comme après. La précision : l'écart avec Math.pow reste sous 2 × 10⁻¹⁵ en relatif, et le logarithme perd quelques chiffres tout près de 1. Le générateur s'en moque. Il ne demande pas la meilleure valeur, il demande la même.

Le tri qui tirait au sort

Restait un second suspect, plus sournois :

const couleurs = [...COULEURS].sort(() => r.next() - 0.5);

Un comparateur qui répond au hasard n'est pas un comparateur. La norme le dit sans détour : quand la fonction de comparaison n'est pas cohérente, l'ordre obtenu est « défini par l'implémentation ». Il dépend de l'algorithme de tri du moteur, et du nombre de comparaisons qu'il fait — donc du nombre de tirages qu'il consomme. Deux moteurs, deux ordres, et une suite décalée pour tout ce qui vient après.

Ce mélange n'est même pas uniforme : certaines permutations sortent plus souvent que d'autres. Le bon outil date de 1938 et porte le nom de ses auteurs, Fisher et Yates ; Durstenfeld l'a mis en forme pour l'ordinateur en 1964.

function shuffle<T>(xs: T[], next: () => number): T[] {
  for (let i = xs.length - 1; i > 0; i--) {
    const j = Math.floor(next() * (i + 1));
    [xs[i], xs[j]] = [xs[j], xs[i]];
  }
  return xs;
}

Exactement n − 1 tirages, quel que soit le moteur, et chaque permutation a la même probabilité.

MÉLANGER HUIT CARTES : UN TIRAGE PAR POSITION01234567i = 7 · j = 4i = 6 · j = 3i = 5 · j = 5i = 4 · j = 3i = 3 · j = 0i = 2 · j = 1i = 1 · j = 0ABCDEFGH7 TIRAGES POUR 8 CARTES, QUEL QUE SOIT LE MOTEUR
Fisher-Yates : partir de la fin, tirer une position parmi celles qui restent, échanger, fixer. Les tirages sont ceux du générateur du site, graine 42.

Les autres sources de dérive

Math.pow et sort étaient les coupables ici. Ils ne sont pas les seuls à pouvoir donner deux résultats à un même programme :

Source Reproductible ? La parade
+ − × ÷, Math.sqrt, Math.floor, Math.imul Oui, au bit près —
Math.pow, log, exp, sin, cos… Non les réécrire avec les quatre opérations
sort avec un comparateur incohérent Non Fisher-Yates
sort avec un vrai comparateur Oui : le tri est stable depuis ES2019 —
Intl, toLocaleString Non : dépend des données ICU du moteur formater soi-même ce qui doit rester identique
new Date("2026-03-29 02:30") Non : format libre, lu dans le fuseau local des dates ISO avec fuseau, les méthodes UTC
Ordre des clés d'un objet, d'une Map Oui —

La ligne Intl n'est pas théorique. En 2023, une mise à jour des données ICU a remplacé, dans Chrome puis dans Node, l'espace qui précède « AM » par une espace fine insécable : toLocaleTimeString("en-US") ne rendait plus la même chaîne, et bien des tests qui la comparaient ont cassé le même jour.

Le vérifier pour de vrai

Le test qui passait ne mentait pas : il vérifiait la base dans un seul moteur. Une promesse « partout » se vérifie au moins à deux endroits. Le principe : une empreinte — quelques comptes et quelques sommes qui dépendent de tout le reste —, calculée d'un côté dans les tests, de l'autre dans la page, puis comparée.

Graine2026Chromela pageNode 22npm testEmpreintes99 028 = 99 028colis, prixcolis, prix
Une graine, deux moteurs, une empreinte de chaque côté. Après correction, les deux bases sont identiques.

Après correction, les deux côtés donnent 99 028 colis, 619 944 articles commandés et 13 549 618,34 € de prix au catalogue. On ne peut pas tester tous les navigateurs, mais on n'en a plus besoin : le générateur n'emploie plus que des opérations dont la norme fixe le résultat au bit près. La reproductibilité ne se constate pas, elle se construit.

En résumé

  1. Math.random ne rejoue rien : un générateur à graine comme mulberry32 ne fait que des opérations entières, donc portables.
  2. Math.pow, log, cos sont approchées : leur dernier bit varie d'un moteur à l'autre, et d'une version à l'autre.
  3. Un seul bit suffit, dès qu'un arrondi décide d'un nombre de tirages.
  4. Les quatre opérations et Math.sqrt sont exactes : on réécrit le reste avec elles.
  5. Un comparateur aléatoire dépend de l'algorithme de tri : on mélange avec Fisher-Yates.
  6. On teste la reproductibilité à deux endroits, avec une empreinte.