tinyrand
1.0.0
tinyrand Especificación de RNG ligero y varias implementaciones ultrarrápidas en Rust. tinyrand es no_std y no usa un asignador de montón.
tinyrand ?std , lo que significa que es incrustable: se ejecuta en microcontroladores y entornos de metal desnudo (sin sistema operativo).Mock para el código de prueba que depende de los números aleatorios. Es decir, si le importa la cobertura del código.A continuación se muestra una comparación de varios PRNG notables.
| Prng | Algoritmo | Ancho de banda (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 es 2 veces más rápido que fastrand y 6x más rápido que rand .
Es imposible saberlo con certeza si un cierto PRNG es bueno; La respuesta es probabilística. Los tres algoritmos se paran bien contra el aluvión de pruebas, pero Wyrand y Splitmix son un poco mejores que Xorshift. (Probado en 30.8 mil millones de muestras.) Esto significa que tinyrand produce números que parecen suficientemente aleatorios y probablemente son adecuados para su uso en la mayoría de las aplicaciones.
Los algoritmos tinyrand no son criptográficamente seguros, lo que significa que es posible adivinar el próximo número aleatorio observando una secuencia de números. (O los números anteriores, para el caso). Si necesita un CSPRNG robusto, se sugiere fuertemente que vaya con rand . Los CSPRNG son generalmente mucho más lentos y la mayoría de la gente no necesita uno.
cargo add tinyrand Se requiere una instancia Rand para generar números. Aquí, usamos StdRand , que es un alias para el RNG predeterminado/recomendado. (Actualmente establecido en Wyrand , pero puede cambiar en el futuro).
use tinyrand :: { Rand , StdRand } ;
let mut rand = StdRand :: default ( ) ;
for _ in 0 .. 10 {
let num = rand . next_u64 ( ) ;
println ! ( "generated {num}" ) ;
}Del mismo modo, podemos generar números de otros tipos:
use tinyrand :: { Rand , StdRand } ;
let mut rand = StdRand :: default ( ) ;
let num = rand . next_u128 ( ) ;
println ! ( "generated wider {num}" ) ; Los métodos next_uXX generan números en todo el rango sin firmar del tipo especificado. A menudo, queremos un número en un rango específico:
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}" ) ; Otro caso de uso común es generar bool s. Es posible que también queramos asignar una ponderación a los resultados binarios:
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" ) ;
}
}Hay momentos en que necesitamos que nuestro hilo duerma por un tiempo, esperando una condición. Cuando duermen muchos hilos, generalmente se recomienda retroceder aleatoriamente para evitar una estampida.
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 ;
} Invocar Default::default() en un Rand lo inicializa con una semilla constante. Esto es excelente para la repetibilidad, pero da como resultado la misma ejecución de números "aleatorios", que no es lo que la mayoría de la gente necesita.
tinyrand es una caja no_std y, lamentablemente, no hay una forma buena y portátil de generar entropía cuando no se pueden hacer suposiciones sobre la plataforma subyacente. En la mayoría de las aplicaciones, uno podría un reloj, pero algo tan trivial como SystemTime::now().duration_since(SystemTime::UNIX_EPOCH) podría no estar siempre disponible.
Si tiene una fuente de entropía a su disposición, podría sembrar un Rrnd como así:
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}" ) ; También puede considerar el uso de getrandom , que es un método multiplataforma para recuperar datos de entropía.
Si a uno no le importa no_std , no deberían estar obligados por sus limitaciones. Para sembrar desde el reloj del sistema, puede optar por std :
cargo add tinyrand-std Ahora, tenemos un ClockSeed a nuestra disposición, lo que también implementa el rasgo Rand . ClockSeed deriva un u64 Xoring los 64 bits superiores de la marca de tiempo de nanosegundos (desde SystemTime ) con los 64 bits inferiores. No es adecuado para uso criptográfico, pero será suficiente para la mayoría de las aplicaciones de propósito general.
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 caja de tinyrand-std también incluye una implementación Rand de hilo y hilo sembrado:
use tinyrand :: Rand ;
use tinyrand_std :: thread_rand ;
let mut rand = thread_rand ( ) ;
let num = rand . next_u64 ( ) ;
println ! ( "generated {num}" ) ; Una buena cobertura de prueba a veces puede ser difícil de lograr; Doblablemente, cuando las aplicaciones dependen de la aleatoriedad u otras fuentes de no determinismo. tinyrand viene con un RNG simulado que ofrece un control de grano fino sobre la ejecución de su código.
El simulacro usa la caja alloc , ya que requiere la asignación de cierres de montón. Como tal, el simulacro se distribuye como un paquete de suscripción:
cargo add tinyrand-alloc En el nivel de base, Mock está configurado con un puñado de delegados . Un delegado es un cierre invocado por el simulacro cuando el sistema llama un método de rasgo particular en prueba. El simulacro también mantiene un estado de invocación interna que realiza un seguimiento del número de veces que se ejerció un delegado en particular. Por lo tanto, no solo puede burlarse del comportamiento del rasgo Rand , sino que también verificar el número de tipos se llamó a un grupo particular de métodos de rasgos relacionados.
Los delegados son especificados por el caso de prueba, mientras que la instancia simulada se pasa al sistema bajo prueba como una implementación Rand . Actualmente, se admiten tres tipos de delegados:
FnMut(&State) -> u128 -Invocado cuando se llama uno de los métodos next_uXX() en el simulacro. ( uXX es uno de u16 , u32 , u64 , u128 o usize .) El delegado devuelve el siguiente número "aleatorio", que puede tener hasta 128 bits de ancho. El ancho está diseñado para acomodar u128 , el tipo más ancho admitido por Rand . Si se solicita uno de los tipos más estrechos, el simulacro simplemente devuelve los bits inferiores. (Por ejemplo, para un u32 , el valor burlado se trunca usando as u32 debajo del capó).FnMut(Surrogate, Probability) -> bool -invocado cuando se llama al método next_bool(Probability) .FnMut(Surrogate, u128) -> u128 -cuando se llama a next_lim o next_range . Comenzando con los conceptos básicos absolutos, nos burlemos de next_uXX() para devolver una constante. Luego verificaremos cuántas veces se llamó a nuestro simulacro.
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 ( ) ) ; Aunque vergonzosamente simple, este escenario es en realidad bastante común. Lo mismo se puede lograr con la función 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 42Dado que los delegados son cierres regulares, podemos unir a las variables en el alcance adjunto. Esto nos da un control casi ilimitado sobre el comportamiento de nuestro simulacro.
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 ( ) ) ;El delegado puede ser reasignado en cualquier momento, incluso después de que se haya creado y ejercido el simulacro:
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 firma del delegado next_u128 toma una referencia State , que captura el número de veces que se invocó el simulacro. (El recuento se incrementa solo después de que se completa la invocación). Escribamos un simulacro que devuelve un número "aleatorio" derivado del estado de invocación.
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 ( ) ) ; Esto es útil cuando esperamos que se llame el simulacro varias veces y cada invocación debería devolver un resultado diferente. Se puede lograr un resultado similar con la función counter(Range) , que se rinde en bicicleta a través de un rango especificado de números, envolviendo convenientemente en el límite:
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 Al suministrar solo el delegado next_u128 , podemos influir en el resultado de cualquier otro método en el rasgo Rand , porque todos derivan de la misma fuente de aleatoriedad y eventualmente llamarán a nuestro delegado bajo el capó ... ¡en teoría! En la práctica, las cosas son mucho más complicadas.
Los métodos Rand derivados, como next_bool(Probability) , next_lim(uXX) y next_range(Range) están respaldados por diferentes distribuciones de probabilidad. next_bool , por ejemplo, se basa en la distribución de Bernoulli, mientras que next_lim y next_range usan una distribución uniforme escalada con una capa de debiaje adicional. Además, el mapeo entre las diversas distribuciones es un detalle de implementación interna que está sujeto a cambios. La capa de Debiasing solo tiene varias implementaciones, optimizadas para tipos de anchos variables. En otras palabras, las asignaciones de next_u128 a next_bool , next_lim y next_range y no trivial; No es algo que querrás burlarse sin una calculadora y algún conocimiento de la aritmética modular.
Afortunadamente, Rand nos permite "pasar" de estas funciones de mapeo. Aquí es donde entran los otros dos delegados. En el siguiente ejemplo, nos burlamos del resultado 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" ) ;
} El delegado next_bool se le entrega una estructura Surrogate , que es tanto una implementación Rand como un guardián del estado de invocación. El sustituto nos deja derivar bool s, como así:
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 ) ) ) ;El sustituto también permite que el delegado llame a los métodos burlados del interior del simulacro.
El último delegado se usa para burlarse de los métodos next_lim y next_range , debido a su isomorfismo. Debajo del capó, next_range se delega a next_lim , de modo que, para cualquier par de límites de límite ( M , N ), M < N , next_range(M..N) = M + next_lim(N - M) . Así es como se burla todo en la práctica:
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 ? Esta sección describe brevemente el enfoque de prueba de tinyrand . Está dirigido a aquellos que -
El proceso de prueba tinyrand se divide en cuatro niveles:
tinyrand . En otras palabras, cada línea de código se ejerce al menos una vez, las expectativas fundamentales se mantienen y es probable que no haya defectos triviales.tinyrand . Estas son pruebas de hipótesis formales que suponen que la fuente es aleatoria (la hipótesis nula) y buscan evidencia para disipar esta suposición (la hipótesis alternativa).Las pruebas unitarias no tienen como objetivo afirmar cualidades numéricas; Son de naturaleza puramente funcional. Los objetivos incluyen -
tinyrand se basa en la filosofía de que si no se ejerce una línea de código, debe eliminarse. No hay excepciones a esta regla.true resultado versus false en la generación de bool s. Las funciones para mapear desde la distribución uniforme a una personalizada no son triviales y requieren una capa de debiaes. tinyrand utiliza diferentes métodos de debiating dependiendo del ancho de la palabra. El propósito de las pruebas de transformación de dominio es verificar que esta funcionalidad funcione como se esperaba y se produce un muestreo de rechazo. Sin embargo, no verifica las propiedades numéricas del debiasing. Los puntos de referencia sintéticos se utilizan para ejercer los caminos calientes de los tinyrand PRNG, comparando los resultados con las bibliotecas de pares. Los puntos de referencia prueban la generación de números en varias longitudes de palabras, transformaciones/debiasing y la generación de bool ponderados. También se incluye un subconjunto de estos puntos de referencia en las pruebas de CI, lo que hace que sea un poco más fácil comparar el rendimiento de tinyrand en las versiones de confirmación.
tinyrand viene incluido con una suite de pruebas estadísticas integradas, inspirada en los gustos de Diehard, Dieharder y NIST SP 800-22. La suite tinyrand es ciertamente mucho más pequeña que cualquiera de estas pruebas; La intención no es replicar el trabajo ya sustancial y fácilmente accesible en esta área, sino crear una red de seguridad que sea muy efectiva para detectar anomalías comunes y lo suficientemente rápido como para ejecutarse en cada compromiso.
Se incluyen las siguientes pruebas.
Rand enmascarando el valor de un solo bit, verificando que el número de veces que el bit se establece en 1 está dentro del rango esperado. Para cada ensayo posterior, la máscara se desplaza una a la izquierda y la hipótesis se vuelve a probar. La prueba continúa durante varios ciclos; Cada ciclo comprende 64 ensayos de Bernoulli (uno para cada bit de un u64 ).bool con una probabilidad elegida de una palabra sin firmar de 64 bits. La prueba comprende una serie de ensayos de Bernoulli con una ponderación diferente (elegida al azar) en cada ensayo, simulando una serie de volteretas de monedas. Dentro de cada ensayo, H0 afirma que la fuente es aleatoria. (Es decir, el número de 'cabezas' cae dentro de un intervalo estadísticamente aceptable).u64 S generados en ensayos separados. En cada ensayo, suponemos que los valores de los bits individuales son IID con probabilidad de 0.5, verificando que el número de veces que el bit se establece en 1 está dentro del rango esperado. Para una fuente aleatoria, el número de 1s (y 0s) sigue un proceso de Bernoulli. Cada una de las pruebas de tinyrand se ejerce no solo contra sus propios PRNG, sino también contra implementaciones intencionalmente defectuosas, que se utilizan para verificar la eficacia de la prueba. Las pruebas deben no rechazar constantemente H0 para los PRNG correctos y aceptar H1 para las defectuosas.
Las pruebas estadísticas están sembradas de valores aleatorios. La aleatoriedad se usa para sembrar los PRNG en prueba (cada ensayo se sembra independientemente), asigne ponderaciones a los experimentos de Bernoulli, rangos de enteros seleccionados para probar las funciones de transformación y la debiajes, los valores de control para las colisiones de pruebas, etc. Utilizamos el paquete rand como el control PRNG para que un defecto en tinyrand no pueda subvertir inadvertidamente una prueba de una manera que se enmienda. Las pruebas se sembran para que, aunque parecen estar en una excursión aleatoria a través del espacio de parámetros, su elección de parámetros es completamente determinista y, por lo tanto, repetible. Esto es esencial debido a la posibilidad de error tipo I (rechazando incorrectamente la hipótesis nula), que no debe permitirse que ocurra de manera intermitente, especialmente en entornos de CI. En otras palabras, las pruebas de aleatoriedad no pueden dejarse al azar .
Una forma de probar la hipótesis de la aleatoriedad es seleccionar un conjunto de parámetros (por ejemplo, el rango de generación de enteros M .. N o la probabilidad de obtener true de una distribución de Bernoulli) y realizar una carrera larga, buscando anomalías en una gran muestra aleatoria. . La justificación es que cuanto más grande sea la muestra, más probabilidades contiene una anomalía detectable. Esto generalmente no es muy efectivo para detectar ciertos tipos de anomalías que pueden afectar los PRNG solo en condiciones muy específicas. Por ejemplo, una función de debiasing mal escrita aún puede funcionar bien para la mayoría de los rangos de enteros pequeños e incluso algunos grandes (aquellos que están cerca de poderes de dos). Si la prueba elige parámetros desfavorablemente, es posible que no encuentre anomalías, sin importar cuán exhaustivamente pruebe esos parámetros.
Una forma mucho mejor de probar PRNG es introducir la diversidad en el régimen de prueba, llevando a cabo una gran cantidad de pequeños ensayos con diferentes parámetros en lugar de uno, una prueba muy grande. Esto es precisamente lo que hacen las pruebas estadísticas tinyrand : realizan varios ensayos con parámetros seleccionados aleatorios (pero deterministas). Esto expone inmediatamente el problema de comparaciones múltiples. Considere un prng ideal a priori . Con frecuencia generará números que aparecerán "aleatorios" de acuerdo con alguna medida acordada. Pero ocasionalmente, producirá una salida que aparecerá no aleatoria en la misma medida. Incluso una fuente ideal producirá una carrera muy larga de unos o ceros, por ejemplo. De hecho, no hacerlo también lo convertiría en no aleatorio. Desafortunadamente, esto producirá un valor p que fallará incluso la prueba más relajada ... en algún momento. Este es un problema para las pruebas de hipótesis única, pero se exacerbe proporcionalmente en las pruebas de hipótesis múltiples.
Las pruebas incorporadas tinyrand abordan este problema utilizando el método de corrección secuencial Holm-Bonferroni. La corrección de Holm-Bonferroni suprime los errores de tipo I mientras mantiene una buena potencia estadística: supresión de errores de tipo II. Parece que funciona bien para las necesidades de tinyrand , especialmente al ver que las pruebas numéricas generalmente se mantienen en el rango de 100-1000. (Las pruebas tinyrand están diseñadas para ser muy rápidas, lo que coloca un límite práctico en el número de ensayos, idealmente, todas las pruebas estadísticas deben completarse en unos pocos segundos para que sean obligados a ser obligatorios como parte del flujo de desarrollo de rutina).
La suite de prueba de diario extiende la batería de pruebas original de Marsaglia. Está incluido con una gran cantidad de pruebas y tarda mucho tiempo (~ 1 hora) en completarse. tinyrand tiene una utilidad para bombear la salida aleatoria al diálogo, que generalmente se ejecuta de manera ad hoc. La batería que se debe ejecutar cuando un PRNG sufre un cambio de material, lo cual es raro: una vez que se implementa un algoritmo PRNG, generalmente permanece intacto a menos que se refactorice o se encuentre algún defecto. Dieharder es posiblemente más útil para construir y probar PRNG experimentales con tinyrand . Los otros tres niveles de pruebas son suficientes para el mantenimiento del paquete tinyrand .
Para dirigir tinyrand contra el académico:
cargo run --release --bin random -- wyrand 42 binary 1T | dieharder -g 200 -a El comando anterior usa el Wyrand PRNG, sembrado con el número 42, que genera salida binaria en más de 1 billón de palabras de 64 bits. Su stdout se bombea a dieharder . (En la práctica, el diámetro consumirá menos de 31 mil millones de números).
Una palabra de precaución: el diálogo no tiene un mecanismo para lidiar con errores de tipo I en múltiples pruebas de hipótesis, en parte porque las pruebas difieren en tipo, no solo en los parámetros. El diámetro limita las pruebas de hipótesis al alcance de una prueba individual; No hay una hipótesis general que clasifique un PRNG como ajuste o no apto en función del número de pruebas aprobadas, o que ajuste el nivel de confianza para tener en cuenta los errores de tipo I.
