如何在 bash 中有效地生成大的、均匀分布的随机整数？

Question

我一直在想这将是获得最佳的方式很好在bash，即随机性，这将是一个过程，以获得之间的随机正整数MIN，并MAX使得

1. 范围可以是任意大的（或者至少可以达到 2 ³² -1）；
2. 值均匀分布（即没有偏差）；
3. 它是有效的。

在 bash 中获得随机性的一种有效方法是使用$RANDOM变量。但是，这仅对 0 到 2 ¹⁵ -1之间的值进行采样，这对于所有用途来说可能不够大。人们通常使用模数将其置于他们想要的范围内，例如，

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

此外，这会产生偏差，除非$MAX碰巧除以 2 ¹⁵ -1=32767。例如，如果$MIN是 0 并且$MAX是 9，那么值 0 到 7 的可能性比值 8 和 9 稍大，$RANDOM永远不会是 32768 或 32769。随着范围的增加，这种偏差会变得更糟，例如，如果$MIN是 0 并且$MAX是9999，那么数字 0 到 2767 的概率为⁴ / ₃₂₇₆₇，而数字 2768 到 9999 的概率仅为³ / ₃₂₇₆₇。

因此，虽然上述方法满足条件 3，但不满足条件 1 和 2。

到目前为止，我在尝试满足条件 1 和 2 时提出的最佳方法是使用/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

基本上，只需从/dev/urandom（/dev/random如果需要加密强的伪随机数生成器，并且如果您有很多时间，或者可能是硬件随机数生成器），则可以考虑改为使用随机性，删除每个不是十进制数字的字符，折叠输出到长度$MAX并切割前导 0。如果我们碰巧只得到 0，$rnd则为空，因此在这种情况下设置rnd为0。检查结果是否超出我们的范围，如果是，则重复。本着模拟do ... while循环的精神，我将 while 循环的“主体”强加到这里的守卫中，以强制执行主体至少一次，因为rnd它开始时未定义。

我想我在这里满足了条件 1 和 2，但现在我搞砸了条件 3。这有点慢。最多需要一秒钟左右（幸运时为十分之一秒）。实际上，循环甚至不能保证终止（尽管终止的概率随着时间的增加收敛到 1）。

在 bash 中，是否有一种有效的方法可以在预先指定且可能很大的范围内获得无偏随机整数？（我会在时间允许的情况下继续调查，但同时我认为这里的某个人可能有一个很酷的主意！）

答案表

1. 最基本的（因此也是可移植的）想法是生成一个足够长的随机位串。有多种生成随机位串的方法，可以使用 bash 的内置$RANDOM变量或使用od和/dev/urandom（或/dev/random）。如果随机数大于$MAX，则重新开始。

   • 使用$RANDOM或任意范围的完整 bash 解决方案/dev/urandom
   • 总体思路
   • 使用openssl或odwith获取随机位串/dev/urandom。用 美化tr。
   • 使用odwith获取随机位串/dev/random。用 美化awk。

2. 或者，可以使用外部工具。

   • Perl 解决方案
     • 优点：非常便携、简单、灵活
     • 反对：不适用于超过 2 ³² -1 的非常大的数字
   • Python解决方案
     • 优点：简单、灵活，甚至适用于大量
     • 反对：便携性较差
   • zsh解决方案
     • 优点：无论如何都适合使用 zsh 的人
     • 反对：可能更不便携

Answer 1

我从这里看到了另一个有趣的方法。

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

这似乎也是一个不错的选择。它从随机设备中读取 4 个字节，并将它们格式化为0和之间的无符号整数2^32-1。

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

Answer 2

谢谢大家的精彩回答。我最终得到了以下解决方案，我想分享一下。

在我详细介绍原因和方法之前，这是tl;dr：我闪亮的新脚本 :-)

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

将其保存到~/bin/randbash 中，您可以随时使用 bash 中的一个甜蜜的随机函数，它可以在给定的任意范围内对整数进行采样。该范围可能包含负整数和正整数，长度可达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

其他回答者的所有想法都很棒。通过这些问题的答案terdon，JF塞巴斯蒂安和jimmij使用外部工具做一个简单而有效的方式工作。但是，我更喜欢真正的 bash 解决方案以获得最大的可移植性，也许还有一点，只是出于对 bash 的热爱；)

Ramesh和l0b0的答案使用/dev/urandom或/dev/random与od. 这很好，但是，他们的方法有一个缺点，即对于某些 n，只能对 0 到 2 ⁸ⁿ -1范围内的随机整数进行采样，因为这种方法对字节进行采样，即长度为 8 的位串。这些是相当大的跳跃增加

最后，Falco的回答描述了如何对任意范围（不仅是 2 的幂）进行此操作的总体思路。基本上，对于给定的 range {0..max}，我们可以确定下一个 2 的幂是多少，即需要多少位来表示max为一个位串。然后我们可以采样那么多位，看看这个双串作为一个整数，是否大于max。如果是这样，请重复。由于我们采样的位数与表示 所需的位数一样多max，因此每次迭代成功的概率大于或等于 50%（最坏情况下为 50%，最好情况下为 100%）。所以这是非常有效的。

我的脚本基本上是 Falco 答案的具体实现，用纯 bash 编写并且非常高效，因为它使用 bash 的内置按位运算来采样所需长度的位串。它还尊重Eliah Kagan 的一个想法，该想法建议$RANDOM通过连接重复调用 产生的位串来使用内置变量$RANDOM。我实际上实现了使用/dev/urandom和的可能性$RANDOM。默认情况下，上述脚本使用$RANDOM. （好吧，如果使用/dev/urandom我们需要od和tr，但这些是由 POSIX 支持的。）

那么它是怎样工作的？

在我进入这个之前，有两个观察：

1. 事实证明 bash 无法处理大于 2 ⁶³ -1 的整数。你自己看：

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

   bash 内部似乎使用有符号的 64 位整数来存储整数。所以，在 2 ⁶³它“环绕”，我们得到一个负整数。所以我们不能希望使用我们使用的任何随机函数获得大于 2 ⁶³ -1 的任何范围。Bash 根本无法处理它。

2. 每当我们要样品之间的任意范围内的值min，并max有可能min != 0，我们可以简单地品尝值之间0和max-min替代，然后添加min到最终结果。这个工程即使min并且还可能max是负的，但是我们必须要小心品尝之间的值0和绝对值 max-min。那么，我们可以专注于如何在0和任意正整数之间采样随机值max。剩下的很容易。

步骤 1：确定需要多少位来表示一个整数（对数）

所以对于给定的 value max，我们想知道需要多少位才能将它表示为一个位串。这样以后我们就可以只随机采样所需的位数，从而使脚本如此高效。

让我们来看看。由于使用n位，我们最多可以表示值 2 ⁿ -1，那么n表示任意值所需的位数x是天花板（log ₂ (x+1)）。所以，我们需要一个函数来计算以 2 为底的对数的上限。它是不言自明的：

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

我们需要条件，n>0所以如果它变得太大，环绕并变为负数，则保证循环终止。

第 2 步：采样一个随机长度的比特串 n

最便携的想法是使用/dev/urandom（或者即使/dev/random有充分的理由）或 bash 的内置$RANDOM变量。让我们先看看如何做到这一点$RANDOM。

选项 A：使用 $RANDOM

这使用了Eliah Kagan 提到的想法。基本上，由于$RANDOM对 15 位整数$((RANDOM<<15|RANDOM))进行采样，因此我们可以使用对 30 位整数进行采样。这意味着，将第一次调用$RANDOM向左移动15 位，并应用按位或第二次调用$RANDOM，有效地连接两个独立采样的位串（或至少与 bash 的内置功能一样独立$RANDOM）。

我们可以重复此操作以获得 45 位或 60 位整数。之后 bash 无法再处理它，但这意味着我们可以轻松地采样 0 到 2 ⁶⁰ -1之间的随机值。因此，为了对 n 位整数进行采样，我们重复该过程，直到我们的随机位串（其长度以 15 位步长增长）的长度大于或等于 n。最后，我们通过适当地按位右移来切除过多的位，我们最终得到一个 n 位随机整数。

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

选项 B：使用 /dev/urandom

或者，我们可以使用od和/dev/urandom来采样一个 n 位整数。od将读取字节，即长度为 8 的位串。与前面的方法类似，我们只采样足够多的字节，使得采样的等效位数大于或等于 n，并切除过多的位。

获得至少 n 位所需的最低字节数是大于或等于 n 的 8 的最低倍数，即 floor((n+7)/8)。

这仅适用于 56 位整数。再采样一个字节将得到一个 64 位整数，即最大为 2 ⁶⁴ -1的值，这是 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) ))
}

将各个部分放在一起：获取任意范围内的随机整数

我们n现在可以采样-bit 位串，但我们希望从0到范围内对整数进行采样max，均匀随机，其中max可能是任意的，不一定是 2 的幂。（我们不能使用模数，因为这会产生偏差。）

我们如此努力地采样表示值所需的位数的全部原因max是，我们现在可以安全地（且有效地）使用循环来重复采样一个n位串，直到我们采样一个较低的值或等于max。在最坏的情况下（max是 2 的幂），每次迭代以 50% 的概率终止，在最好的情况下（max是 2 的幂减 1），第一次迭代肯定会终止。

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
}

收拾东西

最后，我们想对min和之间的整数进行采样max，其中min和max可以是任意的，甚至是负数。如前所述，这现在是微不足道的。

让我们把它全部放在一个 bash 脚本中。做一些参数解析的东西...我们想要两个参数minand max，或者只有一个参数max，min默认为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

...最后，为了在min和之间随机均匀地采样一个值max，我们在0和 的绝对值之间采样一个随机整数，并将其max-min添加min到最终结果中。:-)

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

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

灵感来自这个，我可能会尝试使用dieharder测试和基准这个PRNG，并把我的发现这里。:-)

Answer 3

可以是zsh吗？

zmodload zsh/mathfunc
max=1000
integer rnd='rand48() * max'

（对于 0 到 999 之间的随机数）

您可能还想将种子与rand48(seed). 如果有兴趣，请参阅man zshmodules和 man 3 erand48详细说明。

Answer 4

如果你想从一个数0至（2 ^ N）-1，其中N模8 = 0，你可以简单地得到N / 8的字节/dev/random。例如，要获得随机数的十进制表示，int您可以：

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

如果您只想取n 位，您可以先取天花板（n / 8）个字节，然后右移到您想要的数量。例如，如果您想要 15 位：

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

如果你有绝对的把握，你不关心随机性的质量，并要保证最小运行时可以使用/dev/urandom的替代/dev/random。使用前请确保您知道自己在做什么/dev/urandom！

Answer 5

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

python 可在基于 Debian 的 Redhat 系统上使用。