tinyrand
1.0.0
tinyrand Lightweight RNG specification and several ultrafast implementations in Rust. tinyrand é no_std e não usa um alocador de heap.
tinyrand ?std , o que significa que é incorporável-é executado em microcontroladores e ambientes de metal nu (sem OS).Mock para testar o código que depende de números aleatórios. Ou seja, se você se preocupa com a cobertura do código.Abaixo está uma comparação de vários PRNGs notáveis.
| Prng | Algoritmo | Largura de banda (GB/s) | |
|---|---|---|---|
rand | Chacha12 | 2.4 | |
tinyrand | SplitMix | 6.5 | |
tinyrand | XorShift | 6.7 | |
fastrand | Wyrond | 7.5 | |
tinyrand | Wyrond | 14.6 |
Tl; dr: tinyrand é 2x mais rápido que fastrand e 6x mais rápido que rand .
É impossível dizer ao certo se um certo prng é bom; A resposta é probabilística. Todos os três algoritmos se levantam bem contra a barragem obstinada de testes, mas Wyrand e Splitmix são um pouco melhores que o XorShift. (Testado em 30,8 bilhões de amostras.) Isso significa que tinyrand produz números que parecem suficientemente aleatórios e provavelmente é adequado para uso na maioria das aplicações.
Os algoritmos tinyrand não são criptograficamente seguros, o que significa que é possível adivinhar o próximo número aleatório observando uma sequência de números. (Ou os números anteriores, nesse caso.) Se você precisar de um CSPRNG robusto, é fortemente sugerido que você vá com rand . Os csprngs geralmente são muito mais lentos e a maioria das pessoas não precisa de uma.
cargo add tinyrand Uma instância Rand é necessária para gerar números. Aqui, usamos StdRand , que é um alias para o RNG padrão/recomendado. (Atualmente definido como Wyrand , mas pode mudar no futuro.)
use tinyrand :: { Rand , StdRand } ;
let mut rand = StdRand :: default ( ) ;
for _ in 0 .. 10 {
let num = rand . next_u64 ( ) ;
println ! ( "generated {num}" ) ;
}Da mesma forma, podemos gerar um número de outros tipos:
use tinyrand :: { Rand , StdRand } ;
let mut rand = StdRand :: default ( ) ;
let num = rand . next_u128 ( ) ;
println ! ( "generated wider {num}" ) ; Os métodos next_uXX geram números em toda a faixa não assinada do tipo especificado. Muitas vezes, queremos um número em um intervalo 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}" ) ; Outro caso de uso comum está gerando bool s. Também podemos querer atribuir uma ponderação aos resultados binários:
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" ) ;
}
}Há momentos em que precisamos do nosso tópico para dormir por um tempo, esperando por uma condição. Quando muitos threads estão dormindo, geralmente é recomendável que eles recuem aleatoriamente para evitar uma debandada.
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() em um Rand inicializa com uma semente constante. Isso é ótimo para repetibilidade, mas resulta na mesma série de números "aleatórios", que não é o que a maioria das pessoas precisa.
tinyrand é uma caixa no_std e, infelizmente, não há uma maneira boa e portátil de gerar entropia quando não se pode fazer suposições sobre a plataforma subjacente. Na maioria dos aplicativos, pode -se um relógio, mas algo tão trivial quanto SystemTime::now().duration_since(SystemTime::UNIX_EPOCH)
Se você tiver uma fonte de entropia à sua disposição, poderá semear um Rrnd como sim:
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}" ) ; You might also consider using getrandom , which is a cross-platform method for retrieving entropy data.
Se alguém não se importa com no_std , não deve estar vinculado por suas limitações. Para semear do relógio do sistema, você pode optar por std :
cargo add tinyrand-std Agora, temos uma ClockSeed à nossa disposição, que também implementa o traço Rand . ClockSeed deriva um u64 xingando os 64 bits superiores do registro de data e hora de nanossegundos (do SystemTime ) com os 64 bits inferiores. Não é adequado para uso criptográfico, mas será suficiente para a maioria das aplicações de uso geral.
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}" ) ; A caixa tinyrand-std também inclui uma implementação semeada e local Rand :
use tinyrand :: Rand ;
use tinyrand_std :: thread_rand ;
let mut rand = thread_rand ( ) ;
let num = rand . next_u64 ( ) ;
println ! ( "generated {num}" ) ; Às vezes, uma boa cobertura de testes pode ser difícil de alcançar; Duplamente, quando as aplicações dependem da aleatoriedade ou de outras fontes de não determinismo. tinyrand vem com um RNG simulado que oferece controle de granulação fina sobre a execução do seu código.
A simulação usa a caixa alloc , pois requer a alocação de fechamentos. Como tal, a simulação é distribuída como um pacote de inscrição:
cargo add tinyrand-alloc No nível de base, Mock é estrutura configurada com um punhado de delegados . Um delegado é um fechamento que é invocado pela simulação quando um método de característica específico é chamado pelo sistema em teste. O Mock também mantém um estado de invocação interno que acompanha o número de vezes que um delegado específico foi exercido. Portanto, você não apenas pode zombar do comportamento do traço Rand , mas também verificar o número de tipos que um grupo específico de métodos de características relacionadas foi chamado.
Os delegados são especificados pelo caso de teste, enquanto a instância de simulação é passada para o sistema em teste como uma implementação Rand . Atualmente, três tipos de delegados são suportados:
FnMut(&State) -> u128 -Invocado quando um dos métodos next_uXX() é chamado no Mock. ( uXX sendo um dos u16 , u32 , u64 , u128 ou usize .) O delegado retorna o próximo número "aleatório", que pode ter até 128 bits de largura. A largura foi projetada para acomodar u128 - o tipo mais amplo suportado pelo Rand . Se um dos tipos mais estreitos for solicitado, a simulação simplesmente retorna os bits inferiores. (Por exemplo, para um u32 , o valor ridículo é truncado usando as u32 sob o capô.)FnMut(Surrogate, Probability) -> bool -invocado quando o método next_bool(Probability) é chamado.FnMut(Surrogate, u128) -> u128 -Quando next_lim ou next_range é chamado. Começando com o básico absoluto, vamos zombar next_uXX() para retornar uma constante. Em seguida, verificaremos quantas vezes nossa simulação foi chamada.
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 ( ) ) ; Embora embaraçosamente simples, esse cenário é realmente bastante comum. O mesmo pode ser alcançado com a função 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 42Como os delegados são fechamentos regulares, podemos vincular a variáveis no escopo de anexo. Isso nos dá um controle quase ilimitado sobre o comportamento de nossa simulação.
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 ( ) ) ;O delegado pode ser transferido a qualquer momento, mesmo depois que a simulação foi criada e exercida:
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 ( ) ) ; A assinatura do delegado next_u128 recebe uma referência State , que captura o número de vezes que a simulação foi invocada. (A contagem é incrementada somente após a conclusão da invocação.) Vamos escrever uma simulação que retorne um número "aleatório" derivado do estado de invocação.
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 ( ) ) ; Isso é útil quando esperamos que a simulação seja chamada várias vezes e cada invocação deve retornar um resultado diferente. Um resultado semelhante pode ser alcançado com a função counter(Range) , que percorre uma faixa especificada de números, envolvendo convenientemente no 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 Ao fornecer apenas o delegado next_u128 , podemos influenciar o resultado de todos os outros métodos do traço Rand , porque todos derivam da mesma fonte de aleatoriedade e acabarão por chamar nosso delegado sob o capô ... em teoria! Na prática, as coisas são muito mais complicadas.
Os métodos Rand derivados, como next_bool(Probability) , next_lim(uXX) e next_range(Range) são apoiados por diferentes distribuições de probabilidade. next_bool , por exemplo, se baseia na distribuição de Bernoulli, enquanto next_lim e next_range usam uma distribuição uniforme em escala com uma camada de debiasing adicional. Além disso, o mapeamento entre as várias distribuições é um detalhe interno da implementação que está sujeito a alterações. Somente a camada de debiasing possui várias implementações, otimizadas para tipos de larguras variadas. Em outras palavras, os mapeamentos de next_u128 a next_bool , next_lim e next_range e não trivial; Não é algo que você queira zombar sem uma calculadora e algum conhecimento de aritmética modular.
Felizmente, Rand nos permite "ignorar" essas funções de mapeamento. É aqui que entram os outros dois delegados. No exemplo a seguir, zombamos do resultado do 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" ) ;
} O delegado next_bool recebe uma estrutura Surrogate , que é uma Rand e guardião do estado de invocação. O substituto nos permite derivar bool s, como assim:
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 ) ) ) ;The surrogate also lets the delegate call the mocked methods from inside the mock.
O último delegado é usado para zombar dos métodos next_lim e next_range , devido ao seu isomorfismo. Sob o capô, next_range delega para next_lim , de modo que, para qualquer par de limites de limite ( M , N ), M < N , next_range(M..N) = M + next_lim(N - M) . É assim que tudo é ridicularizado na prática:
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 é testado? Esta seção descreve brevemente a abordagem de teste de tinyrand . Visa aqueles que -
O processo de teste tinyrand é dividido em quatro camadas:
tinyrand . Em outras palavras, toda linha de código é exercida pelo menos uma vez, as expectativas fundamentais são mantidas e provavelmente não há defeitos triviais.tinyrand . São testes formais de hipótese que assumem que a fonte é aleatória (a hipótese nula) e procure evidências para dissipar essa suposição (a hipótese alternativa).Os testes de unidade não têm como objetivo afirmar qualidades numéricas; Eles são puramente funcionais de natureza. Os objetivos incluem -
tinyrand é construído sobre a filosofia de que, se uma linha de código não for comprovada, ela deve ser removida. Não há exceções a esta regra.true resultado versus false na geração de bool s. As funções para o mapeamento da distribuição uniforme para uma personalizada não são triviais e exigem uma camada de debiasing. tinyrand usa diferentes métodos de debiasing, dependendo da largura da palavra. O objetivo dos testes de transformação de domínio é verificar se essa funcionalidade está funcionando como esperada e a amostragem de rejeição está ocorrendo. No entanto, ele não verifica as propriedades numéricas do Debiasing. Os benchmarks sintéticos são usados para exercer os caminhos quentes dos PRNGs tinyrand , comparando os resultados às bibliotecas de pares. Os benchmarks testam a geração de números em vários comprimentos de palavras, transformações/debiasing e a geração de bool ponderado s. Um subconjunto desses benchmarks também está incluído nos testes de IC, facilitando um pouco a comparação do desempenho de tinyrand nas versões de comprometimento.
tinyrand vem com uma suíte de teste estatístico integrado, inspirado em artistas como Diehard, Dieharder e Nist SP 800-22. A suíte tinyrand é reconhecidamente muito menor do que qualquer um desses testes; A intenção não é replicar o trabalho já substancial e facilmente acessível nessa área, mas criar uma rede de segurança que seja muito eficaz na detecção de anomalias comuns e rápido o suficiente para ser executado em todos os compromissos.
Os seguintes testes estão incluídos.
Rand , mascarando o valor de um único bit, verificando que o número de vezes em que o bit está definido como 1 está dentro do intervalo esperado. For each subsequent trial, the mask is shifted by one to the left and the hypothesis is retested. O teste prossegue sobre vários ciclos; Cada ciclo compreendendo 64 ensaios de Bernoulli (um para cada bit de u64 ).bool com uma probabilidade escolhida de uma palavra não assinada de 64 bits. O teste compreende uma série de ensaios de Bernoulli com uma ponderação diferente (escolhida aleatoriamente) em cada estudo, simulando uma corrida de movimentos de moedas. Dentro de cada estudo, o H0 afirma que a fonte é aleatória. (Ou seja, o número de 'cabeças' se enquadra em um intervalo estatisticamente aceitável.)u64 s gerados em ensaios separados. Em cada estudo, assumimos que os valores dos bits individuais são IID com probabilidade de 0,5, verificando que o número de vezes o bit está definido como 1 está dentro do intervalo esperado. Para uma fonte aleatória, o número de 1s (e 0s) segue um processo de Bernoulli. Cada um dos testes de tinyrand é exercido não apenas contra seus próprios PRNGs, mas também contra implementações intencionalmente defeituosas, que são usadas para verificar a eficácia do teste. Os testes devem falhar consistentemente em rejeitar o H0 para os PRNGs corretos e aceitar o H1 para os defeituosos.
Os testes estatísticos são semeados a partir de valores aleatórios. A aleatoriedade é usada para semear os PRNGs em teste (todo teste é semeado independentemente), atribua ponderações a experimentos de Bernoulli, selecione intervalos inteiros para testar funções de transformação e debiasening, valores de controle para testar colisões e assim por diante. Usamos o pacote rand como o PRNG de controle para que um defeito em tinyrand não possa subverter inadvertidamente um teste de uma maneira que se mascule. Os testes são semeados para que, embora pareçam estar em uma excursão aleatória através do espaço dos parâmetros, sua escolha de parâmetros é totalmente determinística e, portanto, repetível. Isso é essencial devido à possibilidade de erro do tipo I (rejeitando incorretamente a hipótese nula), que não deve ocorrer intermitentemente, especialmente em ambientes de IC. Em outras palavras, o teste de aleatoriedade não pode ser deixado ao acaso .
Uma maneira de testar a hipótese da aleatoriedade é selecionar um conjunto de parâmetros (por exemplo, a faixa de geração inteira M .. N ou a probabilidade de obter true de uma distribuição de Bernoulli) e realizar um longo prazo, buscando anomalias em uma grande amostra aleatória . Quanto a lógica é que, quanto maior a amostra, maior a probabilidade de conter uma anomalia detectável. Isso geralmente não é muito eficaz para detectar certos tipos de anomalias que podem afetar os PRNGs apenas em condições muito específicas. Por exemplo, uma função de debiasing mal escrita ainda pode ter um bom desempenho para a maioria dos intervalos inteiros pequenos e até alguns grandes (aqueles que estão próximos dos poderes de dois). Se o teste escolher os parâmetros desfavoráveis, poderá não encontrar anomalias, por mais exaustivamente que testa esses parâmetros.
A much better way of testing PRNG is to introduce diversity into the testing regime — conducting a large number of small trials with different parameters rather than one, very large trial. É exatamente isso que os testes estatísticos tinyrand - conduzem vários ensaios com parâmetros selecionados aleatoriamente (mas deterministicamente). Isso expõe imediatamente o problema de comparações múltiplas. Considere um prng a priori . Frequentemente, gera números que aparecem "aleatórios" de acordo com alguma medida acordada. But occasionally, it will produce output that will appear nonrandom by the same measure. Mesmo uma fonte ideal produzirá um longo período ou zeros, por exemplo. De fato, não fazer isso também o tornaria não -aleatório. Infelizmente, isso produzirá um valor p que falhará até o teste mais relaxado ... em algum momento. Este é um problema para testes de hipóteses únicas, mas é proporcionalmente exacerbado em múltiplos testes de hipóteses.
Os testes internos tinyrand abordam esse problema usando o método de correção sequencial de Holm-Bonferroni. A correção de Holm-Bonferroni suprime erros do tipo I, mantendo um bom poder estatístico-supressão dos erros do tipo II. Parece ter um bom desempenho para as necessidades de tinyrand , especialmente vendo que os ensaios numéricos geralmente são mantidos na faixa de 100 a 1.000. (Os testes tinyrand são projetados para serem muito rápidos, o que coloca um limite prático no número de ensaios - idealmente, todos os testes estatísticos devem ser concluídos dentro de alguns segundos para que sejam mandatados como parte do fluxo de desenvolvimento de rotina.)
O Dieharder Test Suite estende a bateria original dos testes de Marsaglia. É empacotado com um grande número de testes e leva muito tempo (~ 1 hora) para ser concluído. tinyrand tem uma utilidade para bombear a saída aleatória para o obstinado, que normalmente é executado em uma base ad hoc. A bateria obstinada deve ser executada quando um PRNG sofre uma mudança de material, o que é raro - uma vez que um algoritmo PRNG é implementado, geralmente permanece intocado, a menos que seja refaturado ou algum defeito. Dieharder is arguably more useful for building and testing experimental PRNGs with tinyrand . Os outros três níveis de testes são suficientes para a manutenção do pacote tinyrand .
Para correr tinyrand contra o obstinado:
cargo run --release --bin random -- wyrand 42 binary 1T | dieharder -g 200 -a O comando acima usa o prng Wyrand, semeado com o número 42, gerando saída binária em 1 trilhão de palavras de 64 bits. Seu stdout é bombeado para o dieharder . (Na prática, o obstinado consumirá menos de 31 bilhões de números.)
Uma palavra de cautela: Dieharder não possui um mecanismo para lidar com erros do tipo I em vários testes de hipóteses - em parte porque os testes diferem no tipo, não apenas nos parâmetros. O obstinado limita o teste de hipóteses ao escopo de um teste individual; Não há hipótese abrangente que classifique um PRNG como adequado ou impróprio com base no número de testes passados ou ajusta o nível de confiança para explicar os erros do tipo I.
