Me he estado preguntando cuál sería la mejor manera de obtener una buena aleatoriedad en bash, es decir, cuál sería un procedimiento para obtener un entero positivo aleatorio entre MINy MAXtal que

1. El rango puede ser arbitrariamente grande (o al menos, digamos, hasta 2 ³² -1);
2. Los valores están distribuidos uniformemente (es decir, sin sesgo);
3. Es eficiente

Una forma eficiente de obtener aleatoriedad en bash es usar la $RANDOMvariable. Sin embargo, esto solo muestra un valor entre 0 y 2 ¹⁵ -1, que puede no ser lo suficientemente grande para todos los propósitos. Las personas generalmente usan un módulo para llevarlo al rango que desean, por ejemplo,

MIN=0
MAX=12345
rnd=$(( $RANDOM % ($MAX + 1 - $MIN) + $MIN ))

Esto, además, crea un sesgo a menos que $MAXocurra dividir 2 ¹⁵ -1 = 32767. Por ejemplo, si $MINes 0 y $MAXes 9, entonces los valores de 0 a 7 son ligeramente más probables que los valores de 8 y 9, ya $RANDOMque nunca serán 32768 o 32769. Este sesgo empeora a medida que aumenta el rango, por ejemplo, si $MINes 0 y $MAXes 9999, a continuación, los números 0 a 2767 tener una probabilidad de ⁴ / ₃₂₇₆₇ , mientras que los números 2768 a 9999 sólo tienen una probabilidad de ³ / ₃₂₇₆₇ .

Entonces, aunque el método anterior cumple la condición 3, no cumple las condiciones 1 y 2.

El mejor método que se me ocurrió hasta ahora para tratar de satisfacer las condiciones 1 y 2 fue usar /dev/urandomlo siguiente:

MIN=0
MAX=1234567890
while
  rnd=$(cat /dev/urandom | tr -dc 0-9 | fold -w${#MAX} | head -1 | sed 's/^0*//;')
  [ -z $rnd ] && rnd=0
  (( $rnd < $MIN || $rnd > $MAX ))
do :
done

Básicamente, solo recopile la aleatoriedad de /dev/urandom(podría considerar usar /dev/randomen su lugar si se desea un generador de números pseudoaleatorios criptográficamente fuerte, y si tiene mucho tiempo, o tal vez un generador de números aleatorios de hardware), elimine cada carácter que no sea un dígito decimal, doble la salida a la longitud de $MAXy corta los ceros iniciales. Si solo obtuvimos 0, entonces $rndestá vacío, por lo que en este caso se establece rnden 0. Compruebe si el resultado está fuera de nuestro rango y, de ser así, repita. Forcé el "cuerpo" del bucle while en la guardia aquí para forzar la ejecución del cuerpo al menos una vez, con el espíritu de emular un do ... whilebucle, ya rndque no está definido para empezar.

Creo que cumplí las condiciones 1 y 2 aquí, pero ahora arruiné la condición 3. Es un poco lento. Toma hasta un segundo más o menos (décima de segundo cuando tengo suerte). En realidad, ni siquiera se garantiza que el ciclo termine (aunque la probabilidad de terminación converge a 1 a medida que aumenta el tiempo).

¿Hay una manera eficiente de obtener enteros aleatorios imparciales, dentro de un rango preespecificado y potencialmente grande, en bash? (Continuaré investigando cuando el tiempo lo permita, ¡pero mientras tanto pensé que alguien aquí podría tener una idea genial!)

Tabla de respuestas

1. La idea más básica (y por lo tanto portátil) es generar una cadena de bits aleatoria el tiempo suficiente. Hay diferentes formas de generar una cadena de bits aleatoria, ya sea usando la $RANDOMvariable incorporada de bash o usando ody /dev/urandom(o /dev/random). Si el número aleatorio es mayor que $MAX, comience de nuevo.

   • Solución completa de bash para rangos arbitrarios utilizando $RANDOMo/dev/urandom
   • La idea general
   • Obtenga una cadena de bits aleatoria con opensslo odcon /dev/urandom. Embellecer con tr.
   • Obtenga una cadena de bits aleatoria odcon /dev/random. Embellecer con awk.

2. Alternativamente, es posible utilizar herramientas externas.

   • La solución de Perl
     • Pro: bastante portátil, simple, flexible
     • Contra: no para números muy grandes por encima de 2 ³² -1
   • La solución de Python
     • Pro: simple, flexible, funciona incluso para grandes cantidades
     • Contra: menos portátil
   • La solución zsh
     • Pro: bueno para las personas que usan zsh de todos modos
     • Contra: probablemente incluso menos portátil

Veo otro método interesante desde aquí .

rand=$(openssl rand 4 | od -DAn)

Esta también parece ser una buena opción. Lee 4 bytes del dispositivo aleatorio y los formatea como un entero sin signo entre 0y 2^32-1.

rand=$(od -N 4 -t uL -An /dev/urandom | tr -d " ")

Gracias a todos por todas sus excelentes respuestas. Terminé con la siguiente solución, que me gustaría compartir.

Antes de entrar en más detalles sobre por qué y cómo, aquí está el tl; dr : mi brillante nuevo script :-)

#!/usr/bin/env bash
#
# Generates a random integer in a given range

# computes the ceiling of log2
# i.e., for parameter x returns the lowest integer l such that 2**l >= x
log2() {
  local x=$1 n=1 l=0
  while (( x>n && n>0 ))
  do
    let n*=2 l++
  done
  echo $l
}

# uses $RANDOM to generate an n-bit random bitstring uniformly at random
#  (if we assume $RANDOM is uniformly distributed)
# takes the length n of the bitstring as parameter, n can be up to 60 bits
get_n_rand_bits() {
  local n=$1 rnd=$RANDOM rnd_bitlen=15
  while (( rnd_bitlen < n ))
  do
    rnd=$(( rnd<<15|$RANDOM ))
    let rnd_bitlen+=15
  done
  echo $(( rnd>>(rnd_bitlen-n) ))
}

# alternative implementation of get_n_rand_bits:
# uses /dev/urandom to generate an n-bit random bitstring uniformly at random
#  (if we assume /dev/urandom is uniformly distributed)
# takes the length n of the bitstring as parameter, n can be up to 56 bits
get_n_rand_bits_alt() {
  local n=$1
  local nb_bytes=$(( (n+7)/8 ))
  local rnd=$(od --read-bytes=$nb_bytes --address-radix=n --format=uL /dev/urandom | tr --delete " ")
  echo $(( rnd>>(nb_bytes*8-n) ))
}

# for parameter max, generates an integer in the range {0..max} uniformly at random
# max can be an arbitrary integer, needs not be a power of 2
rand() {
  local rnd max=$1
  # get number of bits needed to represent $max
  local bitlen=$(log2 $((max+1)))
  while
    # could use get_n_rand_bits_alt instead if /dev/urandom is preferred over $RANDOM
    rnd=$(get_n_rand_bits $bitlen)
    (( rnd > max ))
  do :
  done
  echo $rnd
}

# MAIN SCRIPT

# check number of parameters
if (( $# != 1 && $# != 2 ))
then
  cat <<EOF 1>&2
Usage: $(basename $0) [min] max

Returns an integer distributed uniformly at random in the range {min..max}
min defaults to 0
(max - min) can be up to 2**60-1  
EOF
  exit 1
fi

# If we have one parameter, set min to 0 and max to $1
# If we have two parameters, set min to $1 and max to $2
max=0
while (( $# > 0 ))
do
  min=$max
  max=$1
  shift
done

# ensure that min <= max
if (( min > max ))
then
  echo "$(basename $0): error: min is greater than max" 1>&2
  exit 1
fi

# need absolute value of diff since min (and also max) may be negative
diff=$((max-min)) && diff=${diff#-}

echo $(( $(rand $diff) + min ))

Guarde eso ~/bin/randy tendrá a su disposición una dulce función aleatoria en bash que puede muestrear un número entero en un rango arbitrario dado. El rango puede contener enteros negativos y positivos y puede tener hasta 2 ⁶⁰ -1 de longitud:

$ rand 
Usage: rand [min] max

Returns an integer distributed uniformly at random in the range {min..max}
min defaults to 0
(max - min) can be up to 2**60-1  
$ rand 1 10
9
$ rand -43543 -124
-15757
$ rand -3 3
1
$ for i in {0..9}; do rand $((2**60-1)); done
777148045699177620
456074454250332606
95080022501817128
993412753202315192
527158971491831964
336543936737015986
1034537273675883580
127413814010621078
758532158881427336
924637728863691573

Todas las ideas de los otros que respondieron fueron geniales. Las respuestas de terdon , JF Sebastian y jimmij utilizaron herramientas externas para realizar la tarea de manera simple y eficiente. Sin embargo, preferí una verdadera solución bash para la máxima portabilidad, y tal vez un poco, simplemente por amor a bash;)

Las respuestas de Ramesh y l0b0 utilizadas /dev/urandomo /dev/randomen combinación con od. Eso es bueno, sin embargo, sus enfoques tenían la desventaja de que solo podían muestrear enteros aleatorios en el rango de 0 a 2 ⁸ⁿ -1 para algunos n, ya que este método muestrea bytes, es decir, cadenas de bits de longitud 8. Estos son saltos bastante grandes con creciente n.

Finalmente, la respuesta de Falco describe la idea general de cómo esto podría hacerse para rangos arbitrarios (no solo potencias de dos). Básicamente, para un rango dado {0..max}, podemos determinar cuál es la siguiente potencia de dos, es decir, exactamente cuántos bits se requieren para representar maxcomo una cadena de bits. Luego podemos muestrear tantos bits y ver si este bistring, como entero, es mayor que max. Si es así, repita. Dado que muestreamos tantos bits como sea necesario para representar max, cada iteración tiene una probabilidad mayor o igual al 50% de tener éxito (50% en el peor de los casos, 100% en el mejor de los casos). Entonces esto es muy eficiente.

Mi script es básicamente una implementación concreta de la respuesta de Falco, escrita en puro bash y altamente eficiente, ya que utiliza las operaciones bit a bit integradas de bash para muestrear cadenas de bits de la longitud deseada. También honra una idea de Eliah Kagan que sugiere utilizar la $RANDOMvariable incorporada al concatenar cadenas de bits resultantes de invocaciones repetidas de $RANDOM. De hecho, implementé las posibilidades de uso /dev/urandomy $RANDOM. Por defecto, el script anterior usa $RANDOM. (Y bueno, si usamos /dev/urandom, necesitamos od y tr , pero estos están respaldados por POSIX).

¿Entonces, cómo funciona?

Antes de entrar en esto, dos observaciones:

1. Resulta que bash no puede manejar enteros mayores de 2 ⁶³ -1. Ver por ti mismo:

   $ echo $((2**63-1))
   9223372036854775807
   $ echo $((2**63))
   -9223372036854775808

   Parece que bash usa internamente enteros de 64 bits con signo para almacenar enteros. Entonces, en 2 ⁶³ "se envuelve" y obtenemos un número entero negativo. Por lo tanto, no podemos esperar obtener un rango mayor que 2 ⁶³ -1 con cualquier función aleatoria que usemos. Bash simplemente no puede manejarlo.

2. Siempre que queramos muestrear un valor en un rango arbitrario entre miny maxposiblemente min != 0, simplemente podemos muestrear un valor entre 0y en su max-minlugar y luego agregarlo minal resultado final. Esto funciona incluso si es minposible que maxsea negativo , pero debemos tener cuidado de muestrear un valor entre 0y el valor absoluto de max-min . Entonces, podemos centrarnos en cómo muestrear un valor aleatorio entre 0y un entero positivo arbitrario max. El resto es fácil.

Paso 1: Determine cuántos bits se necesitan para representar un número entero (el logaritmo)

Entonces, para un valor dado max, queremos saber cuántos bits se necesitan para representarlo como una cadena de bits. Esto es para que luego podamos muestrear aleatoriamente solo tantos bits como sean necesarios, lo que hace que el script sea tan eficiente.

Veamos. Como con nbits, podemos representar hasta el valor 2 ⁿ -1, entonces el número nde bits necesarios para representar un valor arbitrario xes el techo (log ₂ (x + 1)). Por lo tanto, necesitamos una función para calcular el techo de un logaritmo a la base 2. Es bastante explicativo:

log2() {
  local x=$1 n=1 l=0
  while (( x>n && n>0 ))
  do
    let n*=2 l++
  done
  echo $l
}

Necesitamos la condición, n>0por lo que si crece demasiado, se envuelve y se vuelve negativa, se garantiza que el ciclo terminará.

Paso 2: muestrear una cadena de bits aleatoria de longitud n

Las ideas más portátiles son usar /dev/urandom(o incluso /dev/randomsi hay una razón sólida) o la $RANDOMvariable incorporada de bash . Veamos $RANDOMprimero cómo hacerlo .

Opción A: usar $RANDOM

Esto utiliza la idea mencionada por Eliah Kagan. Básicamente, dado que $RANDOMmuestrea un entero de 15 bits, podemos usarlo $((RANDOM<<15|RANDOM))para muestrear un entero de 30 bits. Eso significa, desplazar una primera invocación de $RANDOM15 bits hacia la izquierda, y aplicar una invocación a nivel de bit o con una segunda invocación de $RANDOM, concatenando efectivamente dos cadenas de bits muestreadas independientemente (o al menos tan independientes como va el incorporado de bash $RANDOM).

Podemos repetir esto para obtener un entero de 45 bits o 60 bits. Después de que bash ya no puede manejarlo, pero esto significa que podemos muestrear fácilmente un valor aleatorio entre 0 y 2 ⁶⁰ -1. Entonces, para muestrear un número entero de n bits, repetimos el procedimiento hasta que nuestra cadena de bits aleatoria, cuya longitud crece en pasos de 15 bits, tenga una longitud mayor o igual que n. Finalmente, cortamos los bits que son demasiado desplazándonos adecuadamente a la derecha, y terminamos con un entero aleatorio de n bits.

get_n_rand_bits() {
  local n=$1 rnd=$RANDOM rnd_bitlen=15
  while (( rnd_bitlen < n ))
  do
    rnd=$(( rnd<<15|$RANDOM ))
    let rnd_bitlen+=15
  done
  echo $(( rnd>>(rnd_bitlen-n) ))
}

Opción B: uso /dev/urandom

Alternativamente, podemos usar ody /dev/urandompara muestrear un número entero de n bits. odleerá bytes, es decir, cadenas de bits de longitud 8. Del mismo modo que en el método anterior, muestreamos tantos bytes que el número equivalente de bits muestreados es mayor o igual que n, y cortamos los bits que son demasiado.

El número más bajo de bytes necesarios para obtener al menos n bits es el múltiplo más bajo de 8 que es mayor o igual que n, es decir, piso ((n + 7) / 8).

Esto solo funciona con enteros de hasta 56 bits. El muestreo de un byte más nos daría un número entero de 64 bits, es decir, un valor de hasta 2 ⁶⁴ -1, que bash no puede manejar.

get_n_rand_bits_alt() {
  local n=$1
  local nb_bytes=$(( (n+7)/8 ))
  local rnd=$(od --read-bytes=$nb_bytes --address-radix=n --format=uL /dev/urandom | tr --delete " ")
  echo $(( rnd>>(nb_bytes*8-n) ))
}

Poner las piezas juntas: obtener enteros aleatorios en rangos arbitrarios

Nos puede muestrear nbits bitstrings ahora, pero queremos enteros de la muestra en un rango de 0a max, de manera uniforme al azar , donde maxpuede ser arbitrario, no necesariamente una potencia de dos. (No podemos usar el módulo ya que eso crea un sesgo).

El punto principal por el que tratamos de muestrear tantos bits como sea necesario para representar el valor max, es que ahora podemos usar de forma segura (y eficiente) un bucle para muestrear repetidamente una ncadena de bits de un bit hasta que muestreemos un valor que es más bajo o igual a max. En el peor de los casos ( maxes una potencia de dos), cada iteración termina con una probabilidad del 50%, y en el mejor de los casos ( maxes una potencia de dos menos uno), la primera iteración termina con certeza.

rand() {
  local rnd max=$1
  # get number of bits needed to represent $max
  local bitlen=$(log2 $((max+1)))
  while
    # could use get_n_rand_bits_alt instead if /dev/urandom is preferred over $RANDOM
    rnd=$(get_n_rand_bits $bitlen)
    (( rnd > max ))
  do :
  done
  echo $rnd
}

Terminando las cosas

Finalmente, queremos muestrear enteros entre miny max, donde miny maxpueden ser arbitrarios, incluso negativos. Como se mencionó anteriormente, esto ahora es trivial.

Pongámoslo todo en un script bash. Haga algunos análisis de argumentos ... Queremos dos argumentos miny max, o solo un argumento max, donde los minvalores predeterminados sean 0.

# check number of parameters
if (( $# != 1 && $# != 2 ))
then
  cat <<EOF 1>&2
Usage: $(basename $0) [min] max

Returns an integer distributed uniformly at random in the range {min..max}
min defaults to 0
(max - min) can be up to 2**60-1  
EOF
  exit 1
fi

# If we have one parameter, set min to 0 and max to $1
# If we have two parameters, set min to $1 and max to $2
max=0
while (( $# > 0 ))
do
  min=$max
  max=$1
  shift
done

# ensure that min <= max
if (( min > max ))
then
  echo "$(basename $0): error: min is greater than max" 1>&2
  exit 1
fi

... y, finalmente, para muestrear uniformemente al azar un valor entre miny max, muestreamos un entero aleatorio entre 0y el valor absoluto de max-min, y lo sumamos minal resultado final. :-)

diff=$((max-min)) && diff=${diff#-}

echo $(( $(rand $diff) + min ))

Inspirado por esto , podría intentar usar dieharder para probar y comparar este PRNG, y poner mis hallazgos aquí. :-)

¿Puede ser zsh?

max=1000
integer rnd=$(( $(( rand48() )) * $max ))

Es posible que desee utilizar semillas también con rand48(seed). Vea man zshmodulesy man 3 erand48para una descripción detallada si está interesado.

$ python -c 'import random as R; print(R.randint(-3, 5**1234))'

python está disponible en Redhat, sistemas basados ​​en Debian.

Si desea un número del 0 al (2 ^ n) -1 donde n mod 8 = 0 , simplemente puede obtener n / 8 bytes /dev/random. Por ejemplo, para obtener la representación decimal de un azar intpuede:

od --read-bytes=4 --address-radix=n --format=u4 /dev/random | awk '{print $1}'

Si desea tomar solo n bits , primero puede tomar el tope (n / 8) bytes y desplazarse a la derecha a la cantidad que desee. Por ejemplo, si quieres 15 bits:

echo $(($(od --read-bytes=2 --address-radix=n --format=u4 /dev/random | awk '{print $1}') >> 1))

Si está absolutamente seguro de que no le importa la calidad de la aleatoriedad y desea garantizar un tiempo de ejecución mínimo que puede usar en /dev/urandomlugar de /dev/random. ¡Asegúrese de saber lo que está haciendo antes de usar /dev/urandom!

Suponiendo que no se oponga al uso de herramientas externas, esto debería cumplir con sus requisitos:

rand=$(perl -e 'print int(rand(2**32-1))'); 

Está utilizando la randfunción de perl que toma un límite superior como parámetro. Puedes configurarlo como quieras. Qué tan cerca está esto de la aleatoriedad verdadera en la definición matemática abstracta está más allá del alcance de este sitio, pero debería estar bien a menos que lo necesite para un cifrado extremadamente sensible o similar. Quizás incluso allí, pero no me aventuraré a opinar.

Debería obtener el más cercano (2 ^ X) -1 igual o mayor que el máximo deseado y obtener el número de bits. Luego simplemente llame / dev / random varias veces y agregue todos los bits juntos hasta que tenga suficiente, truncando todos los bits que son demasiado. Si el número resultante es mayor que su repetición máxima. En el peor de los casos, tiene una probabilidad superior al 50% de obtener un número aleatorio por debajo de su Máximo, por lo que (en el peor de los casos) atenderá dos llamadas en promedio.

Su respuesta es interesante pero bastante larga.

Si desea números arbitrariamente grandes, puede unir varios números aleatorios en un asistente:

# $1 - number of 'digits' of size base
function random_helper()
{
  base=32768
  random=0
  for((i=0; i<$1; ++i)); do
    let "random+=$RANDOM*($base**$i)"
  done
  echo $random
}

Si el problema es parcial, simplemente elimínelo.

# $1 - min value wanted
# $2 - max value wanted
function random()
{
  MAX=32767
  min=$1
  max=$(($2+1))
  size=$((max-min))
  bias_range=$((MAX/size))
  while
    random=$RANDOM
  [ $((random/size)) -eq $bias_range ]; do :; done
  echo $((random%size+min))
}

Uniendo estas funciones juntas

# $1 - min value wanted
# $2 - max value wanted
# $3 - number of 'digits' of size base
function random()
{
  base=32768
  MAX=$((base**$3-1))
  min=$1
  max=$(($2+1))
  size=$((max-min))
  bias_range=$((MAX/size))
  while
    random=$(random_helper)
  [ $((random/size)) -eq $bias_range ]; do :; done
  echo $((random%size+min))
}