Je me demandais quelle serait la meilleure façon d'obtenir un bon caractère aléatoire en bash, c'est-à-dire quelle serait la procédure pour obtenir un entier positif aléatoire entre MINet MAXtel que

1. La plage peut être arbitrairement grande (ou au moins, disons, jusqu'à 2 ³² -1);
2. Les valeurs sont réparties uniformément (c.-à-d., Pas de biais);
3. C'est efficace.

Un moyen efficace d'obtenir un caractère aléatoire dans bash est d'utiliser la $RANDOMvariable. Cependant, cela n'échantillonne qu'une valeur comprise entre 0 et 2 ¹⁵ -1, qui peut ne pas être suffisamment grande pour tous les usages. Les gens utilisent généralement un modulo pour le mettre dans la plage qu'ils souhaitent, par exemple,

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

De plus, cela crée un biais, sauf s'il $MAXarrive de diviser 2 ¹⁵ -1 = 32767. Par exemple, si $MINest 0 et $MAXest 9, alors les valeurs 0 à 7 sont légèrement plus probables que les valeurs 8 et 9, comme $RANDOMjamais 32768 ou 32769. Ce biais s'aggrave à mesure que la plage augmente, par exemple, si $MINest 0 et $MAXest 9999, puis les chiffres de 0 à 2767 ont une probabilité de ⁴ / ₃₂₇₆₇ , tandis que les numéros 2768 à 9999 ont seulement une probabilité de ³ / ₃₂₇₆₇ .

Ainsi, bien que la méthode ci-dessus remplisse la condition 3, elle ne remplit pas les conditions 1 et 2.

La meilleure méthode que j'ai trouvée jusqu'à présent pour essayer de satisfaire aux conditions 1 et 2 était d'utiliser la méthode /dev/urandomsuivante:

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

Fondamentalement, il suffit de collecter le caractère aléatoire à partir de /dev/urandom(pourrait envisager d'utiliser à la /dev/randomplace si un générateur de nombres pseudo-aléatoires cryptographiquement fort est souhaité, et si vous avez beaucoup de temps, ou bien peut-être un générateur de nombres aléatoires matériel), supprimez chaque caractère qui n'est pas un chiffre décimal, pliez la sortie à la longueur $MAXet couper les 0 en tête. S'il nous arrivait de n'obtenir que des 0, alors il $rndest vide, alors dans ce cas, réglez rndsur 0. Vérifiez si le résultat est en dehors de notre plage et si oui, répétez. J'ai forcé le "corps" de la boucle while dans le garde ici afin de forcer l'exécution du corps au moins une fois, dans l'esprit d'émuler une do ... whileboucle, car il rndn'est pas défini pour commencer.

Je pense que j'ai rempli les conditions 1 et 2 ici, mais maintenant j'ai foiré la condition 3. C'est un peu lent. Ça prend environ une seconde (dixième de seconde quand j'ai de la chance). En fait, la boucle n'est même pas garantie de se terminer (bien que la probabilité de résiliation converge vers 1 lorsque le temps augmente).

Existe-t-il un moyen efficace d'obtenir des entiers aléatoires non biaisés, dans une plage prédéfinie et potentiellement large, en bash? (Je continuerai d'enquêter lorsque le temps le permettra, mais en attendant, je pensais que quelqu'un ici pourrait avoir une idée sympa!)

Tableau des réponses

1. L'idée la plus fondamentale (et donc portable) est de générer une chaîne de bits aléatoire juste assez longtemps. Il existe différentes façons de générer une chaîne de bits aléatoire, en utilisant la $RANDOMvariable intégrée de bash ou en utilisant odet /dev/urandom(ou /dev/random). Si le nombre aléatoire est supérieur à $MAX, recommencez.

   • Solution bash complète pour des plages arbitraires utilisant soit $RANDOMou/dev/urandom
   • L'idée générale
   • Obtenez une chaîne de bits aléatoire en utilisant soit opensslou odavec /dev/urandom. Embellissez avec tr.
   • Obtenez une chaîne de bits aléatoire en utilisant odavec /dev/random. Embellissez avec awk.

2. Alternativement, il est possible d'utiliser des outils externes.

   • La solution Perl
     • Pro: assez portable, simple, flexible
     • Contra: pas pour les très grands nombres supérieurs à 2 ³² -1
   • La solution Python
     • Pro: simple, flexible, fonctionne même pour les grands nombres
     • Contra: moins portable
   • La solution zsh
     • Pro: bon pour les personnes qui utilisent quand même zsh
     • Contra: probablement encore moins portable

Je vois une autre méthode intéressante d' ici .

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

Celui- ci semble également être une bonne option. Il lit 4 octets du périphérique aléatoire et les formate comme un entier non signé entre 0et 2^32-1.

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

Merci à tous pour vos excellentes réponses. Je me suis retrouvé avec la solution suivante, que je voudrais partager.

Avant d'entrer dans les détails du pourquoi et du comment, voici le tl; dr : mon nouveau script brillant :-)

#!/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 ))

Enregistrez cela dans ~/bin/randet vous avez à votre disposition une fonction aléatoire douce dans bash qui peut échantillonner un entier dans une plage arbitraire donnée. La plage peut contenir des nombres entiers négatifs et positifs et peut avoir une longueur maximale de 2 ⁶⁰ -1:

$ 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

Toutes les idées des autres répondeurs étaient excellentes. Les réponses de terdon , JF Sebastian et jimmij ont utilisé des outils externes pour effectuer la tâche de manière simple et efficace. Cependant, j'ai préféré une vraie solution bash pour une portabilité maximale, et peut-être un peu, simplement par amour pour bash;)

Réponses de Ramesh et l0b0 utilisées /dev/urandomou /dev/randomcombinées avec od. C'est bien, cependant, leurs approches avaient l'inconvénient de ne pouvoir échantillonner que des nombres entiers aléatoires compris entre 0 et 2 ⁸ⁿ -1 pour certains n, car cette méthode échantillonne les octets, c'est-à-dire les chaînes de bits de longueur 8. Ce sont de très gros sauts avec croissant n.

Enfin, la réponse de Falco décrit l'idée générale de la façon dont cela pourrait être fait pour des plages arbitraires (pas seulement des puissances de deux). Fondamentalement, pour une plage donnée {0..max}, nous pouvons déterminer quelle est la puissance suivante de deux, c'est-à-dire exactement combien de bits sont nécessaires pour représenter maxcomme une chaîne de bits. Ensuite, nous pouvons échantillonner juste autant de bits et voir si cet enregistrement, en tant qu'entier, est supérieur à max. Si oui, répétez. Puisque nous échantillonnons autant de bits que nécessaire pour représenter max, chaque itération a une probabilité supérieure ou égale à 50% de réussite (50% dans le pire des cas, 100% dans le meilleur des cas). C'est donc très efficace.

Mon script est essentiellement une implémentation concrète de la réponse de Falco, écrite en bash pur et très efficace car elle utilise les opérations bit à bit intégrées de bash pour échantillonner des chaînes de bits de la longueur souhaitée. Il honore en outre une idée d' Eliah Kagan qui suggère d'utiliser la $RANDOMvariable intégrée en concaténant les chaînes de bits résultant des invocations répétées de $RANDOM. J'ai en fait implémenté à la fois les possibilités d'utilisation /dev/urandomet $RANDOM. Par défaut, le script ci-dessus utilise $RANDOM. (Et ok, si vous utilisez, /dev/urandomnous avons besoin de od et tr , mais ceux-ci sont soutenus par POSIX.)

Alors, comment ça marche?

Avant d'entrer dans le détail, deux observations:

1. Il s'avère que bash ne peut pas gérer des entiers supérieurs à 2 ⁶³ -1. Voir par vous-même:

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

   Il semblerait que bash utilise en interne des entiers signés 64 bits pour stocker des entiers. Donc, à 2 ^63, il «s'enroule» et nous obtenons un entier négatif. Nous ne pouvons donc pas espérer obtenir une plage supérieure à 2 ⁶³ -1 avec la fonction aléatoire que nous utilisons. Bash ne peut tout simplement pas le gérer.

2. Chaque fois que nous voulons échantillonner une valeur dans une plage arbitraire entre minet maxavec éventuellement min != 0, nous pouvons simplement échantillonner une valeur entre 0et à la max-minplace, puis ajouter minau résultat final. Cela fonctionne même si minet peut-être aussi maxsont négatifs , mais nous devons faire attention à échantillonner une valeur entre 0et la valeur absolue de max-min . Ainsi, nous pouvons nous concentrer sur la façon d'échantillonner une valeur aléatoire entre 0et un entier positif arbitraire max. Le reste est facile.

Étape 1: déterminer le nombre de bits nécessaires pour représenter un entier (le logarithme)

Donc, pour une valeur donnée max, nous voulons savoir exactement combien de bits sont nécessaires pour la représenter comme une chaîne de bits. C'est ainsi que plus tard, nous pouvons échantillonner au hasard seulement autant de bits que nécessaire, ce qui rend le script si efficace.

Voyons voir. Comme avec les nbits, nous pouvons représenter jusqu'à la valeur 2 ⁿ -1, alors le nombre nde bits nécessaires pour représenter une valeur arbitraire xest plafond (log ₂ (x + 1)). Donc, nous avons besoin d'une fonction pour calculer le plafond d'un logarithme à la base 2. Elle est plutôt explicite:

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

Nous avons besoin de la condition, n>0donc si elle devient trop grande, s'enroule et devient négative, la boucle est garantie de se terminer.

Étape 2: échantillonner une chaîne binaire aléatoire de longueur n

Les idées les plus portables sont soit d'utiliser /dev/urandom(ou même /dev/randoms'il y a une bonne raison) soit la $RANDOMvariable intégrée de bash . Voyons d'abord comment le faire $RANDOM.

Option A: utilisation $RANDOM

Cela utilise l' idée mentionnée par Eliah Kagan. Fondamentalement, puisque $RANDOMéchantillonne un entier de 15 bits, nous pouvons utiliser $((RANDOM<<15|RANDOM))pour échantillonner un entier de 30 bits. Cela signifie, décaler une première invocation de $RANDOM15 bits vers la gauche et appliquer au niveau du bit ou avec une seconde invocation de $RANDOM, concaténant efficacement deux chaînes de bits échantillonnées indépendamment (ou au moins aussi indépendantes que le bash intégré de $RANDOMva).

Nous pouvons répéter ceci pour obtenir un entier de 45 bits ou 60 bits. Après cela, bash ne peut plus le gérer, mais cela signifie que nous pouvons facilement échantillonner une valeur aléatoire entre 0 et 2 ⁶⁰ -1. Donc, pour échantillonner un entier de n bits, nous répétons la procédure jusqu'à ce que notre chaîne de bits aléatoire, dont la longueur augmente par pas de 15 bits, ait une longueur supérieure ou égale à n. Enfin, nous coupons les bits qui sont trop en décalant de façon appropriée au niveau du bit vers la droite, et nous nous retrouvons avec un entier aléatoire 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) ))
}

Option B: utilisation /dev/urandom

Alternativement, nous pouvons utiliser odet /dev/urandompour échantillonner un entier de n bits. odlira des octets, c'est-à-dire des chaînes de bits de longueur 8. De la même manière que dans la méthode précédente, nous échantillonnons juste autant d'octets que le nombre équivalent de bits échantillonnés est supérieur ou égal à n, et coupons les bits qui sont trop.

Le plus petit nombre d'octets nécessaires pour obtenir au moins n bits est le plus petit multiple de 8 supérieur ou égal à n, c'est-à-dire étage ((n + 7) / 8).

Cela ne fonctionne que jusqu'à 56 bits. L'échantillonnage d'un octet supplémentaire nous donnerait un entier 64 bits, c'est-à-dire une valeur jusqu'à 2 ⁶⁴ -1, que bash ne peut pas gérer.

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

Assembler les morceaux: Obtenez des nombres entiers aléatoires dans des plages arbitraires

Nous pouvons nmaintenant échantillonner des chaînes de bits, mais nous voulons échantillonner des entiers dans une plage de 0à max, uniformément au hasard , où maxpeut être arbitraire, pas nécessairement une puissance de deux. (Nous ne pouvons pas utiliser modulo car cela crée un biais.)

Tout ce pourquoi nous avons essayé si dur d'échantillonner autant de bits que nécessaire pour représenter la valeur max, c'est que nous pouvons maintenant utiliser en toute sécurité (et efficacement) une boucle pour échantillonner de manière répétée une nchaîne de bits -bit jusqu'à ce que nous échantillonnions une valeur qui est inférieure ou égal à max. Dans le pire des cas ( maxest une puissance de deux), chaque itération se termine avec une probabilité de 50%, et dans le meilleur des cas ( maxest une puissance de deux moins un), la première itération se termine avec certitude.

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
}

Envelopper les choses

Enfin, nous voulons échantillonner des entiers entre minet max, où minet maxpeut être arbitraire, voire négatif. Comme mentionné précédemment, cela est désormais trivial.

Mettons tout cela dans un script bash. Faites des analyses d'arguments ... Nous voulons deux arguments minet max, ou un seul argument max, par mindéfaut 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

... et, enfin, pour échantillonner uniformément au hasard une valeur entre minet max, nous échantillonnons un entier aléatoire entre 0et la valeur absolue de max-min, et ajoutons minau résultat final. :-)

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

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

Inspiré par cela , je pourrais essayer d'utiliser dieharder pour tester et comparer ce PRNG, et mettre mes résultats ici. :-)

Peut-il être zsh?

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

Vous pouvez également utiliser des semences avec rand48(seed). Voir man zshmoduleset man 3 erand48pour une description détaillée si vous êtes intéressé.

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

python est disponible sur Redhat, sur les systèmes basés sur Debian.

Si vous voulez un nombre de 0 à (2 ^ n) -1 où n mod 8 = 0, vous pouvez simplement obtenir n / 8 octets /dev/random. Par exemple, pour obtenir la représentation décimale d'un aléatoire, intvous pouvez:

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

Si vous voulez prendre seulement n bits, vous pouvez d'abord prendre des octets de plafond (n / 8) et passer à droite à la quantité souhaitée. Par exemple, si vous voulez 15 bits:

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

Si vous êtes absolument sûr que vous ne vous souciez pas de la qualité du caractère aléatoire et que vous souhaitez garantir un temps d'exécution minimal, vous pouvez utiliser à la /dev/urandomplace de /dev/random. Assurez-vous de savoir ce que vous faites avant d'utiliser /dev/urandom!

En supposant que vous ne vous opposez pas à l'utilisation d'outils externes, cela devrait répondre à vos besoins:

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

Il utilise la randfonction de perl qui prend une limite supérieure comme paramètre. Vous pouvez le régler à votre guise. La proximité de ce phénomène avec le vrai hasard dans la définition mathématique abstraite dépasse le cadre de ce site, mais cela devrait être correct, sauf si vous en avez besoin pour un cryptage extrêmement sensible ou similaire. Peut-être même là-bas, mais je ne m'aventurerai pas.

Vous devriez obtenir le plus proche (2 ^ X) -1 égal ou râpe que votre maximum souhaité et obtenir le nombre de bits. Ensuite, il suffit d'appeler / dev / random plusieurs fois et d'ajouter tous les bits ensemble jusqu'à ce que vous en ayez assez, en tronquant tous les bits qui sont trop. Si le nombre résultant est supérieur à votre répétition max. Dans le pire des cas, vous avez plus de 50% de chances d'obtenir un nombre aléatoire inférieur à votre maximum, donc (dans ce pire cas), vous prendrez deux appels en moyenne.

Votre réponse est intéressante mais assez longue.

Si vous voulez des nombres arbitrairement grands, vous pouvez joindre plusieurs nombres aléatoires dans une aide:

# $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 le problème est un biais, supprimez-le.

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

Joindre ces fonctions ensemble

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