Ich habe mich gefragt , was der beste Weg wäre, zu bekommen gute Zufälligkeit in der Bash, das heißt, was für ein Verfahren , um eine zufällige positive ganze Zahl zu erhalten zwischen wäre MINund MAXso , dass

1. Der Bereich kann beliebig groß sein (oder zumindest bis zu 2 ³² -1);
2. Die Werte sind gleichmäßig verteilt (dh ohne Verzerrung).
3. Es ist effizient.

Ein effizienter Weg, Zufälligkeit in Bash zu erhalten, ist die Verwendung der $RANDOMVariablen. Dies tastet jedoch nur einen Wert zwischen 0 und 2 ¹⁵ -1 ab, der möglicherweise nicht für alle Zwecke groß genug ist. Leute benutzen normalerweise ein Modulo, um es in den Bereich zu bringen, den sie wollen, zB

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

Dies erzeugt zusätzlich eine Verzerrung, wenn nicht $MAXzufällig 2 ¹⁵ -1 = 32767 geteilt wird. Wenn z. B. $MIN0 und $MAX9 sind, sind die Werte 0 bis 7 etwas wahrscheinlicher als die Werte 8 und 9, wie dies $RANDOMniemals bei 32768 oder 32769 der Fall ist. Diese Abweichung wird mit zunehmendem Bereich schlimmer, z. B. wenn $MIN0 und 9 $MAXsind 9999, dann werden die Zahlen von 0 bis 2767 haben eine Wahrscheinlichkeit von ⁴ / ₃₂₇₆₇ , während die Zahlen 2768 bis 9999 nur eine Wahrscheinlichkeit von haben ³ / ₃₂₇₆₇ .

Während das obige Verfahren die Bedingung 3 erfüllt, erfüllt es die Bedingungen 1 und 2 nicht.

Die beste Methode, die ich bisher gefunden habe, um die Bedingungen 1 und 2 zu erfüllen, war die /dev/urandomfolgende:

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

Sammeln Sie einfach die Zufälligkeit von /dev/urandom(verwenden Sie diese Option möglicherweise, /dev/randomwenn ein kryptografisch starker Pseudozufallszahlengenerator gewünscht wird, und wenn Sie viel Zeit haben, oder einen Hardware-Zufallszahlengenerator), und löschen Sie jedes Zeichen, das keine Dezimalstelle ist die Ausgabe auf die Länge der $MAXführenden Nullen und abschneiden. Wenn wir nur zufällig 0'en bekommen dann $rndleer ist , so dass in diesem Fall Satz rndzu 0. Überprüfen Sie, ob das Ergebnis außerhalb unseres Bereichs liegt, und wiederholen Sie den Vorgang, wenn dies der Fall ist. Ich habe hier den "Körper" der while-Schleife in die Wache gezwungen, um die Ausführung des Körpers mindestens einmal zu erzwingen, im Geiste, eine do ... whileSchleife zu emulieren , da dies zunächst rndundefiniert ist.

Ich glaube, ich habe hier die Bedingungen 1 und 2 erfüllt, aber jetzt habe ich Bedingung 3 durcheinander gebracht. Es ist ein bisschen langsam. Dauert ungefähr eine Sekunde (Zehntelsekunde, wenn ich Glück habe). Tatsächlich ist nicht einmal die Beendigung der Schleife garantiert (obwohl die Wahrscheinlichkeit der Beendigung mit zunehmender Zeit gegen 1 konvergiert).

Gibt es einen effizienten Weg, um unbefangene Zufallszahlen innerhalb eines vorgegebenen und potenziell großen Bereichs in Bash zu erhalten? (Ich werde weiter nachforschen, wenn es die Zeit erlaubt, aber in der Zwischenzeit dachte ich, dass jemand hier eine coole Idee haben könnte!)

Tabelle der Antworten

1. Die einfachste (und damit tragbare) Idee ist es, einen zufälligen Bitstring gerade lang genug zu generieren. Es gibt verschiedene Möglichkeiten, einen zufälligen Bitstring zu generieren, entweder mit der eingebauten $RANDOMVariablen von bash oder mit odund /dev/urandom(oder /dev/random). Wenn die Zufallszahl größer als ist $MAX, beginnen Sie erneut.

   • Komplette Bash-Lösung für beliebige Bereiche mit entweder $RANDOModer/dev/urandom
   • Die allgemeine Idee
   • Holen Sie sich zufällige Bitfolge entweder mit openssloder odmit /dev/urandom. Verschönern Sie mit tr.
   • Holen Sie sich zufällige Bitstring odmit /dev/random. Verschönern Sie mit awk.

2. Alternativ können externe Tools verwendet werden.

   • Die Perl-Lösung
     • Pro: ziemlich portabel, einfach, flexibel
     • Contra: nicht für sehr große Zahlen über 2 ³² -1
   • Die Python-Lösung
     • Pro: einfach, flexibel, funktioniert auch bei großen Stückzahlen
     • Contra: weniger tragbar
   • Die zsh-Lösung
     • Pro: gut für Leute, die sowieso zsh benutzen
     • Contra: wahrscheinlich noch weniger portabel

Ich sehe eine andere interessante Methode von hier .

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

Dies scheint auch eine gute Option zu sein. Es liest 4 Bytes vom Zufallsgerät und formatiert sie als vorzeichenlose Ganzzahl zwischen 0und 2^32-1.

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

Vielen Dank für all Ihre tollen Antworten. Am Ende habe ich die folgende Lösung gefunden, die ich mitteilen möchte.

Bevor ich in näher über das Wie und Warum gehen, hier ist die tl; dr : mein glänzendes neues Skript :-)

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

Speichern Sie das in ~/bin/randund Sie haben bei Ihrer Verfügbarkeit eine süße Zufallsfunktion in der Bash, die eine ganze Zahl in einem beliebigen Bereich abtasten kann. Der Bereich kann negative und positive ganze Zahlen enthalten und bis zu 2 ⁶⁰ -1 lang sein:

$ 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

Alle Ideen der anderen Antwortenden waren großartig. Die Antworten von terdon , JF Sebastian und jimmij verwendeten externe Tools, um die Aufgabe auf einfache und effiziente Weise zu erledigen. Ich bevorzuge jedoch eine echte bash-Lösung für maximale Portabilität und vielleicht ein bisschen, einfach aus Liebe zu bash;)

Ramesh 's und l0b0 ' s Antworten verwendet /dev/urandomoder /dev/randomin Kombination mit od. Das ist gut, aber ihre Ansätze hatten den Nachteil, dass sie nur zufällige ganze Zahlen im Bereich von 0 bis 2 ⁸ⁿ -1 für einige n abtasten konnten, da diese Methode Bytes abtastet, dh Bitstrings der Länge 8. Dies sind ziemlich große Sprünge mit zunehmende n.

Schließlich beschreibt Falcos Antwort die allgemeine Idee, wie dies für beliebige Bereiche (nicht nur Zweierpotenzen) erfolgen könnte. Im Grunde genommen für einen bestimmten Bereich {0..max}, können wir bestimmen , was die nächste Zweierpotenz ist, das heißt, genau wie viele Bits erforderlich sind , zu repräsentieren maxals Bitstring. Dann können wir nur so viele Bits abtasten und feststellen, ob diese Verzerrung als Ganzzahl größer als ist max. Wenn ja, wiederholen. Da wir nur so viele Bits abtasten, wie zur Darstellung erforderlich sind max, hat jede Iteration eine Wahrscheinlichkeit größer oder gleich 50% des Erfolgs (50% im schlimmsten Fall, 100% im besten Fall). Das ist also sehr effizient.

Mein Skript ist im Grunde eine konkrete Implementierung von Falcos Antwort, die in reinem Bash geschrieben und hocheffizient ist, da es die eingebauten bitweisen Operationen von Bash verwendet, um Bitstrings der gewünschten Länge abzutasten. Darüber hinaus wird eine Idee von Eliah Kagan$RANDOM gewürdigt , die vorschlägt, die eingebaute Variable zu verwenden, indem Bitfolgen verkettet werden, die aus wiederholten Aufrufen von $RANDOM. Ich habe tatsächlich sowohl die Verwendungsmöglichkeiten /dev/urandomals auch implementiert $RANDOM. Standardmäßig wird das obige Skript verwendet $RANDOM. (Und ok, wenn /dev/urandomwir od und tr brauchen , werden diese von POSIX unterstützt.)

Wie funktioniert es?

Bevor ich darauf eingehe, zwei Beobachtungen:

1. Es stellt sich heraus, dass bash keine Ganzzahlen größer als 2 ⁶³ -1 verarbeiten kann. Überzeugen Sie sich selbst:

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

   Es scheint, dass Bash intern signierte 64-Bit-Ganzzahlen verwendet, um Ganzzahlen zu speichern. Bei 2 ⁶³ "dreht sich alles um" und wir erhalten eine negative ganze Zahl. Wir können also nicht hoffen, mit einer beliebigen Zufallsfunktion einen größeren Bereich als 2 ⁶³ -1 zu erhalten. Bash kommt einfach nicht damit klar.

2. Wann immer wir einen Wert in einem beliebigen Bereich zwischen minund maxmit abtasten möchten min != 0, können wir einfach einen Wert zwischen 0und max-minabtasten und dann minzum Endergebnis hinzufügen . Dies funktioniert auch , wenn minund möglicherweise auch maxsind negativ , aber wir müssen vorsichtig sein , einen Wert zwischen Probe 0und den absoluten Wert max-min . Dann können wir uns darauf konzentrieren, wie ein zufälliger Wert zwischen 0und einer beliebigen positiven ganzen Zahl abgetastet wird max. Der Rest ist einfach.

Schritt 1: Bestimmen Sie, wie viele Bits benötigt werden, um eine Ganzzahl (den Logarithmus) darzustellen

Für einen bestimmten Wert maxmöchten wir wissen, wie viele Bits erforderlich sind, um ihn als Bitfolge darzustellen. Dies ist so, dass wir später nur so viele Bits wie nötig zufällig abtasten können, was das Skript so effizient macht.

Wir werden sehen. Da mit nBits bis zum Wert 2 ⁿ -1 dargestellt werden kann, ist die Anzahl nder Bits, die zur Darstellung eines beliebigen Werts erforderlich sind, die xObergrenze (log ₂ (x + 1)). Wir brauchen also eine Funktion, um die Obergrenze eines Logarithmus zur Basis 2 zu berechnen. Es ist ziemlich selbsterklärend:

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

Wir brauchen die Bedingung, n>0damit die Schleife garantiert endet, wenn sie zu groß wird, sich umgibt und negativ wird.

Schritt 2: Wählen Sie eine zufällige Bitfolge mit einer Länge aus n

Die tragbarsten Ideen sind, entweder die eingebaute Variable von bash zu verwenden /dev/urandom(oder auch /dev/randomwenn es einen starken Grund gibt) $RANDOM. Schauen wir uns zuerst an, wie es geht $RANDOM.

Option A: Verwenden von $RANDOM

Dies basiert auf der Idee von Eliah Kagan. Grundsätzlich $RANDOMkönnen wir , da eine 15-Bit-Ganzzahl abgetastet wird, $((RANDOM<<15|RANDOM))eine 30-Bit-Ganzzahl abtasten. Verschieben Sie also einen ersten Aufruf $RANDOMum 15 Bit nach links und wenden Sie einen bitweisen oder einen zweiten Aufruf an $RANDOM, um zwei unabhängig abgetastete Bitstrings effektiv zu verketten (oder zumindest so unabhängig, wie es in bash integriert ist $RANDOM).

Wir können dies wiederholen, um eine 45-Bit- oder 60-Bit-Ganzzahl zu erhalten. Nach dieser Bash kann es nicht mehr verarbeitet werden, aber dies bedeutet, dass wir leicht einen Zufallswert zwischen 0 und 2 ⁶⁰ -1 abtasten können. Um eine n-Bit-Ganzzahl abzutasten, wiederholen wir die Prozedur, bis unsere zufällige Bitfolge, deren Länge in 15-Bit-Schritten zunimmt, eine Länge größer oder gleich n hat. Schließlich schneiden wir die zu großen Bits ab, indem wir sie entsprechend bitweise nach rechts verschieben. Am Ende erhalten wir eine n-Bit-Zufallszahl.

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: Verwenden von /dev/urandom

Alternativ können wir odund verwenden /dev/urandom, um eine n-Bit-Ganzzahl abzutasten. odBytes, dh Bitstrings der Länge 8, werden gelesen. Ähnlich wie bei der vorherigen Methode werden nur so viele Bytes abgetastet, dass die äquivalente Anzahl der abgetasteten Bits größer oder gleich n ist, und die zu großen Bits werden abgeschnitten.

Die niedrigste Anzahl von Bytes, die benötigt wird, um mindestens n Bits zu erhalten, ist das niedrigste Vielfache von 8, das größer oder gleich n ist, dh Floor ((n + 7) / 8).

Dies funktioniert nur mit 56-Bit-Ganzzahlen. Wenn Sie ein weiteres Byte abtasten, erhalten Sie eine 64-Bit-Ganzzahl, dh einen Wert bis zu 2 ⁶⁴ -1, den die Bash nicht verarbeiten kann.

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

Zusammenfügen der Teile: Ermitteln Sie zufällige ganze Zahlen in beliebigen Bereichen

Wir können probieren njetzt -Bit bitstrings, aber wir wollen Probe ganze Zahlen in einem Bereich von 0bis max, gleichmäßig zufällig , wo maxwillkürlich kann, die nicht unbedingt eine Zweierpotenz. (Wir können Modulo nicht verwenden, da dies zu einer Verzerrung führt.)

Der springende Punkt, warum wir uns so sehr bemüht haben, nur so viele Bits abzutasten, wie zur Darstellung des Werts erforderlich sind max, ist, dass wir jetzt eine Schleife sicher (und effizient) zum wiederholten nAbtasten eines Bitstrings mit -bit verwenden können, bis wir einen niedrigeren Wert abtasten oder gleich max. Im ungünstigsten Fall ( maxZweierpotenz) endet jede Iteration mit einer Wahrscheinlichkeit von 50%, und im besten Fall ( maxZweierpotenz minus Eins) endet die erste Iteration mit Sicherheit.

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
}

Dinge einpacken

Schließlich wollen wir ganze Zahlen zwischen minund max, wo minund maxkann beliebig sein, auch negativ abtasten. Wie bereits erwähnt, ist dies jetzt trivial.

Lassen Sie uns alles in ein Bash-Skript schreiben. Führe ein paar Argumente aus, die analysiert werden ... Wir wollen zwei Argumente minund maxoder nur ein Argument max, wobei der minStandardwert ist 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

... und schließlich, um einen Wert zwischen minund gleichmäßig zufällig abzutasten max, tasten wir eine zufällige ganze Zahl zwischen 0und dem absoluten Wert von max-minund addieren minzum Endergebnis. :-)

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

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

Davon inspiriert , könnte ich versuchen, diesen PRNG mit Dieharder zu testen und zu vergleichen und meine Erkenntnisse hier einzubringen . :-)

Kann es zsh sein?

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

Sie können auch Samen mit verwenden rand48(seed). Siehe man zshmodulesund man 3 erand48für detaillierte Beschreibung bei Interesse.

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

python ist auf Redhat-basierten Debian-Systemen verfügbar.

Wenn Sie eine Zahl von 0 bis (2 ^ n) -1 wollen, wobei n mod 8 = 0 ist , können Sie einfach n / 8 Bytes abrufen /dev/random. Um beispielsweise die dezimale Darstellung eines Zufalls zu erhalten, können intSie:

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

Wenn Sie nur n Bits verwenden möchten, können Sie zuerst die Obergrenze (n / 8) Bytes verwenden und nach rechts verschieben, um den gewünschten Wert festzulegen. Zum Beispiel, wenn Sie 15 Bits möchten:

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

Wenn Sie absolut sicher sind, dass Ihnen die Qualität der Zufälligkeit egal ist und Sie eine minimale Laufzeit garantieren möchten, die Sie /dev/urandomstattdessen verwenden können /dev/random. Stellen Sie sicher, dass Sie wissen, was Sie tun, bevor Sie es verwenden /dev/urandom!

Vorausgesetzt, Sie haben keine Einwände gegen die Verwendung externer Tools, sollte dies Ihre Anforderungen erfüllen:

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

Es wird die Perl- randFunktion verwendet, die eine Obergrenze als Parameter verwendet. Sie können es nach Belieben einstellen. Wie nahe dies an der wahren Zufälligkeit in der abstrakten mathematischen Definition liegt, würde den Rahmen dieser Website sprengen, sollte aber in Ordnung sein, es sei denn, Sie benötigen es für äußerst sensible Verschlüsselung oder dergleichen. Vielleicht sogar dort, aber ich werde es nicht wagen, eine Meinung zu äußern.

Sie sollten das nächste (2 ^ X) -1 erhalten, das gleich oder größer als Ihr gewünschtes Maximum ist, und die Anzahl der Bits erhalten. Rufen Sie dann einfach / dev / random mehrmals auf und fügen Sie alle Bits zusammen, bis Sie genug haben, und kürzen Sie alle Bits, die zu viel sind. Wenn die resultierende Zahl größer als Ihre maximale Wiederholung ist. Im schlimmsten Fall haben Sie eine Chance von mehr als 50%, eine Zufallszahl unter Ihr Maximum zu bringen. In diesem schlimmsten Fall nehmen Sie durchschnittlich zwei Anrufe entgegen.

Ihre Antwort ist interessant, aber ziemlich lang.

Wenn Sie beliebig große Zahlen möchten, können Sie mehrere Zufallszahlen zu einem Helfer zusammenfügen:

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

Wenn das Problem eine Verzerrung ist, entfernen Sie es einfach.

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

Zusammenführen dieser Funktionen

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