生成用于测试的强偏随机数。

2017-8-4 17:22:17
收藏：0
阅读：167
评论：3

我想要使用随机输入运行测试，并需要生成“合理”的随机数，即匹配足够好以通过被测试函数的前提条件，但希望在其代码内部深入引发混乱的数字。

math.random()（我正在使用Lua）生成均匀分布的随机数。将其放大会得到更多大数而不是小数，几乎没有整数。

我想要偏向于随机数（或使用旧函数作为随机源生成新随机数），以强烈偏向于“简单”数字，但仍然涵盖整个范围，也就是扩展到正/负无穷大（或$ \ pm $1e309的双精度）。这意味着：

  • 数字最多应该到10，
  • 整数应比分数更常见，
  • 数字以0.5结尾的分数应该是最常见的，
  • 然后是0.25和0.75;然后是0.125，
  • 依此类推。

不同的描述：确定一个基本概率_x_，使概率总和为一，并将数_n_的概率定义为_xk_ 其中_k_是构造数为surreal number ** 1**的生成。它将_x_分配给0，将_x2分配给-1和+ 1，将_x3分配给-2，-1/2，+1/2和+2，依此类推。这提供了对我要求的事物的一个很好的描述（它偏向了一些），但在计算随机数时几乎无法使用。结果分布无处连续（是分形！），我不确定如何确定基本概率_x_（我认为对于无限精度它将是零），基于迭代计算这些数字会非常慢（花费接近无限的时间构建大数字）。

有没有人知道一个简单的近似值，可以生成非常粗略分布如上所述的随机数字，给定均匀分布的随机性源？

我想运行数千次随机测试，数量/速度比质量更重要。仍然，更好的数字意味着更少的输入被拒绝。

Lua具有JIT，因此性能通常不是问题。但是，基于随机性的跳跃将破坏每个预测，而对math.random()的许多调用也将变慢。这意味着闭合的公式将比迭代或递归的公式更好。

1维基百科有一篇关于surreal numbers的文章，其中有一个漂亮的图片。c普若米数是两个surreal number的一对，即x：={n | m}, 其价值为对中的数字，即（对于有限数字）{n | m} =（n + m）/ 2（作为有理数）。如果一对的一边为空，那将被解释为增量（如果右边为空，则为减量）达到一。如果两边都为空，则为零。最初，没有数字，因此可以构建的唯一数字是0：={|}。在第二代中，可以构建数字{0 |} =：1和{| 0} =： -1，第三代中，我们得到数字{1 |} =：2，{| 1} =： -2，{0 | 1} =：1/2和{ -1 | 0} =：-1/2（加上一些已知数字的复杂表示，例如{-1 | 1}？0）。请注意，例如1/3从不由有限数字生成，因为它是无限分数 - 浮点数也是如此，1/3从不准确地表示。

点赞
用户1204143
用户1204143

这个算法怎么样？

  1. 使用库函数生成一个 (0, 1)之间的随机浮点数。
  2. 根据所需的概率密度函数生成一个随机的整数截断点（例如，概率为0.5时为0，概率为0.25时为1，概率为0.125时为2，...）。
  3. 根据截断点'将'浮点数四舍五入（例如，floor((float_val << roundoff)+0.5)）。
  4. 根据另一个概率密度函数生成一个随机的整数指数（例如，0、1、2、3的概率都为0.1，之后逐渐减小）。
  5. 将四舍五入后的浮点数乘上 $2^{exponent}$。
2012-10-07 04:03:30
用户508994
用户508994

生成一个类似超现实的小数，您需要一个随机的二进制数字。偶数位告诉你是停下还是继续前进，奇数位告诉你是否向树的右边或左边前进：

> 0... => 0.0 [50%] 停
> 100... => -0.5 [< 12.5%] 前往左边，停止
> 110... => 0.5 [< 12.5%] 前往右边，停止
> 11100... => 0.25 [< 3.125%] 前往右边，然后前往左边，停止
> 11110... => 0.75 [< 3.125%] 前往右边，然后前往右边，停止
> 1110100... => 0.125
> 1110110... => 0.375
> 1111100... => 0.625
> 1111110... => 0.875

快速生成随机二进制数字的一种方法是查看math.random()中的十进制数字，并将0-4替换为“1”，将5-9替换为“1”：

  • 0.8430419054348022 变成 1000001010001011 然后变成 -0.5

  • 0.5513009827118367 变成 1100001101001011 然后变成 0.25 等等

我没有做过很多lua编程，但是用JavaScript可以做到：

Math.random().toString().substring(2).split("").map(
    function(digit) { return digit >= "5" ? 1 : 0 }
);

或真正的二进制展开：

Math.random().toString(2).substring(2)

不确定哪一个更真正的“随机”——你需要测试。

你可以用这种方式生成超现实的数字，但大多数结果将是形如a / 2^b的小数，其中整数相对较少。第3天只产生了2个整数(-3和3)，而有14个小数，在第4天是2对14，在第n天是2对(2^n-2)。

如果从'math.random()'中添加两个均匀随机数字，则会得到一个具有“三角形”分布（从中心线性下降）的新分布。添加3个或更多将得到一个更像钟形曲线的分布，其以0为中心：

math.random() + math.random() + math.random()  - 1.5

通过一个随机数除以一个随机数将获得一个真正的狂野数字：

A/(math.random()+1e-300)

这将返回A和（_理论上) A *1e+300之间的结果，尽管我的测试显示结果50％的时间在A和2 *之间。 A和大约75％的时间在A和4 * A之间。

将它们组合起来，我们就得到：

round(6*(math.random()+math.random()+math.random() - 1.5)/(math.random()+1e-300))

这种方法使-9和9之间的数字超过70％，同时偶尔会出现一些大数字。

请注意，这个分布的平均值和总和倾向于随着运行次数的增加而发散成一个很大的负数或正数，因为您运行它的次数越多，分母的小数字越可能导致数字“膨胀”到像147,967或 -194,137这样的大数字。

有关示例代码，请参见gist。

Josh

2012-10-26 06:27:48
用户1880288
用户1880288

你可以立即计算第n个Born Surreal数。

例如，第1000个Surreal数为：

  1. 转换为二进制：

    1000 dec = 1111101000 bin

  2. 1变为加号，0变为减号：

    1111101000

    +++++-+---

  3. 第一个“1”位为0值，下一组类似数字为+1（对于1）或-1（对于0），然后对于每个后续位，值为1/2、1/4、1/8等。

    1 1 1 1 1 0 1 0 0 0

    + + + + + - + - - -

    0 1 1 1 1 h h h h h

    +0+1+1+1+1-1/2+1/4-1/8-1/16-1/32

    = 3+17/32

    = 113/32

    = 3.53125

此表示的二进制位长度等于该数字出生的日期。

Surreal数的左右数字是其二进制表示，其尾部分别削减到最后一个0或1。

Surreal数在-1和1之间均匀分布，其中一半的数字将存在于特定日期创建的数字中。从-2到-1和1到2等，1/4的数字均匀分布存在。最大范围将是负整数到正整数，与您提供的天数相匹配。数字会因为每天仅将负和正范围增加一而缓慢地无限增加，而天数包含上一个的两倍的数字。

编辑：

这个位表示的好名字是“sinary”

负数是转位。例如：

100010101001101s -> negative number (always start 10...)

111101010110010s -> positive number (always start 01...)

我们注意到所有位都会翻转，除了第一个是一个转位。

Nan是=> 0s（因为所有其他数字都以1开头），这使得它理想地在计算机的比特寄存器中表示，因为需要前导零（我们不再制造三进制计算机...太糟糕了）

所有的康威超现代代数都可以在这些数字上完成，而无需转换成二进制或十进制。

sinary格式可以看作是一个简单的1计数器与附加的2的补码十进制表示形式之和。

这是关于finary（类似于sinary）的不完整报告：https://github.com/peawormsworth/tools/blob/master/finary/Fine%20binary.ipynb

2020-06-08 07:42:10

作者:

用户805875

用户805875
推荐文章