Saya telah bertanya-tanya apa yang akan menjadi cara terbaik untuk mendapatkan keacakan yang baik di bash, yaitu, apa yang akan menjadi prosedur untuk mendapatkan bilangan bulat positif acak antara MINdan MAXsedemikian rupa sehingga

1. Kisarannya bisa besar secara sewenang-wenang (atau setidaknya, katakanlah, hingga 2 ³² -1);
2. Nilai didistribusikan secara seragam (yaitu, tidak ada bias);
3. Itu efisien.

Cara efisien untuk mendapatkan keacakan dalam bash adalah dengan menggunakan $RANDOMvariabel. Namun, ini hanya sampel nilai antara 0 dan 2 ¹⁵ -1, yang mungkin tidak cukup besar untuk semua tujuan. Orang biasanya menggunakan modulo untuk membawanya ke kisaran yang mereka inginkan, misalnya,

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

Ini, selain itu, menciptakan bias kecuali $MAXterjadi untuk membagi 2 ¹⁵ -1 = 32767. Misalnya, jika $MINadalah 0 dan $MAXadalah 9, maka nilai-nilai 0 sampai 7 sedikit lebih mungkin daripada nilai 8 dan 9, karena $RANDOMtidak akan pernah 32768 atau 32769. Bias ini semakin memburuk dengan meningkatnya jangkauan, misalnya, jika $MINadalah 0 dan $MAXadalah 9999, maka angka 0 sampai 2767 memiliki probabilitas ⁴ / ₃₂₇₆₇ , sedangkan nomor 2768 melalui 9999 hanya memiliki probabilitas ³ / ₃₂₇₆₇ .

Jadi sementara metode di atas memenuhi syarat 3, itu tidak memenuhi ketentuan 1 dan 2.

Metode terbaik yang saya buat sejauh ini dalam mencoba memenuhi kondisi 1 dan 2 adalah menggunakan /dev/urandomsebagai berikut:

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

Pada dasarnya, kumpulkan saja keacakan dari /dev/urandom(mungkin dapat dipertimbangkan untuk digunakan /dev/randomsebagai gantinya jika generator nomor pseudorandom acak yang kuat secara kriptografi diinginkan, dan jika Anda memiliki banyak waktu, atau mungkin juga generator nomor acak perangkat keras), hapus setiap karakter yang bukan digit desimal, lipat output dengan panjang $MAXdan memotong 0 yang memimpin. Jika kita kebetulan hanya mendapatkan 0 maka $rndkosong, maka dalam hal ini diatur rndke 0. Periksa apakah hasilnya di luar jangkauan kami dan jika demikian, ulangi. Saya memaksa "tubuh" loop sementara ke penjaga di sini untuk memaksa eksekusi tubuh setidaknya sekali, dalam semangat meniru do ... whileloop, karena rndtidak ditentukan untuk memulai.

Saya pikir saya memenuhi persyaratan 1 dan 2 di sini, tapi sekarang saya mengacaukan kondisi 3. Ini agak lambat. Memakan waktu sekitar satu detik atau lebih (sepersepuluh detik saat saya beruntung). Sebenarnya, loop bahkan tidak dijamin untuk berakhir (walaupun probabilitas pemutusan konvergen menjadi 1 seiring dengan meningkatnya waktu).

Apakah ada cara yang efisien untuk mendapatkan bilangan bulat acak yang tidak bias, dalam kisaran yang ditentukan sebelumnya dan berpotensi besar, dalam bash? (Saya akan terus menyelidiki ketika waktu memungkinkan, tetapi sementara itu saya pikir seseorang di sini mungkin punya ide keren!)

Daftar Jawaban

1. Gagasan paling mendasar (dan karenanya portabel) adalah untuk menghasilkan bitstring acak cukup lama. Ada berbagai cara menghasilkan bitstring acak, baik menggunakan $RANDOMvariabel bawaan bash atau menggunakan oddan /dev/urandom(atau /dev/random). Jika angka acak lebih besar dari $MAX, mulai dari awal.

   • Solusi bash lengkap untuk rentang acak menggunakan salah satu $RANDOMatau/dev/urandom
   • Gagasan umum
   • Dapatkan bitstring acak menggunakan salah satu opensslatau oddengan /dev/urandom. Percantik dengan tr.
   • Dapatkan bitstring acak oddengan menggunakan /dev/random. Percantik dengan awk.

2. Atau, dimungkinkan untuk menggunakan alat eksternal.

   • Solusi Perl
     • Pro: cukup portabel, sederhana, fleksibel
     • Kontra: bukan untuk angka yang sangat besar di atas 2 ³² -1
   • Solusi Python
     • Pro: sederhana, fleksibel, bekerja bahkan untuk jumlah besar
     • Contra: kurang portabel
   • Solusi zsh
     • Pro: bagus untuk orang yang menggunakan zsh
     • Contra: bahkan mungkin lebih portabel

Saya melihat metode lain yang menarik dari sini .

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

Yang ini juga tampaknya menjadi pilihan yang bagus. Bunyinya 4 byte dari perangkat acak dan memformatnya sebagai integer tak bertanda antara 0dan 2^32-1.

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

Terima kasih atas semua jawaban Anda. Saya berakhir dengan solusi berikut, yang ingin saya bagikan.

Sebelum saya membahas lebih detail tentang mengapa dan bagaimana, inilah tl; dr : skrip baru saya yang mengkilap :-)

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

Simpan itu ~/bin/randdan Anda memiliki fungsi acak manis di bash yang dapat mencicipi integer dalam rentang sewenang-wenang yang diberikan. Rentang ini dapat berisi bilangan bulat negatif dan positif dan panjangnya dapat mencapai 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

Semua ide dari penjawab lain sangat bagus. Jawaban oleh terdon , JF Sebastian , dan jimmij menggunakan alat eksternal untuk melakukan tugas dengan cara yang sederhana dan efisien. Namun, saya lebih suka solusi bash sejati untuk portabilitas maksimum, dan mungkin sedikit, hanya karena cinta untuk bash;)

Jawaban Ramesh dan l0b0 digunakan /dev/urandomatau /dev/randomdikombinasikan dengan od. Itu bagus, bagaimanapun, pendekatan mereka memiliki kelemahan hanya mampu sampel bilangan bulat acak dalam kisaran 0 hingga 2 ⁸ⁿ -1 untuk beberapa n, karena metode ini sampel byte, yaitu, bitstrings dengan panjang 8. Ini adalah lompatan yang cukup besar dengan meningkat n.

Akhirnya, jawaban Falco menggambarkan gagasan umum bagaimana ini bisa dilakukan untuk rentang arbitrer (tidak hanya kekuatan dua). Pada dasarnya, untuk rentang yang diberikan {0..max}, kita dapat menentukan apa kekuatan dua berikutnya, yaitu, persis berapa banyak bit yang diperlukan untuk mewakili maxsebagai bitstring. Kemudian kita bisa mencicipi banyak bit itu dan melihat apakah bistring ini, sebagai bilangan bulat, lebih besar dari max. Jika demikian, ulangi. Karena kami sampel bit yang diperlukan untuk mewakili max, setiap iterasi memiliki probabilitas lebih besar atau sama dengan 50% dari berhasil (50% dalam kasus terburuk, 100% dalam kasus terbaik). Jadi ini sangat efisien.

Skrip saya pada dasarnya adalah implementasi konkret jawaban Falco, ditulis dalam bash murni dan sangat efisien karena menggunakan operasi bitwise bawaan bash untuk mengambil sampel bitstring dengan panjang yang diinginkan. Ini juga menghormati ide oleh Eliah Kagan yang menyarankan untuk menggunakan $RANDOMvariabel bawaan dengan meringkas bitstring yang dihasilkan dari pemanggilan berulang $RANDOM. Saya benar-benar mengimplementasikan kedua kemungkinan untuk menggunakan /dev/urandomdan $RANDOM. Secara default, skrip di atas menggunakan $RANDOM. (Dan ok, jika menggunakan /dev/urandomkita perlu od dan tr , tetapi ini didukung oleh POSIX.)

Jadi bagaimana cara kerjanya?

Sebelum saya membahas hal ini, dua pengamatan:

1. Ternyata bash tidak dapat menangani bilangan bulat yang lebih besar dari 2 ⁶³ -1. Lihat diri mu sendiri:

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

   Tampaknya bash secara internal menggunakan integer 64-bit yang ditandatangani untuk menyimpan integer. Jadi, pada 2 ⁶³ itu "membungkus" dan kami mendapatkan bilangan bulat negatif. Jadi kita tidak bisa berharap untuk mendapatkan rentang yang lebih besar dari 2 ⁶³ -1 dengan fungsi acak apa pun yang kita gunakan. Bash tidak bisa mengatasinya.

2. Kapan pun kita ingin mengambil sampel dalam rentang yang sewenang-wenang antara mindan maxdengan yang mungkin min != 0, kita bisa dengan mudah mengambil sampel di antara 0dan max-minalih-alih kemudian menambahkan minke hasil akhir. Ini bekerja bahkan jika mindan mungkin juga maxyang negatif , tapi kami harus berhati-hati untuk sampel nilai antara 0dan nilai absolut dari max-min . Jadi, kita bisa fokus pada bagaimana sampel nilai acak antara 0dan bilangan bulat positif arbitrer max. Sisanya mudah.

Langkah 1: Tentukan berapa banyak bit yang diperlukan untuk mewakili integer (logaritma)

Jadi untuk nilai yang diberikan max, kami ingin tahu berapa banyak bit yang diperlukan untuk menyatakannya sebagai bitstring. Ini agar nantinya kita dapat secara acak sampel hanya sebanyak bit yang diperlukan, yang membuat skrip jadi efisien.

Ayo lihat. Karena dengan nbit, kita dapat mewakili hingga nilai 2 ⁿ -1, maka jumlah nbit yang diperlukan untuk mewakili nilai arbitrer xadalah plafon (log ₂ (x + 1)). Jadi, kita membutuhkan fungsi untuk menghitung langit-langit logaritma ke basis 2. Ini agak jelas:

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

Kita membutuhkan kondisinya n>0sehingga jika tumbuh terlalu besar, membungkus dan menjadi negatif, loop dijamin akan berakhir.

Langkah 2: Cicipi bitstring acak yang panjangnya n

Gagasan yang paling portabel adalah menggunakan /dev/urandom(atau bahkan /dev/randomjika ada alasan kuat) atau $RANDOMvariabel bawaan bash . Mari kita lihat bagaimana melakukannya $RANDOMterlebih dahulu.

Opsi A: Menggunakan $RANDOM

Ini menggunakan ide yang disebutkan oleh Eliah Kagan. Pada dasarnya, karena $RANDOMsampel bilangan bulat 15-bit, kita dapat menggunakan $((RANDOM<<15|RANDOM))sampel bilangan bulat 30-bit. Itu berarti, menggeser doa pertama $RANDOMsebesar 15 bit ke kiri, dan menerapkan bitwise atau dengan doa kedua $RANDOM, efektif meringkas dua bitstring sampel secara independen (atau setidaknya sama independennya dengan built-in $RANDOMberjalan bash ).

Kita dapat mengulanginya untuk mendapatkan integer 45-bit atau 60-bit. Setelah itu bash tidak bisa mengatasinya lagi, tetapi ini berarti kita dapat dengan mudah mencicipi nilai acak antara 0 dan 2 ⁶⁰ -1. Jadi, untuk mengambil sampel bilangan bulat n-bit, kami ulangi prosedur sampai bitstring acak kami, yang panjangnya tumbuh dalam langkah 15-bit, memiliki panjang lebih besar atau sama dengan n. Akhirnya, kita memotong bit yang terlalu banyak dengan menggeser bitwise ke kanan, dan kita berakhir dengan integer acak 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) ))
}

Opsi B: Menggunakan /dev/urandom

Atau, kita bisa menggunakan oddan /dev/urandommengambil sampel integer n-bit. odakan membaca byte, yaitu, bitstrings of length 8. Demikian pula seperti dalam metode sebelumnya, kami sampel begitu banyak byte sehingga jumlah setara bit sampel lebih besar atau sama dengan n, dan memotong bit yang terlalu banyak.

Jumlah byte terendah yang diperlukan untuk mendapatkan setidaknya n bit adalah kelipatan terendah dari 8 yang lebih besar atau sama dengan n, yaitu lantai ((n + 7) / 8).

Ini hanya bekerja hingga bilangan bulat 56-bit. Mengambil sampel satu byte lagi akan memberi kita integer 64-bit, yaitu nilai hingga 2 ⁶⁴ -1, yang tidak dapat ditangani oleh bash.

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

Menyatukan potongan: Dapatkan bilangan bulat acak dalam rentang acak

Kita dapat mencicipi nbitstring-bit sekarang, tetapi kami ingin mengambil contoh bilangan bulat dalam kisaran dari 0hingga max, seragam secara acak , di mana maxmungkin arbitrer, tidak harus kekuatan dua. (Kami tidak dapat menggunakan modulo karena itu menciptakan bias.)

Inti mengapa kami berusaha sangat keras untuk sampel bit sebanyak yang diperlukan untuk mewakili nilai max, adalah bahwa kita sekarang dapat dengan aman (dan efisien) menggunakan loop untuk berulang kali sampel nbitstring-bit sampai kita sampel nilai yang lebih rendah atau sama dengan max. Dalam kasus terburuk ( maxadalah kekuatan dua), setiap iterasi berakhir dengan probabilitas 50%, dan dalam kasus terbaik ( maxadalah kekuatan dua minus satu), iterasi pertama berakhir dengan pasti.

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
}

Membungkus semuanya

Akhirnya, kami ingin mengambil sampel bilangan bulat antara mindan max, di mana mindan maxdapat arbitrer, bahkan negatif. Seperti yang disebutkan sebelumnya, ini sekarang sepele.

Mari kita letakkan semuanya dalam skrip bash. Lakukan beberapa penguraian argumen ... Kami ingin dua argumen mindan max, atau hanya satu argumen max, di mana mindefaultnya adalah 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

... dan, akhirnya, untuk sampel secara acak di nilai antara mindan max, kami sampel bilangan bulat acak antara 0dan nilai absolut dari max-min, dan menambah minhasil akhir. :-)

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

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

Terinspirasi oleh ini , saya mungkin mencoba menggunakan dieharder untuk menguji dan membandingkan PRNG ini, dan memasukkan temuan saya di sini. :-)

Bisakah itu zsh?

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

Anda mungkin ingin menggunakan seed juga rand48(seed). Lihat man zshmodulesdan man 3 erand48untuk deskripsi terperinci jika tertarik.

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

python tersedia di Redhat, sistem berbasis Debian.

Jika Anda menginginkan angka dari 0 hingga (2 ^ n) -1 di mana n mod 8 = 0 Anda cukup mendapatkan n / 8 byte dari /dev/random. Misalnya, untuk mendapatkan representasi desimal acak, intAnda dapat:

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

Jika Anda ingin mengambil hanya n bit, Anda dapat mengambil byte (n / 8) byte terlebih dahulu dan bergeser ke jumlah yang Anda inginkan. Misalnya jika Anda ingin 15 bit:

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

Jika Anda benar-benar yakin bahwa Anda tidak peduli dengan kualitas keacakan dan Anda ingin menjamin waktu berjalan minimal yang dapat Anda gunakan /dev/urandomsebagai gantinya /dev/random. Pastikan Anda tahu apa yang Anda lakukan sebelum menggunakan /dev/urandom!

Dengan asumsi Anda tidak keberatan menggunakan alat eksternal, ini harus memenuhi persyaratan Anda:

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

Ini menggunakan randfungsi perl yang mengambil batas atas sebagai parameter. Anda dapat mengaturnya sesuai keinginan Anda. Seberapa dekat hal ini dengan keacakan yang sebenarnya dalam definisi matematika abstrak berada di luar cakupan situs ini, tetapi seharusnya tidak ada masalah kecuali Anda memerlukannya untuk enkripsi yang sangat sensitif atau sejenisnya. Mungkin bahkan di sana tetapi saya tidak akan berani berpendapat.

Anda harus mendapatkan yang terdekat (2 ^ X) -1 sama atau parutan dari maksimum yang Anda inginkan dan mendapatkan jumlah bit. Kemudian panggil / dev / acak beberapa kali dan tambahkan semua bit sampai Anda punya cukup, memotong semua bit yang terlalu banyak. Jika angka yang dihasilkan lebih besar dari max repeat Anda. Dalam kasus terburuk Anda memiliki peluang lebih besar dari 50% untuk mendapatkan nomor acak di bawah Maksimum Anda sehingga (untuk kasus terburuk ini), Anda akan menerima dua panggilan rata-rata.

Jawaban Anda menarik tetapi cukup panjang.

Jika Anda ingin angka besar sewenang-wenang, maka Anda dapat bergabung dengan beberapa angka acak dalam sebuah bantuan:

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

Jika masalahnya bias, maka hapus saja.

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

Menggabungkan fungsi-fungsi ini bersama-sama

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