Modo corretto per ottenere un numero compreso tra 0 e 9 da un byte casuale?

Ci sono due modi generici per produrre una cifra casuale "sufficientemente imparziale".

Il primo metodo consiste nel loop se il byte non si trova nell'intervallo corretto. Cioè:.

• Ottieni il prossimo byte casuale b .
• Se b si trova nell'intervallo 0..249, restituisci b mod 10.
• Loop.

Questo metodo può consumare un numero illimitato di byte casuali, ma è perfettamente imparziale ed è molto improbabile che richieda il loop molte volte. Questo è ciò che Java Random.nextInt (int) si applica il metodo standard (anche se con parole a 32 bit anziché byte).

Il secondo metodo è quello di utilizzare come valore di origine non un byte ma una parola abbastanza grande. Supponi di usare 20 byte, interpretarli come un intero x nell'intervallo 0..2 ¹⁶⁰ -1 e restituire x mod 10. In questo modo, il pregiudizio è ancora lì, ma può essere reso arbitrariamente piccolo, al punto che non conta più. Questo è computazionalmente costoso (più del primo metodo) ma ha il vantaggio di richiedere sempre lo stesso numero di byte di input, che può essere utile in alcune situazioni specifiche (ad esempio perdite di canale laterale).

Dividere il byte, per visualizzare più numeri

Dato che il generatore casuale può essere qualcosa costoso , il modo più efficiente è tagliare ogni byte (0-255) in due parti (0-15), prima di eliminare fuori limite valori:

C'è un piccolo campione usando bash :

unset random cnt
while [ ! "$random" ] ;do
    ((cnt++))
    i=$(dd if=/dev/random bs=1 count=1 2>/dev/null | od -A n -t u1)
    for val in $((i&15)) $((i>>4)) ;do
        [ $val -lt 10 ] && [ ! "$random" ] && random=$val
    done
done
printf "%d bytes read, random value: %d\n" $cnt $random

Esecuzione di un tipo di confronto:

Come risposta al commento di @ AndreasKrey, c'è una piccola demo, in cui cerco di ottenere 10 numeri tra 0 e 9:

Uso lo stesso pot (di numeri casuali) in entrambi i metodi:

• Dividere il byte in due parti e filtrare un numero maggiore di 9
• Rilascio di numeri superiori a 249 e utilizzando mod :

.

#!/bin/bash

myRandom() {
    printf ${1+-v} $1 "%s" $(
        head -c1 /dev/urandom | od -A n -t u1
    )
}

num=${1:-10} byteMod=0 byteSplit=0 potMod=() potSplit=() wholePot=()

while [ ${#potMod[@]} -lt $num ] || [ ${#potSplit[@]} -lt $num ];do
    myRandom rndVal
    wholePot+=($rndVal)

    [ ${#potMod[@]}   -lt $num ] && ((byteMod+=1)) &&
        [ $rndVal -lt 250 ] && potMod+=($[rndVal%10])

    [ ${#potSplit[@]} -lt $num ] && ((byteSplit+=1))

    for val in $[rndVal&15] $[rndVal>>4] ;do
        [ $val -lt 10 ] && [ ${#potSplit[@]} -lt $num ] && potSplit+=($val)
      done

  done

printf "%2d bytes was read for rendering %2d values by split * max 10: %s\n" \
    $byteSplit ${#potSplit[@]} "${potSplit[*]}"
printf "%2d bytes was read for rendering %2d values by max 250 && mod: %s\n" \
    $byteMod ${#potMod[@]} "${potMod[*]}"

echo Whole pot: ${wholePot[@]}

Potrebbe essere eseguito più volte:

./randGen10.sh
 6 bytes was read for rendering 10 values by split * max 10: 8 3 9 7 9 3 1 1 3 4
10 bytes was read for rendering 10 values by max 250 && mod: 6 1 7 0 9 0 3 1 3 9
Whole pot: 56 121 57 30 49 20 183 161 123 239

./randGen10.sh
 7 bytes was read for rendering 10 values by split * max 10: 7 1 5 0 7 4 6 9 4 4
10 bytes was read for rendering 10 values by max 250 && mod: 3 3 6 1 8 3 4 0 4 9
Whole pot: 23 213 176 71 198 73 244 220 154 139

./randGen10.sh
10 bytes was read for rendering 10 values by split * max 10: 0 8 3 9 6 6 8 9 2 3
11 bytes was read for rendering 10 values by max 250 && mod: 1 8 2 5 4 8 9 9 0 7
Whole pot: 221 128 254 62 105 214 168 249 189 50 77

./randGen10.sh
 7 bytes was read for rendering 10 values by split * max 10: 3 1 5 9 5 8 6 9 7 7
10 bytes was read for rendering 10 values by max 250 && mod: 9 1 9 8 8 1 7 4 7 6
Whole pot: 19 181 89 168 198 121 247 54 117 226

./randGen10.sh
 9 bytes was read for rendering 10 values by split * max 10: 5 8 6 3 6 8 5 4 0 1
10 bytes was read for rendering 10 values by max 250 && mod: 4 0 0 9 3 4 8 6 6 9
Whole pot: 234 90 200 109 243 214 88 196 16 199

./randGen10.sh
11 bytes was read for rendering 10 values by split * max 10: 3 1 9 5 0 0 6 9 5 5
10 bytes was read for rendering 10 values by max 250 && mod: 5 9 7 0 5 0 1 7 8 9
Whole pot: 175 19 157 90 235 0 191 107 238 89 117

Naturalmente, ci sono alcuni casi in cui il metodo splited max 10 utilizza più byte di mod max 250 ...

Spiegazione:

Sorprendentemente, dover perdere 6/256 values -> 2.34% sembra molto più piccolo di dover eliminare 6/16 values -> 37.5% , ma come si potrebbe ottenere una seconda possibilità per ogni numero:

• dividendo, abbiamo 2 x 62,5% = > 125% di possibilità di ottenere un numero corretto
• usando mod (o dividi per 25), abbiamo solo il 97,65% di possibilità ...

Quindi, per il rendering di 100.000 valori:

./randGen10.sh 100000 | sed 's/^\(.\{74\}\).*$/.../'
 80086 bytes was read for rendering 100000 values by split * max 10: 9 9 2...
102397 bytes was read for rendering 100000 values by max 250 && mod: 3 7 6...
Whole pot: 233 217 46 36 193 182 9 44 187 48 100 172 127 230 157 194 197 1...

Questo sembra corretto: 100'000/97.65% = 102'407 e 100'000/1.25=80'000 .