Xoroshiro

[Laurent Caillette]

"`Xoroshiro128+`"

https://en.wikipedia.org/wiki/Xoroshiro128%2B

est un algorithme de génération de nombre pseudo-aléatoires avec un ensemble de caractéristiques tout à fait attrayant.

- Les résultats aux tests statistiques sont meilleurs que ceux des autres générateurs.

- L'état est conservé sur 128 bits seulement, c'est à dire deux variables de type ``long`` en Java. 

- Sur du bon matériel il génère un nombre en moins d'une nanoseconde.

- La période est de 2^64.

- L'équidistribution est excellente.

Xoroshiro est donc beaucoup plus intéressant que tous ses équivalents -- notamment le ``java.util.Random`` -- pour qui veut générer des nombres aléatoires rapidement, avec une bonne qualité statistique mais sans atteindre une qualité cryptographique. 

Xoroshiro est le résultat de travaux menés par David Blackman, chercheur indépendant en Australie, et Sebastiano Vigna, de l'Université de Milan. Leur publication date de cette année.

== Motivation

Depuis notre dernière discussion sur le sujet je me suis intéressé aux générateurs de nombres pseudo-aléatoires ("PRNG", Pseudo-Random Number Generator) afin de générer des clés identifiant des entités visibles par les utilisateurs. Montrer les clés ça peut aider à s'y retrouver, mais ça laisse aussi déduire des choses sur l'activité de notre plateforme. Donc une petite dose de camouflage ne peut pas faire de mal.

Une solution c'est un générateur de clés qui fonctionne de la façon suivante. D'abord il génère des clés aléatoires, dans une certaine plage de valeurs. Il se souvient de toutes les valeurs générées pour éviter les doublons. Ça ne prend pas trop de place grâce à un ``BitSet`` qui occupe (à peu près) la largeur de la plage divisée par 8 (8 bits dans un octet). Par exemple si on veut se souvenir des `524.288` premières valeurs générées ça ne prend que `65.536` octets.

Une fois qu'un certain taux de remplissage est atteint les clés croissent de façon monotone, par incrément de 1.

Pour avoir des tests répétables il faut une génération déterministe, donc pseudo-aléatoire. C'est là qu'on est bien content de trouver le ``java.util.Random`` qui fournit toujours la même séquence pour une graine donnée.

Il y a peu j'ai commencé à concevoir un annuaire d'utilisateurs éditables par les utilisateurs eux-mêmes, avec des droits et tout le tintoin. Je veux une structure immuable, avec des copies à chaque changement. Je veux également que ça soit l'annuaire qui attribue les clés. Donc il faut que, lorsqu'on reconstruit l'annuaire, le générateur de clés se retrouve dans le même état. Donc il faut que l'état soit facile à externaliser.

Une façon d'externaliser l'état d'un ``java.util.Random`` c'est de garder quelque part la graine et le nombre d'itérations. Mais ça veut dire que chaque fois qu'on le reconstruit il faut générer autant de nombre que la dernière fois. C'est moche mais ça peut fonctionner. Par contre si on utilise un ``java.security.SecureRandom`` ça revient vite cher en puissance de calcul.

Le mieux c'est de faire du générateur est un objet immuable, qui contient sa propre configuration. Voici le contrat minimal :

<<<

public interface UniqueLongRandomizer< RANDOMIZER extends UniqueLongRandomizer > {

  long currentLongValue() ;

  RANDOMIZER next() ;

}

>>>

Après chaque ``RANDOMIZER`` concret exhibe ses propres paramètres de configuration, de façon à ce qu'on puisse le persister puis le reconstruire à l'identique. Comme ce sont des valeurs immuables pas de problème.

Puis je me suis mis à la recherche d'un générateur de nombres aléatoires dont l'état puisse s'externaliser simplement, et que le temps de remise en état soit constant. Idéalement il fournirait quelque chose comme tous les nombres de 0 à `2^63 - 1` dans le désordre, avec pour seul paramètre d'entrée le nombre de valeurs déjà générées. Mais là je crois que je rêve un peu.

J'ai d'abord tenté ma chance en hachant un compteur incrémenté de 1 à chaque tentative, avec un SHA-256 et en gardant juste une partie des bits. En cas de doublon, on réessaye, et au bout d'un certain nombre de tentatives on dit que la génération aléatoire c'est fini et on passe à la génération monotone.

Là on voit que l'équidistribution des valeurs produites par l'algorithme compte beaucoup. Si on ne garde que les bits de poids faible et que ceux-ci ne varient pas assez souvent on se retrouve coincé. En revanche, avec une bonne équidistribution, un générateur peut remplir presque toutes les valeurs aléatoires en-dessous du seuil, avant de passer à la génération monotone.

== Mise en œuvre

L'équidistribution du SHA-256 n'était apparemment pas suffisante. Après j'ai essayé le "Xorshift"

https://en.wikipedia.org/wiki/Xorshift

qui était mieux. Mais je n'arrivais pas à dépasser `150.000` valeurs aléatoires.

Puis j'ai découvert le Xoroshiro. Avec un seuil de `524.287` (`2^19 - 1`) et au plus 1000 tentatives en cas de collision, le Xoroshiro produit `520.637` valeurs différentes, ce qui fait un taux de remplissage de `99 %`. La classe.

== Annexe

"Javadoc de la version originale"

http://dsiutils.di.unimi.it/docs/it/unimi/dsi/util/XoRoShiRo128PlusRandom.html

"Scrambled Linear Pseudorandom Number Generators"

http://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf

"SquidPony"

https://github.com/SquidPony/SquidLib/blob/master/squidlib-util/src/main/java/squidpony/squidmath/XoRoRNG.java

Dans "Chiron-toolbox"

https://github.com/OTCdLink/Chiron-framework/blob/master/modules/chiron/toolbox/src/main/java/com/otcdlink/chiron/toolbox/random/UniqueLongRandomizer.java