Zastanawiałem się, jaki byłby najlepszy sposób na uzyskanie dobrej losowości w bashu, tj. Jaka byłaby procedura uzyskania losowej dodatniej liczby całkowitej między MINi MAXtaka, że

1. Zakres może być dowolnie duży (lub, powiedzmy, do 2 ³² -1);
2. Wartości są równomiernie rozłożone (tzn. Bez uprzedzeń);
3. Jest wydajny.

Skutecznym sposobem na uzyskanie losowości w bash jest użycie $RANDOMzmiennej. Jednak to tylko próbki wartości od 0 do 2 ¹⁵ -1, które mogą nie być wystarczająco duże do wszystkich celów. Ludzie zwykle używają modulo, aby uzyskać pożądany zakres, np.

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

To dodatkowo tworzy błąd, chyba że $MAXpodzielisz 2 ¹⁵ -1 = 32767. Np. Jeśli $MINwynosi 0 i $MAXwynosi 9, wówczas wartości od 0 do 7 są nieco bardziej prawdopodobne niż wartości 8 i 9, ponieważ $RANDOMnigdy nie będzie to 32768 lub 32769. Ta tendencja pogarsza się wraz ze wzrostem zakresu, np. Jeśli $MINwynosi 0 i $MAXwynosi 9999, a liczba od 0 do 2767 mają prawdopodobieństwo ⁴ / ₃₂₇₆₇ , a liczba 2768 do 9999 mają tylko prawdopodobieństwo ³ / ₃₂₇₆₇ .

Tak więc, chociaż powyższa metoda spełnia warunek 3, nie spełnia warunków 1 i 2.

Najlepszą metodą, jaką do tej pory wymyśliłem, próbując spełnić warunki 1 i 2, było /dev/urandom:

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

Zasadniczo po prostu zbieraj losowość od /dev/urandom( /dev/randommożesz rozważyć użycie zamiast tego, jeśli pożądany jest silny kryptograficznie generator liczb pseudolosowych i jeśli masz dużo czasu, a może sprzętowy generator liczb losowych), usuń każdy znak, który nie jest cyfrą dziesiętną, złóż wyjście na długość $MAXi wycięcie wiodących zer. Jeśli zdarzyło nam się dostać tylko 0, to $rndjest puste, więc w tym przypadku ustaw rndna 0. Sprawdź, czy wynik jest poza naszym zakresem, a jeśli tak, to powtórz. Zmusiłem „ciało” pętli while do osłony tutaj, aby wymusić wykonanie ciała co najmniej raz, w duchu naśladowania do ... whilepętli, ponieważ rndna początek jest niezdefiniowany.

Myślę, że spełniłem tutaj warunki 1 i 2, ale teraz spieprzyłem warunek 3. To trochę powolne. Zajmuje to mniej więcej sekundę (dziesięć sekund, kiedy mam szczęście). W rzeczywistości nie ma nawet gwarancji, że pętla się zakończy (chociaż prawdopodobieństwo zakończenia zbiega się z 1 wraz ze wzrostem czasu).

Czy istnieje skuteczny sposób na uzyskanie bezstronnych losowych liczb całkowitych, w ramach wcześniej określonego i potencjalnie dużego zakresu, w bash? (Będę kontynuował badanie, kiedy czas pozwoli, ale tymczasem myślałem, że ktoś tutaj może mieć fajny pomysł!)

Tabela odpowiedzi

1. Najbardziej podstawowym (i stąd przenośnym) pomysłem jest wygenerowanie losowego ciągu bitów na tyle długo, aby był wystarczający. Istnieją różne sposoby generowania losowego ciągu bitów, albo używając wbudowanej $RANDOMzmiennej bash, albo używając odi /dev/urandom(lub /dev/random). Jeśli liczba losowa jest większa niż $MAX, zacznij od nowa.

   • Kompletne rozwiązanie bash dla dowolnych przedziałach stosując albo $RANDOMalbo/dev/urandom
   • Ogólny pomysł
   • Uzyskaj losowy łańcuch bitów z zastosowaniem jednej openssllub odz /dev/urandom. Upiększ za pomocą tr.
   • Uzyskaj losowy ciąg bitów za odpomocą /dev/random. Upiększ za pomocą awk.

2. Alternatywnie można użyć narzędzi zewnętrznych.

   • Rozwiązanie Perla
     • Pro: dość przenośny, prosty, elastyczny
     • Kontra: nie dla bardzo dużych liczb powyżej 2 ³² -1
   • Rozwiązanie Python
     • Pro: prosty, elastyczny, działa nawet dla dużych liczb
     • Contra: mniej przenośny
   • Rozwiązanie Zsh
     • Pro: dobre dla osób, które i tak używają Zsh
     • Contra: prawdopodobnie jeszcze mniej przenośny

Widzę stąd inną ciekawą metodę .

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

Ta również wydaje się być dobrą opcją. Odczytuje 4 bajty z losowego urządzenia i formatuje je jako liczbę całkowitą bez znaku między 0i 2^32-1.

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

Dziękuję wszystkim za wszystkie wspaniałe odpowiedzi. Skończyło się na następującym rozwiązaniu, którym chciałbym się podzielić.

Zanim przejdę do bardziej szczegółowych informacji o tym, dlaczego i jak, oto tl; dr : mój błyszczący nowy skrypt :-)

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

Zapisz to ~/bin/randi masz do dyspozycji słodką losową funkcję w bash, która może próbkować liczbę całkowitą w danym arbitralnym zakresie. Zakres ten może zawierać ujemnych i dodatnich liczb całkowitych, i może wynosić do 2 ⁶⁰ -1 długość:

$ 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

Wszystkie pomysły innych odpowiedzi były świetne. Odpowiedzi terdon , JF Sebastian i jimmij wykorzystali narzędzia zewnętrzne do wykonania zadania w prosty i wydajny sposób. Jednak wolałem prawdziwe rozwiązanie bash dla maksymalnej przenośności, a może trochę po prostu z miłości do bash;)

Użyto odpowiedzi Ramesha i 10b0/dev/urandom lub /dev/randomw połączeniu z od. To dobrze, jednak ich podejścia miały tę wadę, że były w stanie próbkować losowe liczby całkowite w zakresie od 0 do 2 ⁸ⁿ -1 dla niektórych n, ponieważ ta metoda próbkuje bajty, tj. ^Ciągi bitów o długości 8. Są to dość duże skoki z zwiększenie n.

Wreszcie odpowiedź Falco opisuje ogólną ideę, jak można to zrobić dla dowolnych zakresów (nie tylko potęg dwóch). Zasadniczo dla danego zakresu {0..max}możemy określić, jaka jest następna potęga dwóch, tj. Dokładnie, ile bitów jest wymaganych do przedstawienia maxjako ciąg bitów . Następnie możemy pobrać próbkę tylu bitów i sprawdzić, czy to dzielenie jako liczba całkowita jest większe niż max. Jeśli tak, powtórz. Ponieważ próbkujemy tyle bitów, ile potrzeba do przedstawienia max, prawdopodobieństwo każdej iteracji jest większe lub równe 50% sukcesu (50% w najgorszym przypadku, 100% w najlepszym przypadku). To jest bardzo wydajne.

Mój skrypt jest w zasadzie konkretną implementacją odpowiedzi Falco, napisaną czystym bashem i bardzo wydajną, ponieważ wykorzystuje wbudowane operacje bitowe basha do próbkowania ciągów bitów o pożądanej długości. Dodatkowo honoruje pomysł Eliasza Kagana, który sugeruje użycie wbudowanej $RANDOMzmiennej poprzez połączenie łańcuchów bitów wynikających z powtarzanych wywołań $RANDOM. W rzeczywistości wdrożyłem zarówno możliwości użycia, jak /dev/urandomi $RANDOM. Domyślnie powyższy skrypt używa $RANDOM. (I ok, jeśli korzystamy /dev/urandom, potrzebujemy od i tr , ale są one wspierane przez POSIX.)

Jak to działa?

Zanim przejdę do tego, dwie obserwacje:

1. Okazuje się, że bash nie obsługuje liczb całkowitych większych niż 2 ⁶³ -1. Sam zobacz:

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

   Wygląda na to, że bash wewnętrznie używa 64-bitowych liczb całkowitych ze znakiem do przechowywania liczb całkowitych. Więc przy 2 ⁶³ „zawija się” i otrzymujemy ujemną liczbę całkowitą. Dlatego nie możemy mieć nadziei na uzyskanie zakresu większego niż 2 ⁶³ -1 z dowolną funkcją losową, której używamy. Bash po prostu nie może tego znieść.

2. Ilekroć chcemy próbkować wartość w dowolnym przedziale pomiędzy mini maxewentualnie min != 0, możemy po prostu próbkować wartość pomiędzy 0i max-minzamiast, a następnie dodać mindo wyniku końcowego. Działa to nawet jeśli mini ewentualnie również maxsą ujemne , ale musimy być ostrożni, aby spróbować wartość pomiędzy 0i wartość bezwzględną max-min . Zatem możemy skupić się na tym, jak próbkować losową wartość pomiędzy 0i dowolną dodatnią liczbą całkowitą max. Reszta jest łatwa.

Krok 1: Określ, ile bitów jest potrzebnych do przedstawienia liczby całkowitej (logarytmu)

Tak więc dla danej wartości maxchcemy wiedzieć, ile bitów jest potrzebnych do przedstawienia jej jako ciągu bitów. Jest tak, że później możemy losowo próbkować tylko tyle bitów, ile potrzeba, co czyni skrypt tak wydajnym.

Zobaczmy. Ponieważ w przypadku nbitów możemy reprezentować do wartości 2 ⁿ -1, wówczas liczba nbitów potrzebna do reprezentowania dowolnej wartości xwynosi pułap (log ₂ (x + 1)). Potrzebujemy więc funkcji do obliczenia pułapu logarytmu do podstawy 2. Jest to raczej oczywiste:

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

Potrzebujemy warunku, n>0więc jeśli będzie on zbyt duży, owija się i staje się ujemny, pętla z pewnością się zakończy.

Krok 2: Próbkuj losowo ciąg bitów o długości n

Najbardziej przenośne pomysły to użycie /dev/urandom(lub nawet /dev/randomjeśli jest to uzasadnione) lub wbudowana $RANDOMzmienna bash . Zobaczmy, jak to zrobić w $RANDOMpierwszej kolejności.

Opcja A: Używanie $RANDOM

Wykorzystuje to pomysł wspomniany przez Eliasza Kagana. Zasadniczo, ponieważ $RANDOMpróbki 15-bitowej liczby całkowitej, możemy użyć $((RANDOM<<15|RANDOM))do próbki 30-bitowej liczby całkowitej. Oznacza to, że przesuń pierwsze wywołanie o $RANDOM15 bitów w lewo i zastosuj bitowe lub drugie wywołanie $RANDOM, skutecznie łącząc dwa niezależnie próbkowane ciągi bitów (lub przynajmniej tak niezależne, jak wbudowane bash $RANDOM).

Możemy to powtórzyć, aby uzyskać 45-bitową lub 60-bitową liczbę całkowitą. Po tym bashu nie jest już w stanie sobie z tym poradzić, ale to oznacza, że ​​możemy łatwo próbkować losową wartość z przedziału od 0 do 2 ⁶⁰ -1. Tak więc, aby próbkować n-bitową liczbę całkowitą, powtarzamy procedurę, aż nasz losowy ciąg bitów, którego długość rośnie w 15-bitowych krokach, ma długość większą lub równą n. Wreszcie odcinamy za dużo bitów, odpowiednio przesuwając bitowo w prawo, i otrzymujemy losową liczbę całkowitą n-bit.

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

Opcja B: Używanie /dev/urandom

Alternatywnie możemy użyć odi /dev/urandomwypróbować n-bitową liczbę całkowitą. ododczytuje bajty, tj. ciągi bitów o długości 8. Podobnie jak w poprzedniej metodzie, próbkujemy tyle bajtów, że równoważna liczba próbkowanych bitów jest większa lub równa n, i odcinamy za dużo bitów.

Najniższa liczba bajtów potrzebna do uzyskania co najmniej n bitów to najniższa wielokrotność liczby 8, która jest większa lub równa n, tj. Floor ((n + 7) / 8).

Działa to tylko do 56-bitowych liczb całkowitych. Próbkowanie jeszcze jednego bajtu dałoby nam 64-bitową liczbę całkowitą, tj. Wartość do 2 ⁶⁴ -1, której bash nie może obsłużyć.

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

Łączenie elementów: zdobądź losowe liczby całkowite w dowolnych zakresach

Możemy nteraz próbkować -bitowe ciągi bitowe, ale chcemy próbkować liczby całkowite w zakresie od 0do max, jednolicie losowo , gdzie maxmogą być dowolne, niekoniecznie potęga dwóch. (Nie możemy używać modulo, ponieważ powoduje to stronniczość.)

Chodzi o to, że tak bardzo staraliśmy się próbkować tyle bitów, ile potrzeba do przedstawienia wartości max, że możemy teraz bezpiecznie (i wydajnie) używać pętli do wielokrotnego próbkowania nciągów bitowych, dopóki nie spróbujemy wartości niższej lub równa max. W najgorszym przypadku ( maxpotęga dwóch) każda iteracja kończy się z prawdopodobieństwem 50%, aw najlepszym przypadku ( maxpotęga dwóch minus jeden) pierwsza iteracja kończy się z pewnością.

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
}

Podsumowując

Na koniec chcemy próbkować liczby całkowite pomiędzy mini max, gdzie mini maxmogą być dowolne, a nawet ujemne. Jak wcześniej wspomniano, jest to teraz trywialne.

Umieśćmy to wszystko w skrypcie bash. Wykonaj kilka analiz składni argumentów ... Chcemy dwa argumenty mini max, lub tylko jeden argument max, mindomyślnie 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

... i wreszcie próbki równomiernie na losowej wartości w między mini max, możemy spróbować losową liczbę całkowitą między 0a wartość bezwzględną max-mini dodać mindo wyniku końcowego. :-)

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

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

Zainspirowany tym , mógłbym spróbować użyć zagorzałego testera do przetestowania i przetestowania tego PRNG i umieszczenia tutaj moich wniosków. :-)

Czy to może być Zsh?

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

Możesz także użyć nasion rand48(seed). Zobacz man zshmodulesi man 3 erand48szczegółowy opis w razie zainteresowania.

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

python jest dostępny na systemach Redhat, opartych na Debianie.

Jeśli chcesz liczbę od 0 do (2 ^ n) -1, gdzie n mod 8 = 0 , możesz po prostu uzyskać n / 8 bajtów /dev/random. Na przykład, aby uzyskać dziesiętną reprezentację losowej, intmożesz:

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

Jeśli chcesz wziąć tylko n bitów , możesz najpierw pobrać pułap (n / 8) bajtów i przesunąć w prawo do żądanej ilości. Na przykład, jeśli chcesz 15 bitów:

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

Jeśli masz absolutną pewność, że nie zależy Ci na jakości losowości i chcesz zagwarantować minimalny czas działania, którego możesz użyć /dev/urandomzamiast /dev/random. Przed użyciem upewnij się, że wiesz, co robisz /dev/urandom!

Zakładając, że nie wyrażasz sprzeciwu wobec korzystania z zewnętrznych narzędzi, powinno to spełniać Twoje wymagania:

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

Używa funkcji perla, randktóra przyjmuje górną granicę jako parametr. Możesz ustawić to, co chcesz. To, jak blisko jest to do prawdziwej przypadkowości w abstrakcyjnej definicji matematycznej, wykracza poza zakres tej witryny, ale powinno być w porządku, chyba że potrzebujesz jej do bardzo wrażliwego szyfrowania lub podobnego. Być może nawet tam, ale nie zaryzykuję opinii.

Powinieneś uzyskać najbliższą (2 ^ X) -1 równą lub większą niż pożądane maksimum i uzyskać liczbę bitów. Następnie wystarczy kilka razy wywołać / dev / random i dołączyć wszystkie bity razem, aż będzie ich wystarczająco, obcinając wszystkie bity, które są zbyt duże. Jeśli wynikowa liczba jest większa niż maksymalna liczba powtórzeń. W najgorszym przypadku masz większą niż 50% szansę na uzyskanie losowej liczby poniżej swojego maksimum, więc (w tym najgorszym przypadku) odbierzesz średnio dwa połączenia.

Twoja odpowiedź jest interesująca, ale dość długa.

Jeśli chcesz dowolnie dużych liczb, możesz dołączyć do wielu losowych liczb w pomocniku:

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

Jeśli problemem jest błąd, po prostu go usuń.

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

Łączenie tych funkcji razem

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