tinyrand
1.0.0
tinyrand Spécification RNG légère et plusieurs implémentations ultrarapilées dans la rouille. tinyrand est no_std et n'utilise pas d'allocateur de tas.
tinyrand ?std , ce qui signifie qu'il est intégré - il fonctionne sur des microcontrôleurs et des environnements à métal nu (pas de système d'exploitation).Mock pour le code de test qui dépend des nombres aléatoires. Autrement dit, si vous vous souciez de la couverture du code.Vous trouverez ci-dessous une comparaison de plusieurs PRNG notables.
| Prng | Algorithme | Bande passante (GB / s) | |
|---|---|---|---|
rand | Chacha12 | 2.4 | |
tinyrand | Splitmix | 6.5 | |
tinyrand | Xorshift | 6.7 | |
fastrand | Wyrand | 7.5 | |
tinyrand | Wyrand | 14.6 |
TL; DR: tinyrand est 2x plus rapide que fastrand et 6x plus rapide que rand .
Il est impossible de dire avec certitude si un certain PRNG est bon; La réponse est probabiliste. Les trois algorithmes se tiennent bien contre le barrage des tests, mais Wyrand et Splitmix sont un peu meilleurs que XORSHIFT. (Testé sur 30,8 milliards d'échantillons.) Cela signifie que tinyrand produit des nombres qui semblent suffisamment aléatoires et sont probablement adaptés à une utilisation dans la plupart des applications.
Les algorithmes tinyrand ne sont pas cryptographiquement sécurisés, ce qui signifie qu'il est possible de deviner le prochain nombre aléatoire en observant une séquence de nombres. (Ou les chiffres précédents, d'ailleurs.) Si vous avez besoin d'un CSPRNG robuste, il est fortement suggéré que vous alliez avec rand . Les CSPRNG sont généralement beaucoup plus lents et la plupart des gens n'en ont pas besoin.
cargo add tinyrand Une instance Rand est requise pour générer des nombres. Ici, nous utilisons StdRand , qui est un alias pour le RNG par défaut / recommandé. (Actuellement réglé sur Wyrand , mais peut changer à l'avenir.)
use tinyrand :: { Rand , StdRand } ;
let mut rand = StdRand :: default ( ) ;
for _ in 0 .. 10 {
let num = rand . next_u64 ( ) ;
println ! ( "generated {num}" ) ;
}De même, nous pouvons générer un nombre d'autres types:
use tinyrand :: { Rand , StdRand } ;
let mut rand = StdRand :: default ( ) ;
let num = rand . next_u128 ( ) ;
println ! ( "generated wider {num}" ) ; Les méthodes next_uXX génèrent des nombres dans toute la plage non signée du type spécifié. Souvent, nous voulons un nombre dans une plage spécifique:
use tinyrand :: { Rand , StdRand , RandRange } ;
let mut rand = StdRand :: default ( ) ;
let tasks = vec ! [ "went to market" , "stayed home" , "had roast beef" , "had none" ] ;
let random_index = rand . next_range ( 0 ..tasks . len ( ) ) ;
let random_task = tasks [ random_index ] ;
println ! ( "This little piggy {random_task}" ) ; Un autre cas d'utilisation courant est de générer bool s. Nous pourrions également vouloir attribuer une pondération aux résultats binaires:
use tinyrand :: { Rand , StdRand , Probability } ;
let mut rand = StdRand :: default ( ) ;
let p = Probability :: new ( 0.55 ) ; // a slightly weighted coin
for _ in 0 .. 10 {
if rand . next_bool ( p ) {
// expect to see more heads in the (sufficiently) long run
println ! ( "heads" ) ;
} else {
println ! ( "tails" ) ;
}
}Il y a des moments où nous avons besoin de notre fil pour dormir pendant un certain temps, en attendant une condition. Lorsque de nombreux fils dorment, il est généralement recommandé de se retirer au hasard pour éviter une bousculade.
use tinyrand :: { Rand , StdRand , RandRange } ;
use core :: time :: Duration ;
use std :: thread ;
use tinyrand_examples :: SomeSpecialCondition ;
let mut rand = StdRand :: default ( ) ;
let condition = SomeSpecialCondition :: default ( ) ;
let base_sleep_micros = 10 ;
let mut waits = 0 ;
while !condition . has_happened ( ) {
let min_wait = Duration :: ZERO ;
let max_wait = Duration :: from_micros ( base_sleep_micros * 2u64 . pow ( waits ) ) ;
let random_duration = rand . next_range ( min_wait..max_wait ) ;
println ! ( "backing off for {random_duration:?}" ) ;
thread :: sleep ( random_duration ) ;
waits += 1 ;
} Invoquer Default::default() sur un Rand l'initialise avec une graine constante. C'est idéal pour la répétabilité, mais se traduit par la même série de nombres "aléatoires", ce qui n'est pas ce dont la plupart des gens ont besoin.
tinyrand est une caisse no_std et, malheureusement, il n'y a pas de bon moyen portable de générer l'entropie lorsque l'on ne peut pas faire d'hypothèses sur la plate-forme sous-jacente. Dans la plupart des applications, on pourrait une horloge, mais quelque chose d'aussi trivial que SystemTime::now().duration_since(SystemTime::UNIX_EPOCH) pourrait ne pas toujours être disponible.
Si vous avez une source d'entropie à votre disposition, vous pouvez semer un Rrnd comme tel:
use tinyrand :: { Rand , StdRand , Seeded } ;
let seed = tinyrand_examples :: get_seed_from_somewhere ( ) ; // some source of entropy
let mut rand = StdRand :: seed ( seed ) ;
let num = rand . next_u64 ( ) ;
println ! ( "generated {num}" ) ; Vous pouvez également envisager d'utiliser getrandom , qui est une méthode multiplateforme pour récupérer les données d'entropie.
Si l'on ne se soucie pas du no_std , ils ne devraient pas être liés par ses limites. Pour semer dans l'horloge du système, vous pouvez opter pour std :
cargo add tinyrand-std Maintenant, nous avons une ClockSeed à notre disposition, qui met également en œuvre le trait Rand . ClockSeed dérivent un u64 en Xorant les 64 bits supérieurs de l'horodatage nanoseconde (du SystemTime ) avec les 64 bits inférieurs. Il ne convient pas à une utilisation cryptographique, mais il suffira pour la plupart des applications à usage général.
use tinyrand :: { Rand , StdRand , Seeded } ;
use tinyrand_std :: clock_seed :: ClockSeed ;
let seed = ClockSeed :: default ( ) . next_u64 ( ) ;
println ! ( "seeding with {seed}" ) ;
let mut rand = StdRand :: seed ( seed ) ;
let num = rand . next_u64 ( ) ;
println ! ( "generated {num}" ) ; La caisse tinyrand-std comprend également une mise en œuvre Rand à semence et au fil de filetage:
use tinyrand :: Rand ;
use tinyrand_std :: thread_rand ;
let mut rand = thread_rand ( ) ;
let num = rand . next_u64 ( ) ;
println ! ( "generated {num}" ) ; Une bonne couverture de test peut parfois être difficile à réaliser; Doublement, lorsque les applications dépendent de l'aléatoire ou d'autres sources de non-déterminisme. tinyrand est livré avec un Mock RNG qui offre un contrôle à grain fin sur l'exécution de votre code.
La simulation utilise la caisse alloc , car elle nécessite une allocation de tas de fermetures. En tant que tel, la simulation est distribuée en tant que package d'opt-in:
cargo add tinyrand-alloc Au niveau de la base, Mock est configurée avec une poignée de délégués . Un délégué est une fermeture invoquée par la simulation lorsqu'une méthode de trait particulière est appelée par le système testé. Le simulation maintient également un état d'invocation interne qui maintient le nombre de fois où un délégué particulier a été exercé. Ainsi, non seulement vous pouvez vous moquer du comportement du trait Rand , mais aussi vérifier le nombre de types qu'un groupe particulier de méthodes de trait associés a été appelée.
Les délégués sont spécifiés par le cas de test, tandis que l'instance simulée est transmise au système testé en tant qu'implémentation Rand . Actuellement, trois types de délégués sont pris en charge:
FnMut(&State) -> u128 - invoqué lorsque l'une des méthodes next_uXX() est appelée sur la simulation. ( uXX étant l'un des u16 , u32 , u64 , u128 ou usize .) Le délégué renvoie le numéro "aléatoire" suivant, qui peut avoir jusqu'à 128 bits de large. La largeur est conçue pour accueillir u128 - le type le plus large pris en charge par Rand . Si l'un des types plus étroits est demandé, la simulation renvoie simplement les bits inférieurs. (Par exemple, pour un u32 , la valeur moquée est tronquée en utilisant as u32 sous le capot.)FnMut(Surrogate, Probability) -> bool - invoqué lorsque la méthode next_bool(Probability) est appelée.FnMut(Surrogate, u128) -> u128 - lorsque next_lim ou next_range est appelé. En commençant par les bases absolues, MACHONS next_uXX() pour retourner une constante. Nous vérifierons ensuite combien de fois notre simulation a été appelée.
use tinyrand :: Rand ;
use tinyrand_alloc :: Mock ;
let mut rand = Mock :: default ( ) . with_next_u128 ( |_| 42 ) ;
for _ in 0 .. 10 {
assert_eq ! ( 42 , rand.next_usize ( ) ) ; // always 42
}
assert_eq ! ( 10 , rand.state ( ) .next_u128_invocations ( ) ) ; Bien que gênante, ce scénario est en fait assez courant. La même chose peut être obtenue avec la fonction fixed(uXX) .
use tinyrand :: Rand ;
use tinyrand_alloc :: { Mock , fixed } ;
let mut rand = Mock :: default ( ) . with_next_u128 ( fixed ( 42 ) ) ;
assert_eq ! ( 42 , rand.next_usize ( ) ) ; // always 42Étant donné que les délégués sont des fermetures régulières, nous pouvons nous lier à des variables dans la portée entourée. Cela nous donne un contrôle presque illimité sur le comportement de notre simulation.
use tinyrand :: Rand ;
use tinyrand_alloc :: Mock ;
use core :: cell :: RefCell ;
let val = RefCell :: new ( 3 ) ;
let mut rand = Mock :: default ( ) . with_next_u128 ( |_| * val . borrow ( ) ) ;
assert_eq ! ( 3 , rand.next_usize ( ) ) ;
// ... later ...
* val . borrow_mut ( ) = 17 ;
assert_eq ! ( 17 , rand.next_usize ( ) ) ;Le délégué peut être réaffecté à tout moment, même après la création et l'exercice de la simulation:
use tinyrand :: Rand ;
use tinyrand_alloc :: { Mock , fixed } ;
let mut rand = Mock :: default ( ) . with_next_u128 ( fixed ( 42 ) ) ;
assert_eq ! ( 42 , rand.next_usize ( ) ) ;
rand = rand . with_next_u128 ( fixed ( 88 ) ) ; // the mock's behaviour is now altered
assert_eq ! ( 88 , rand.next_usize ( ) ) ; La signature du délégué next_u128 prend une référence State , qui capture le nombre de fois où la maquette a été invoquée. (Le nombre est incrémenté uniquement une fois l'invocation terminée.) Écrivons une simulation qui renvoie un nombre "aléatoire" dérivé de l'état d'invocation.
use tinyrand :: Rand ;
use tinyrand_alloc :: Mock ;
let mut rand = Mock :: default ( ) . with_next_u128 ( |state| {
// return number of completed invocations
state . next_u128_invocations ( ) as u128
} ) ;
assert_eq ! ( 0 , rand.next_usize ( ) ) ;
assert_eq ! ( 1 , rand.next_usize ( ) ) ;
assert_eq ! ( 2 , rand.next_usize ( ) ) ; Ceci est utile lorsque nous nous attendons à ce que la simulation soit appelée plusieurs fois et que chaque invocation doit renvoyer un résultat différent. Un résultat similaire peut être obtenu avec la fonction counter(Range) , qui passe à travers une plage de nombres spécifiée, en emballage commodément à la limite:
use tinyrand :: Rand ;
use tinyrand_alloc :: { Mock , counter } ;
let mut rand = Mock :: default ( ) . with_next_u128 ( counter ( 5 .. 8 ) ) ;
assert_eq ! ( 5 , rand.next_usize ( ) ) ;
assert_eq ! ( 6 , rand.next_usize ( ) ) ;
assert_eq ! ( 7 , rand.next_usize ( ) ) ;
assert_eq ! ( 5 , rand.next_usize ( ) ) ; // start again En ne fournissant que le délégué next_u128 , nous pouvons influencer le résultat de toutes les autres méthodes dans le trait Rand , car ils dérivent tous de la même source de hasard et appellent finalement notre délégué sous le capot ... en théorie! En pratique, les choses sont beaucoup plus compliquées.
Des méthodes Rand dérivées, telles que next_bool(Probability) , next_lim(uXX) et next_range(Range) sont soutenues par différentes distributions de probabilité. next_bool , par exemple, tire de la distribution de Bernoulli, tandis que next_lim et next_range utilisent une distribution uniforme à l'échelle avec une couche de débiasage supplémentaire. De plus, la cartographie entre les différentes distributions est un détail de mise en œuvre interne qui est susceptible de changement. La couche debiasing à elle seule a plusieurs implémentations, optimisées pour les types de largeurs variables. En d'autres termes, les mappages de next_u128 à next_bool , next_lim et next_range et non trivial; Ce n'est pas quelque chose que vous voudrez vous moquer sans calculatrice et une certaine connaissance de l'arithmétique modulaire.
Heureusement, Rand nous permet de «contourner» ces fonctions de mappage. C'est là que les deux autres délégués entrent en jeu. Dans l'exemple suivant, nous nous moquons du résultat de next_bool .
use tinyrand :: { Rand , Probability } ;
use tinyrand_alloc :: Mock ;
let mut rand = Mock :: default ( ) . with_next_bool ( |_ , _| false ) ;
if rand . next_bool ( Probability :: new ( 0.999999 ) ) {
println ! ( "very likely" ) ;
} else {
// we can cover this branch thanks to the magic of mocking
println ! ( "very unlikely" ) ;
} Le délégué next_bool reçoit une structure Surrogate , qui est à la fois une implémentation Rand et un gardien de l'état d'invocation. Le substitut nous permet de dériver bool , comme tel:
use tinyrand :: { Rand , Probability } ;
use tinyrand_alloc :: Mock ;
let mut rand = Mock :: default ( ) . with_next_bool ( |surrogate , _| {
surrogate . state ( ) . next_bool_invocations ( ) % 2 == 0
} ) ;
assert_eq ! ( true , rand.next_bool ( Probability ::new ( 0.5 ) ) ) ;
assert_eq ! ( false , rand.next_bool ( Probability ::new ( 0.5 ) ) ) ;
assert_eq ! ( true , rand.next_bool ( Probability ::new ( 0.5 ) ) ) ;
assert_eq ! ( false , rand.next_bool ( Probability ::new ( 0.5 ) ) ) ;Le substitut permet également au délégué d'appeler les méthodes moquées de l'intérieur de la simulation.
Le dernier délégué est utilisé pour se moquer des méthodes next_lim et next_range , en raison de leur isomorphisme. Sous le capot, les délégués next_range à next_lim , de sorte que, pour toutes les limites de limite ( M , N ), M < N , next_range(M..N) = M + next_lim(N - M) . C'est ainsi que tout est moqué dans la pratique:
use tinyrand :: { Rand , RandRange } ;
use tinyrand_alloc :: Mock ;
enum Day {
Mon , Tue , Wed , Thu , Fri , Sat , Sun
}
const DAYS : [ Day ; 7 ] = [ Day :: Mon , Day :: Tue , Day :: Wed , Day :: Thu , Day :: Fri , Day :: Sat , Day :: Sun ] ;
let mut rand = Mock :: default ( ) . with_next_lim_u128 ( |_ , _| 6 ) ;
let day = & DAYS [ rand . next_range ( 0 .. DAYS . len ( ) ) ] ;
assert ! ( matches! ( day, Day :: Sun ) ) ; // always a Sunday
assert ! ( matches! ( day, Day :: Sun ) ) ; // yes!!!tinyrand est-il testé? Cette section décrit brièvement l'approche tinyrand Testing. Il s'adresse à ceux qui -
Le processus de test tinyrand est divisé en quatre niveaux:
tinyrand . En d'autres termes, chaque ligne de code est exercée au moins une fois, les attentes fondamentales sont confirmées et il n'y a probablement pas de défauts triviaux.tinyrand . Ce sont des tests d'hypothèse formels qui supposent que la source est aléatoire (l'hypothèse nulle) et recherchent des preuves pour dissiper cette hypothèse (l'hypothèse alternative).Les tests unitaires ne visent pas à affirmer des qualités numériques; Ils sont de nature purement fonctionnelle. Les objectifs comprennent -
tinyrand est construit sur la philosophie que si une ligne de code n'est pas prouvée, elle doit être supprimée. Il n'y a aucune exception à cette règle.true résultat par rapport false dans la génération de bool s. Les fonctions de cartographie de la distribution uniforme à celle personnalisée sont non triviales et nécessitent une couche debiasing. tinyrand utilise différentes méthodes de débiasing en fonction de la largeur du mot. Le but des tests de transformation de domaine est de vérifier que cette fonctionnalité fonctionne comme prévu et que l'échantillonnage de rejet a lieu. Il ne vérifie cependant pas les propriétés numériques du débiasing. Les repères synthétiques sont utilisés pour exercer les chemins chauds des prngs tinyrand , en comparant les résultats aux bibliothèques de pairs. Les repères testent la génération de nombres à différentes longueurs de mots, les transformations / débias et la génération de bool pondérés. Un sous-ensemble de ces repères est également inclus dans les tests CI, ce qui rend un peu plus facile à comparer les performances de tinyrand à travers les versions de validation.
tinyrand est livré avec une suite de tests statistiques intégrée, inspirée par des goûts de Diehard, Diehardeur et NIST SP 800-22. La suite tinyrand est certes beaucoup plus petite que n'importe lequel de ces tests; L'intention n'est pas de reproduire le travail déjà substantiel et facilement accessible dans ce domaine, mais de créer un filet de sécurité qui est à la fois très efficace pour détecter les anomalies communes et assez rapidement pour être exécutée à chaque engagement.
Les tests suivants sont inclus.
Rand en masquant la valeur d'un seul bit, vérifiant que le nombre de fois que le bit est défini sur 1 est dans la plage attendue. Pour chaque essai ultérieur, le masque est décalé par un à gauche et l'hypothèse est retestée. Le test passe sur plusieurs cycles; Chaque cycle comprenant 64 essais de Bernoulli (un pour chaque bit de u64 ).bool avec une probabilité choisie à partir d'un mot non signé 64 bits. Le test comprend une série d'essais de Bernoulli avec une pondération différente (choisie au hasard) à chaque essai, simulant une série de flips de pièces. Dans chaque essai, H0 affirme que la source est aléatoire. (C'est-à-dire, le nombre de «têtes» se situe dans un intervalle statistiquement acceptable.)u64 S générés dans des essais séparés. Dans chaque essai, nous supposons que les valeurs des bits individuels sont IID avec une probabilité de 0,5, vérifiant que le nombre de fois que le bit est réglé sur 1 est dans la plage attendue. Pour une source aléatoire, le nombre de 1s (et 0s) suit un processus de Bernoulli. Chacun des tests de tinyrand est exercé non seulement contre ses propres PRNG, mais également contre des implémentations intentionnellement défectueuses, qui sont utilisées pour vérifier l'efficacité du test. Les tests doivent toujours ne pas rejeter H0 pour les PRNG corrects et accepter H1 pour ceux défectueux.
Les tests statistiques sont eux-mêmes ensemencés de valeurs aléatoires. L'aléatoire est utilisé pour semer les PRNG à tester (chaque essai est ensemencé indépendamment), attribuer des pondérations aux expériences de Bernoulli, sélectionner des gammes entières pour tester les fonctions de transformation et le débiasage, les valeurs de contrôle pour le test des collisions, etc. Nous utilisons le package rand comme Control PRNG afin qu'un défaut dans tinyrand ne puisse pas renverser par inadvertance un test d'une manière qui se masque. Les tests sont ensemencés de sorte que, bien qu'ils semblent être sur une excursion aléatoire à travers l'espace des paramètres, leur choix de paramètres est entièrement déterministe et donc reproductible. Ceci est essentiel en raison de la possibilité d'une erreur de type I (rejetant incorrectement l'hypothèse nulle), qui ne doit pas être autorisée à se produire par intermittence, en particulier dans les environnements CI. En d'autres termes, le test du hasard ne peut pas être laissé au hasard .
Une façon de tester l'hypothèse de l'aléatoire est de sélectionner un ensemble de paramètres (par exemple, la plage de génération entière M .. N ou la probabilité d'obtenir true à partir d'une distribution de Bernoulli) et d'effectuer un long terme, cherchant des anomalies dans un grand échantillon aléatoire . La justification est que plus l'échantillon est grand, plus il contiendra une anomalie détectable. Ce n'est généralement pas très efficace pour repérer certains types d'anomalies qui peuvent affecter les PRNG uniquement dans des conditions très spécifiques. Par exemple, une fonction de débutant mal écrite peut encore bien fonctionner pour la plupart des petites gammes entières et même quelques grandes (celles qui sont proches des pouvoirs de deux). Si le test choisit défavorablement les paramètres, il peut ne pas trouver d'anomalies, peu importe à quel point il teste de façon exhaustive ces paramètres.
Une bien meilleure façon de tester le PRNG consiste à introduire la diversité dans le régime de test - effectuant un grand nombre de petits essais avec des paramètres différents plutôt qu'un seul essai. C'est précisément ce que font les tests statistiques tinyrand - effectuer plusieurs essais avec des paramètres sélectionnés aléatoirement (mais déterministiquement). Cela expose immédiatement le problème des comparaisons multiples. Considérez un PRNG idéal a priori . Il générera fréquemment des nombres qui apparaîtront "aléatoires" selon une mesure convenue. Mais parfois, il produira une production qui apparaîtra non aléatoire par la même mesure. Même une source idéale produira une très longue manche ou des zéros, par exemple. En fait, le fait de ne pas le faire le rendrait également non aléatoire. Malheureusement, cela produira une valeur p qui échouera même le test le plus détendu ... à un moment donné. C'est un problème pour les tests d'hypothèse unique, mais il est proportionnellement exacerbé dans plusieurs tests d'hypothèse.
Les tests intégrés tinyrand abordent ce problème à l'aide de la méthode de correction séquentielle de Holm-Bonferroni. La correction de Holm-Bonferroni supprime les erreurs de type I tout en maintenant une bonne puissance statistique - suppression des erreurs de type II. Il semble bien performer pour les besoins de tinyrand , en particulier en voyant que les essais numériques sont généralement conservés dans la plage de 100 à 1000. (Les tests tinyrand sont conçus pour être très rapides, ce qui place une limite pratique sur le nombre d'essais - idéalement, tous les tests statistiques devraient se terminer en quelques secondes pour qu'ils soient mandatés dans le cadre du flux de développement de routine.)
La suite de tests de Dieharde étend la batterie purs et dure des tests d'origine de Marsaglia. Il est emballé avec un grand nombre de tests et prend beaucoup de temps (~ 1 heure) à terminer. tinyrand a un utilitaire pour pomper la sortie aléatoire à Dieharde, qui est généralement exécuté sur une base ad hoc. La batterie pureharde doit être exécutée lorsqu'un PRNG subit un changement de matériau, ce qui est rare - une fois qu'un algorithme PRNG est mis en œuvre, il reste généralement intact à moins qu'il ne soit refactorisé ou qu'un défaut soit trouvé. Dieharders est sans doute plus utile pour construire et tester les PRNG expérimentaux avec tinyrand . Les trois autres niveaux des tests sont suffisants pour l'entretien de l'emballage tinyrand .
Pour courir tinyrand contre Dieharde:
cargo run --release --bin random -- wyrand 42 binary 1T | dieharder -g 200 -a La commande ci-dessus utilise le Wyrand Prng, ensemencé avec le nombre 42, générant une sortie binaire sur 1 billion de mots 64 bits. Son stdout est pompé vers dieharder . (Dans la pratique, Dieharde consommera moins de 31 milliards de numéros.)
Un mot d'avertissement: Dieharders n'a pas de mécanisme pour traiter les erreurs de type I dans plusieurs tests d'hypothèse - en partie parce que les tests diffèrent en type, pas seulement par les paramètres. Dayharde limite les tests d'hypothèse à la portée d'un test individuel; Il n'y a pas d'hypothèse globale qui classe un PRNG comme ajustée ou inapte en fonction du nombre de tests passés, ou a-t-il autrement ajusté le niveau de confiance pour tenir compte des erreurs de type I.
