Eu tenho me perguntado qual seria a melhor maneira de obter uma boa aleatoriedade no bash, ou seja, qual seria um procedimento para obter um número inteiro positivo aleatório entre MINe MAXtal que

1. O intervalo pode ser arbitrariamente grande (ou pelo menos, digamos, até 2 ³² -1);
2. Os valores são distribuídos uniformemente (ou seja, sem viés);
3. É eficiente.

Uma maneira eficiente de obter aleatoriedade no bash é usar a $RANDOMvariável No entanto, isso apenas mostra um valor entre 0 e 2 ¹⁵ -1, que pode não ser grande o suficiente para todos os fins. As pessoas normalmente usam um módulo para colocá-lo no intervalo que desejam, por exemplo,

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

Além disso, isso cria um viés, a menos $MAXque divida 2 ¹⁵ -1 = 32767. Por exemplo, se $MINfor 0 e $MAX9, os valores de 0 a 7 são um pouco mais prováveis ​​que os valores 8 e 9, como $RANDOMnunca serão 32768 ou 32769. Esse viés piora à medida que o intervalo aumenta, por exemplo, se $MINé 0 e $MAXé 9999, em seguida, os números 0 a 2767 tem uma probabilidade de ⁴ / ₃₂₇₆₇ , enquanto que os números de 2768 até 9999 só tem uma probabilidade de ³ / ₃₂₇₆₇ .

Portanto, embora o método acima preencha a condição 3, ele não preenche as condições 1 e 2.

O melhor método que eu criei até agora na tentativa de satisfazer as condições 1 e 2 foi usar /dev/urandomo seguinte:

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

Basicamente, basta coletar aleatoriedade de /dev/urandom(pode considerar usar /dev/randomum gerador de números pseudoaleatórios criptograficamente fortes, e se você tiver muito tempo, ou talvez um gerador de números aleatórios de hardware), exclua todos os caracteres que não sejam um dígito decimal, dobre a saída para o comprimento $MAXe corte os zeros à esquerda. Se por acaso obtivemos apenas 0, então $rndestá vazio, portanto, neste caso, defina rndcomo 0. Verifique se o resultado está fora do nosso alcance e, em caso afirmativo, repita. Eu forcei o "corpo" do loop while para a guarda aqui, a fim de forçar a execução do corpo pelo menos uma vez, no espírito de emular um do ... whileloop, já que rndé indefinido para começar.

Acho que cumpri as condições 1 e 2 aqui, mas agora estraguei a condição 3. É meio lento. Leva mais ou menos um segundo (décimo de segundo quando tenho sorte). Na verdade, nem sequer é garantido que o loop termine (embora a probabilidade de término converja para 1 à medida que o tempo aumenta).

Existe uma maneira eficiente de obter números inteiros aleatórios imparciais, dentro de um intervalo pré-especificado e potencialmente grande, no bash? (Continuarei a investigar quando o tempo permitir, mas, enquanto isso, acho que alguém aqui pode ter uma ideia interessante!)

Tabela de respostas

1. A idéia mais básica (e, portanto, portátil) é gerar uma sequência de bits aleatória apenas o tempo suficiente. Existem diferentes maneiras de gerar uma sequência de bits aleatória, usando a $RANDOMvariável interna do bash ou usando ode /dev/urandom(ou /dev/random). Se o número aleatório for maior que $MAX, inicie novamente.

   • Solução completa do bash para intervalos arbitrários usando $RANDOMou/dev/urandom
   • A ideia geral
   • Obtenha bitstring aleatório usando opensslou odcom /dev/urandom. Embelezar com tr.
   • Obtenha bitstring aleatório usando odwith /dev/random. Embelezar com awk.

2. Como alternativa, é possível usar ferramentas externas.

   • A solução Perl
     • Pro: bastante portátil, simples, flexível
     • Contra: não para números muito grandes acima de 2 ³² -1
   • A solução Python
     • Pro: simples, flexível, funciona mesmo para grandes números
     • Contra: menos portátil
   • A solução zsh
     • Pro: bom para quem usa o zsh de qualquer maneira
     • Contra: provavelmente ainda menos portátil

Eu vejo outro método interessante daqui .

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

Este também parece ser uma boa opção. Ele lê 4 bytes do dispositivo aleatório e os formata como um número inteiro não assinado entre 0e 2^32-1.

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

Obrigado a todos pelas ótimas respostas. Acabei com a seguinte solução, que gostaria de compartilhar.

Antes de entrar em mais detalhes sobre os porquês e comos, aqui está o tl; dr : meu brilhante novo 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 ))

Salve isso ~/bin/rande você terá à sua disposição uma função aleatória doce no bash que pode amostrar um número inteiro em um determinado intervalo arbitrário. O intervalo pode conter números inteiros negativos e positivos e pode ter até 2 ⁶⁰ -1 de comprimento:

$ 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 as idéias dos outros respondentes foram ótimas. As respostas de terdon , JF Sebastian e jimmij usaram ferramentas externas para executar a tarefa de maneira simples e eficiente. No entanto, eu preferi uma solução verdadeira do bash para máxima portabilidade e, talvez um pouco, simplesmente por amor ao bash;)

As respostas de Ramesh e l0b0 usadas /dev/urandomou /dev/randomem combinação com od. Isso é bom, no entanto, suas abordagens tiveram a desvantagem de poder apenas amostrar números inteiros aleatórios no intervalo de 0 a 2 ⁸ⁿ -1 para alguns n, já que esse método faz uma amostra de bytes, ou seja, bitstrings de comprimento 8. Esses são saltos bastante grandes com crescente n.

Finalmente, a resposta de Falco descreve a idéia geral de como isso pode ser feito para intervalos arbitrários (não apenas para poderes de dois). Basicamente, para um determinado intervalo {0..max}, podemos determinar qual é a próxima potência de dois, ou seja, exatamente quantos bits são necessários para representar maxcomo uma cadeia de bits . Em seguida, podemos amostrar apenas esses bits e ver se esse bistring, como um inteiro, é maior que max. Se sim, repita. Como amostramos o número de bits necessário para representar max, cada iteração tem uma probabilidade maior ou igual a 50% de êxito (50% no pior caso, 100% no melhor caso). Então, isso é muito eficiente.

Meu script é basicamente uma implementação concreta da resposta de Falco, escrita em bash puro e altamente eficiente, pois usa as operações bit a bit internas do bash para obter amostras de strings de bit do comprimento desejado. Além disso, ele homenageia uma idéia de Eliah Kagan que sugere o uso da $RANDOMvariável incorporada concatenando as cadeias de bits resultantes de repetidas invocações de $RANDOM. Na verdade, eu implementei as possibilidades de usar /dev/urandome $RANDOM. Por padrão, o script acima usa $RANDOM. (E ok, se estiver usando /dev/urandom, precisamos de od e tr , mas estes são suportados pelo POSIX.)

Então, como isso funciona?

Antes de entrar nisso, duas observações:

1. Acontece que o bash não pode manipular números inteiros maiores que 2 ⁶³ -1. Veja por si mesmo:

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

   Parece que o bash usa internamente números inteiros assinados de 64 bits para armazenar números inteiros. Então, em 2 ^63, ele "se envolve" e obtemos um número inteiro negativo. Portanto, não podemos esperar obter um intervalo maior que 2 ⁶³ -1 com qualquer função aleatória que usamos. O Bash simplesmente não consegue lidar com isso.

2. Sempre que quisermos amostrar um valor em um intervalo arbitrário entre mine maxcom min != 0, possivelmente , podemos simplesmente amostrar um valor entre 0e ao max-mininvés disso e depois adicionar minao resultado final. Isso funciona mesmo que mine possivelmente também maxseja negativo , mas precisamos ter cuidado para amostrar um valor entre 0e o valor absoluto de max-min . Portanto, podemos nos concentrar em como amostrar um valor aleatório entre 0e um número inteiro positivo arbitrário max. O resto é fácil.

Etapa 1: determinar quantos bits são necessários para representar um número inteiro (o logaritmo)

Portanto, para um determinado valor max, queremos saber quantos bits são necessários para representá-lo como uma cadeia de bits. Isso é para que mais tarde possamos amostrar aleatoriamente apenas quantos bits forem necessários, o que torna o script tão eficiente.

Vamos ver. Como com nbits, podemos representar até o valor 2 ⁿ -1, então o número nde bits necessários para representar um valor arbitrário xé teto (log ₂ (x + 1)). Portanto, precisamos de uma função para calcular o teto de um logaritmo para a base 2. É bastante auto-explicativo:

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

Precisamos da condição n>0para que, se ela crescer muito, contornar e se tornar negativa, o loop seja garantido para terminar.

Etapa 2: experimente um bitstring aleatório de comprimento n

As idéias mais portáteis são usar /dev/urandom(ou mesmo /dev/randomse houver um motivo forte) ou a $RANDOMvariável interna do bash . Vamos ver como fazer isso $RANDOMprimeiro.

Opção A: Usando $RANDOM

Isso usa a idéia mencionada por Eliah Kagan. Basicamente, uma vez que $RANDOMcria um número inteiro de 15 bits, podemos usar $((RANDOM<<15|RANDOM))para amostrar um número inteiro de 30 bits. Isso significa que, desloque uma primeira invocação de $RANDOM15 bits para a esquerda e aplique uma invocação bit a bit ou com uma segunda invocação $RANDOM, concaturando efetivamente duas seqüências de bits com amostragem independente (ou pelo menos tão independente quanto o built-in do bash $RANDOM).

Podemos repetir isso para obter um número inteiro de 45 ou 60 bits. Depois que o bash não aguenta mais, mas isso significa que podemos facilmente amostrar um valor aleatório entre 0 e 2 ⁶⁰ -1. Portanto, para amostrar um número inteiro de n bits, repetimos o procedimento até que nossa cadeia de bits aleatória, cujo comprimento cresça em etapas de 15 bits, tenha um comprimento maior ou igual a n. Por fim, cortamos os bits que são demais, deslocando-se bit a bit apropriadamente para a direita e terminamos com um número inteiro aleatório 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) ))
}

Opção B: Usando /dev/urandom

Como alternativa, podemos usar ode /dev/urandomamostrar um número inteiro de n bits. odlerá bytes, isto é, cadeias de bits de comprimento 8. Da mesma forma que no método anterior, coletamos tantos bytes que o número equivalente de bits amostrados é maior ou igual a n e eliminamos os bits que são demais.

O menor número de bytes necessários para obter pelo menos n bits é o múltiplo mais baixo de 8 que é maior ou igual a n, ou seja, floor ((n + 7) / 8).

Isso funciona apenas com números inteiros de 56 bits. A amostragem de mais um byte nos daria um número inteiro de 64 bits, ou seja, um valor de até 2 ⁶⁴ -1, que o bash não pode manipular.

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) ))
}

Juntando as peças: obtenha números aleatórios em intervalos arbitrários

Podemos provar nbits bitstrings agora, mas queremos inteiros de amostra em um intervalo de 0para max, uniformemente ao acaso , onde maxpode ser arbitrária, não necessariamente uma potência de dois. (Não podemos usar o módulo, pois isso cria um viés.)

O ponto principal por que tentamos tanto amostrar quantos bits são necessários para representar o valor maxé que agora podemos usar com segurança (e eficientemente) um loop para amostrar repetidamente uma ncadeia de bits de bits até obtermos um valor menor ou igual a max. No pior caso ( maxé um poder de dois), cada iteração termina com uma probabilidade de 50% e, no melhor dos casos ( maxé um poder de dois menos um), a primeira iteração termina com 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
}

Embrulhando as coisas

Finalmente, queremos amostrar números inteiros entre mine max, onde mine maxpodem ser arbitrários e até negativos. Como mencionado anteriormente, isso agora é trivial.

Vamos colocar tudo em um script bash. Faça algum argumento para analisar coisas ... Queremos dois argumentos mine max, ou apenas um argumento max, onde o minpadrão é 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

... e, finalmente, para amostrar uniformemente aleatoriamente um valor entre mine max, amostramos um número inteiro aleatório entre 0e o valor absoluto de max-mine adicionamos minao resultado final. :-)

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

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

Inspirado por isso , posso tentar usar o dieharder para testar e comparar esse PRNG e colocar minhas conclusões aqui. :-)

Pode ser zsh?

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

Você pode querer usar sementes também rand48(seed). Veja man zshmodulese man 3 erand48para uma descrição detalhada, se estiver interessado.

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

python está disponível em sistemas baseados no Debian, Redhat.

Se você deseja um número de 0 a (2 ^ n) -1, onde n mod 8 = 0, você pode simplesmente obter n / 8 bytes /dev/random. Por exemplo, para obter a representação decimal de uma forma aleatória, intvocê pode:

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

Se você deseja obter apenas n bits, pode primeiro pegar bytes de teto (n / 8) e mudar para a quantidade desejada. Por exemplo, se você quiser 15 bits:

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

Se você tem certeza absoluta de que não se importa com a qualidade da aleatoriedade e deseja garantir um tempo de execução mínimo, pode usar em /dev/urandomvez de /dev/random. Certifique-se de saber o que está fazendo antes de usar /dev/urandom!

Supondo que você não se oponha ao uso de ferramentas externas, isso deve atender aos seus requisitos:

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

Ele está usando a randfunção perl, que aceita um limite superior como parâmetro. Você pode configurá-lo para o que quiser. O quão perto isso está da verdadeira aleatoriedade na definição matemática abstrata está além do escopo deste site, mas deve ser bom, a menos que você precise para criptografia extremamente sensível ou algo semelhante. Talvez até lá, mas não vou arriscar uma opinião.

Você deve obter o mais próximo (2 ^ X) -1 igual ou maior que o máximo desejado e obter o número de bits. Em seguida, basta chamar / dev / random várias vezes e anexar todos os bits até que você tenha o suficiente, truncando todos os bits que são demais. Se o número resultante for maior que sua repetição máxima. Na pior das hipóteses, você tem mais de 50% de chance de obter um número aleatório abaixo do seu Máximo; portanto, para a pior das hipóteses, você atenderá duas chamadas em média.

Sua resposta é interessante, mas bastante longa.

Se você quiser números arbitrariamente grandes, poderá juntar vários números aleatórios em um auxiliar:

# $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
}

Se o problema for tendencioso, remova-o.

# $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))
}

Unindo essas funções

# $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))
}