如何改进给定随机函数的均匀分布以生成均匀分布的数？

Question

问题与 Linux 相关，如 Debian 或 Ubuntu、bash 以及使用 RANDOM 的给定函数。

每项改进都应仅使用 bash。

给出以下函数：

getRND(){
    min="${1:-1}"   ## min is the first parameter, or 1 if no parameter is given           
    max="${2:-100}" ## max is the second parameter, or 100 if no parameter is given
    rnd_count=$((RANDOM%(max-min+1)+min));
    echo "$rnd_count"
}

var=$(getRND -10 10) # Call the function
echo $var # output

怎么样：

提高随机性

为 Linux 尚未安装 bash 5.1 的系统寻求解决方案，因此到目前为止无法使用 SRANDOM。

Answer 1

在 main shell 中为 RANDOM 制作种子并期望它在 subshell 中受到青睐是没有意义的，因为新的 shell 会自行初始化种子。

所以你需要播种并使用 main shell 的 RANDOM 并将值传递给另一个函数进行转换。

这里是一个如何让你的种子发挥作用的例子：

#!/bin/bash


normalize_value(){
    value_to_normalize=
    min="${2:-1}"   ## min is the first parameter, or 1 if no parameter is given           
    max="${3:-100}" ## max is the second parameter, or 100 if no parameter is given
    rnd_count=$((value_to_normalize % (max-min+1)+min));
    echo "$rnd_count"
}

RANDOM=$(date +%s%N | cut -b10-19)

rnd=$RANDOM # get random value in a context of main shell and your seed
var=$(normalize_value $rnd -10 10) # pass random value into normalizer function
echo $var # output

###### following example will NOT WORK because statement refers to subshell's random generator
RANDOM=1
var=$(normalize_value $RANDOM -10 10) # wrong random sequence is used (not seeded by you)
echo $var # output

var=$(normalize_value $RANDOM -10 10) # wrong
echo $var # output

Answer 2

what can be improved on a given random function to make it more random or for a bigger range or something else?

and therefore no SRANDOM can be used up to now.

How to improve the randomness of the fuction above, if possible ?

Sooo 用你自己的语义写你自己的 SRANDOM。例如：

srandom() {
   # take random number from /dev/urandom
   # we take only just 4 bytes - one 2^32 number
   printf "%d\n" "0x$(
       dd if=/dev/urandom of=/dev/stdout bs=4 count=1 status=none |
       xxd -p)"
}

然后：

normalize_value(){
   ...
   rnd=$(srandom)
   rnd_count=$((rnd / ...))
}

Accepting a wider range of numbers

如果您对 shell 算术展开的方式不满意，那么...使用不同的工具。 bc 计算器的范围是无限的。

rnd_count=$(echo "
     # see https://superuser.com/questions/31445/gnu-bc-modulo-with-scale-other-than-0
     scale=0; 
     # super big random number from three 2^32 numbers
     rnd = $(srandom) * 2^(32*2) +  $(srandom) * 2^32 + $(srandom)
     rnd % ($max - $min + 1) + $min
     " | bc)

您可以使用 getrandom() 编写您自己的 C 程序并即时编译它 echo "int main() { stuff(); }" | gcc -xc - && ./a.out; rm ./a.out 基本上授予您任何您想要的语义。还有其他脚本语言，如 perl、python、ruby，它们很可能都有自己的大数库和 urandom 数生成实现。突破极限。

Every improvement should use bash only.

从我的角度来看，这是一个毫无意义的限制 - 总的来说，我是按结果付费的，而不是我真正“如何”解决问题。无论如何，你可以，给你一堆如何进行的想法：

首先编写一个函数，从 /dev/urandom 中读取并将字节转换为数字。
- 我不知道如何在纯 bash 中做到这一点，同时将随机性保持在正常水平。我怀疑输入会很快耗尽。
- 你可以从 urandom 读取一个字节。您必须忽略 read 退出状态，因为字节可能是零字节或换行符。
- 然后检查该字节是否为数字。如果不是，请重复上一步。
- 将此类算法视为0-9范围内随机数的生成器。从这些数字构建更大的数字。
然后使用算术展开作为“后端”开发自己的大数库，用bash编写。
- 似乎毫无意义，因为 bc 很常见。
- 这将像通常的大数字库一样工作。
- 我建议将数字存储为最大 2^16 的数字数组。为了获得灵感，研究用 C 和 C++ 语言编写的类似库，并将其转换为 bash.

Answer 3

这就是将问题代码和 KamilCuk 答案代码合并到一个函数中以实现随机分布更均匀时的样子：

#!/bin/bash

get_rnd_num_eq_dis(){
    min="${1:-1}"   # min is the first parameter, or 1 if no parameter is given           
    max="${2:-100}" # max is the second parameter, or 100 if no parameter is given
#   rnd=$(srandom)
    srnd="$((0x$(dd if=/dev/urandom of=/dev/stdout bs=4 count=1 status=none | xxd -p)))"
    rnd_count=$((srnd%(max-min+1)+min));
    echo "$rnd_count"
}

var=$(get_rnd_num_eq_dis -100 100) # Call the function
echo "$var" # output

sleep 2

备注：好像可以在大于+-32000的范围内使用

如何改进给定随机函数的均匀分布以生成均匀分布的数？

How to improve the uniformly distributed of a given random function to generate uniformly distributed numbers?

linux

bash

function

random

random-seed