¿La forma correcta de obtener un número de 0-9 de un byte aleatorio?

Hay dos formas genéricas de producir un dígito aleatorio "lo suficientemente imparcial".

El primer método es hacer un bucle si el byte no estaba en el rango correcto. Es decir:

• Obtenga el siguiente byte aleatorio b .
• Si b está en el rango 0..249, devuelva b mod 10.
• Loop.

Este método puede consumir un número ilimitado de bytes aleatorios, pero es perfectamente imparcial y es muy poco probable que requiera repetición de bucles muchas veces. Eso es lo que Random.nextInt (int) se aplica el método estándar (aunque con palabras de 32 bits en lugar de bytes).

El segundo método es utilizar como valor de origen, no un byte sino una palabra lo suficientemente grande. Por ejemplo, use 20 bytes, interprételos como un entero x en el rango 0..2 ¹⁶⁰ -1 y devuelva x mod 10. De esta manera, el sesgo sigue ahí, pero puede hacerse arbitrariamente pequeño, hasta el punto de que ya no importa. Esto es computacionalmente costoso (más que el primer método) pero tiene la ventaja de que siempre requiere el mismo número de bytes de entrada, lo que puede ser útil en algunas situaciones específicas (por ejemplo, fugas de canales laterales).

Byte de división, para representar varios números

Como el generador aleatorio puede ser algo caro , la forma más eficiente es cortar cada byte (0-255) en dos partes (0-15), antes de eliminar fuera del límite valores:

Hay una pequeña muestra que utiliza 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

Haciendo un tipo de comparación:

Como respuesta al comentario de @ AndreasKrey, hay una pequeña demostración, donde trato de obtener 10 números entre 0 y 9:

Uso el mismo pot (de números aleatorios) en ambos métodos:

• Dividir el byte en dos partes y filtrar un número mayor que 9
• Bajando números mayores a 249 y usando 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[@]}

Esto podría ejecutarse varias veces:

./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

Por supuesto, hay algunos casos en los que el método splited max 10 usa más bytes que mod max 250 ...

Explicación:

Sorprendentemente, tener que eliminar 6/256 values -> 2.34% parece mucho más pequeño que tener que eliminar 6/16 values -> 37.5% , pero como podríamos obtener una segunda oportunidad para cada número:

• al dividir, tenemos 2 x 62.5% = > 125% de posibilidades de obtener un número correcto
• al usar mod (o dividir por 25), solo tenemos 97.65% de posibilidades ...

Por lo tanto, para representar 100'000 valores:

./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...

Esto parece correcto: 100'000/97.65% = 102'407 y 100'000/1.25=80'000 .