自由数字。

Question 1

带走

除了下面详细解释的浮点限制（不超过 15 位十进制数字）之外，源代码还有以下额外限制：

最初的 awk 仅限于仅有的rand() 函数中存在 32768 (0..32767) 个不同的值。

/* #ifndef RAND_MAX */  
/* #define RAND_MAX     32767 */        /* all that ansi guarantees */  
/* #endif */

这比 4 位数字多一点，这就是旧 awk 中您可以信任的所有数字。

mawk 实现对 rand() 有几个限制，从 16 位到 32 位 (0..4294967295)。所以，有点多于 9 位数字。

奇怪的是，GNU awk 只会从random()(read support/random.c) 返回 31 位，尽管内置了任意精度的数学。仍然多于 9 位数字，但是 mawk arc4random 的一半（来自 BSD）（0..2147483647）。

让我们一步步深入研究 awk 中的浮点表示。

rand() 会给出多少位小数？

明显

显而易见的答案是：您要求多少（是的，大多数版本）：

$ awk 'BEGIN{srand(11); printf("%.83f\n",rand())}'
0.37904318086255550657170942940865643322467803955078125000000000000000000000000000000

用于srand(11)生成可重复的随机数。任何用户都应该获得相同的随机数（在 GNU awk 中，不同版本的 awk 可能会有所不同，但在重复调用和计算机上稳定）。

是的，位数可能比 83 多得多，并且将忠实地打印这么多位数。

但很明显，经过一些计数后，无论您要求多少，所有数字都会变为零。

有效的

如果你想数一下它们：

$ printf '%s' "  " $(seq 9)"_"{,,,,,}; echo; \
    awk 'BEGIN{srand(11); printf("%.63f\n",rand())}';\
    printf '  ';printf '^%.0s' $(seq 53); echo "<--- up to here"

  123456789_123456789_123456789_123456789_123456789_123456789_
0.379043180862555506571709429408656433224678039550781250000000000
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^<--- up to here

你会发现有 53 位十进制数字（至少在 Linux GNU 中）。

为什么是53？

这与 awk 中用于表示数字的二进制浮点数尾数中使用的二进制位数完全相同。好吧，至少与“双精度”浮点数（8字节浮点数）为由 IEEE 754 定义

问：是这个原因吗？二进制位数等于十进制位数吗？

答：一言以蔽之：是的。

证明

任何二元分数，即一个零后面跟着一个点，后面跟着几个二进制数字：

0.100110011

可以写成：

1 × 2 ^-1 + ₂_× 2 ^-2 + ₃ × 2 ^-3 + ....

对于某个_i二进制数字序列。

例如：

0.100110011
1×2 ^-1 + 0×2 ^-2 + 0×2 ^-3 + 1×2 ^-4 + 1×2 ^-5 + ....

删除零：

2 ^-1 + 2 ^-4 + 2 ^-5 + 2 ^-8 + 2 ^-9

因式分解 2 ^-9：

( 2 ⁺⁸ + 2 ⁺⁵ + 2 ⁺⁴ + 2 ¹ + 1 ) × 2 ^-9

括号内是一个整数二进制数：

100110011 #（十进制307）

这个分数实际上是一个二进制分数：

307 × 2 ^-9
307 / 2 ⁹

如果我们将分子和分母都乘以 5 ⁹我们得到：

307 × 5 ⁹ / 2 ⁹ × 5 ⁹
307 × 5 ⁹ / 10 ⁹
307 × 1953125 / 10 ⁹
599609375 / 10 ⁹
0.599609375

与二进制分数位数相同的十进制分数。

因此，所有二进制分数都可以转换（确切地) 化为点后位数完全相同的小数（分母的指数相同）。反之则不然。并非所有十进制分数都可以转换为二进制分数。

现在我们知道怎么做了：我们可以尝试更长的分数：

0.10011001100110011001100110011001100110011001100110011
10011001100110011001100110011001100110011001100110011₂ / 2⁵³
5404319552844595₁₀ / 2⁵³
5404319552844595₁₀ × 5⁵³ / 10⁵³
5404319552844595 × 11102230246251565404236316680908203125 / 10⁵³
59999999999999997779553950749686919152736663818359375 / 10⁵³
0.59999999999999997779553950749686919152736663818359375

这正是 awk 给出的0.653 位表示形式：

$ awk 'BEGIN{printf("%.60g\n",0.6)}'
0.59999999999999997779553950749686919152736663818359375

因此，53 位十进制数字是 awk 可以给出的 53 位尾数浮点数的最大值。

好吧，读作 53重要的数字，因为某些数字可能有前导零：

$ awk 'BEGIN{printf("%.90f\n",3^-20)}'
0.000000000286797199079244134930566254988964884631297280748185585252940654754638671875000000

自由数字。

问：但是所有浮点数（小数）都以 5 结尾，是否存在某种潜在的力量使数字不随机？

答：是的。

描述

任何二进制数字都有十进制的精确表示。如上所述，二进制分数是：

1 × 2 ^-1 + ₂_× 2 ^-2 + ₃ × 2 ^-3 + ....

_{对于 a i}的某个序列。每个指数的值是众所周知的：

2 ^-1 = 0.5
2 ^-2 = 0.25
2 ^-3 = 0.125
2 ^-4 = 0.0625
2 ^-5 = 0.03125
2 ^-6 = 0.015625
2 ^-7 = 0.0078125
2 ^-8 = 0.00390625
2 ^-9 = 0.001953125
2 ^-10 = 0.0009765625
...

我们可以看到为什么以及如何用连续的二进制分数来近似像 0.6 这样的数字。
添加的每个连续分数必须来自以下。所有分数都相加，无法返回到更小的值。

2 ^-1 = 0.5 ==> 0.5

第一个二进制数字贡献了 0.5，我们距离 0.6 还差 0.1。下一个：0.25和0.125之后的一个比需要添加的要大。所以，它们不能被使用。可以添加接下来的两个。第一个 2 ^-4 (0.0625) 小于 0.1 差值，可以相加。第二个 2 ^-5 (0.03125) 小于第一个留下的 0.375 差值，也可以相加。

2<sup>-1</sup>   = 0.5                     ==> 0.5
2<sup>-4</sup>   = 0.0625                  ==> 0.5625
2<sup>-5</sup>   = 0.03125                 ==> 0.59375
----------------------^ <== digit being approximated
-----------------------*** <== trailing digits of each fraction.

随着每个连续的二进制位添加到 0.6 的表示中，结果变得更接近该值：

2<sup>-8</sup>   = 0.00390625              ==> 0.59765625
2<sup>-9</sup>   = 0.001953125             ==> 0.599609375

2<sup>-12</sup>  = 0.000244140625          ==> 0.599853515625
2<sup>-13</sup>  = 0.0001220703125         ==> 0.5999755859375

2<sup>-16</sup>  = 0.0000152587890625      ==> 0.5999908447265625
2<sup>-17</sup>  = 0.00000762939453125     ==> 0.59999847412109375

2<sup>-20</sup>  = 0.00000095367431640625  ==> 0.59999942779541015625
2<sup>-21</sup>  = 0.000000476837158203125 ==> 0.599999904632568359375    
digit being approximated-------------------------------| <==
Accumulated trailing digits. ---------------------------^^^^^^^^^^^^^^

因此，当我们设置前 6 位数字时，我们已经使用了 21 个二进制数字，并且根据上面的结果，已经生成了 21 个十进制数字。但这些数字是不免费。它们与前 6 位十进制数字的值相关。

然而，尝试从特定示例生成一般规则是不可能的。

一般来说：

使用更高层次的数学，我们可以说：

问：对于截断的位数，多少个十进制数字是“有效”的？

答：2^(b-1) >= 10^d - 1

这是他 1967 年论文中的 Matula 公式：D._W.马图拉，“Base_conversion_mappings”，_1967_Spring_Joint_Computer_Conf.，_AFIPS_Proc.，_vol._30.，_pp._311-318

应用于十进制数字 (d) 转换为二进制数字 (b)

正如我们通常知道一个浮点数能够存储多少个二进制位，我们可以求解 d（往返 b 个二进制数字的十进制数字）：

2^(b-1) >= 10^d - 1 # 使用>唯一（去掉 - 1）
2^(b-1) > 10^d # 应用日志
log ₁₀ (2) × (b-1) > d

所以（最大整数）：

d = int( log ₁₀ (2) × (b-1) )
d = int( 0.30102999566 * (b-1) ) # 足够接近。

 Bits  5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101 105 109 113  
digits 1 2  3  4  6  7  8  9 10 12 13 14 15 16 18 19 20 21 22 24 25 26 27 28  30  31  32  33

如上所示，21 个二进制位生成 0.599999904632568359375，但只有 6 个（四舍五入）数字可以信任。 0.599999 必须向上舍入为 0.6，因为下一位是 9。

所以：0.6 往返二进制并再次变为 0.6。
具有 21 个二进制位：最多可以可靠地转换 6 位十进制数字。

最终的

那么，可以生成多少个（有效）数字rand：

使用的浮点数可以从二进制转换回尽可能多的浮点数。（使用上表）。

对于 53 位二进制来说，可信的数字不超过 15 个。

使用：

$ awk -M -vPREC=101 'BEGIN{printf("%.33g\n",0.6)}'
0.599999999999999999999999999999921

如果您需要浮点数至少有 30 位小数。

但还存在其他限制问题，例如 LFSR 代码中使用的位数。这是本答案开头提到的限制。

Answer

带走

除了下面详细解释的浮点限制（不超过 15 位十进制数字）之外，源代码还有以下额外限制：

最初的 awk 仅限于仅有的rand() 函数中存在 32768 (0..32767) 个不同的值。

/* #ifndef RAND_MAX */  
/* #define RAND_MAX     32767 */        /* all that ansi guarantees */  
/* #endif */

这比 4 位数字多一点，这就是旧 awk 中您可以信任的所有数字。

mawk 实现对 rand() 有几个限制，从 16 位到 32 位 (0..4294967295)。所以，有点多于 9 位数字。

奇怪的是，GNU awk 只会从random()(read support/random.c) 返回 31 位，尽管内置了任意精度的数学。仍然多于 9 位数字，但是 mawk arc4random 的一半（来自 BSD）（0..2147483647）。

让我们一步步深入研究 awk 中的浮点表示。

rand() 会给出多少位小数？

明显

显而易见的答案是：您要求多少（是的，大多数版本）：

$ awk 'BEGIN{srand(11); printf("%.83f\n",rand())}'
0.37904318086255550657170942940865643322467803955078125000000000000000000000000000000

用于srand(11)生成可重复的随机数。任何用户都应该获得相同的随机数（在 GNU awk 中，不同版本的 awk 可能会有所不同，但在重复调用和计算机上稳定）。

是的，位数可能比 83 多得多，并且将忠实地打印这么多位数。

但很明显，经过一些计数后，无论您要求多少，所有数字都会变为零。

有效的

如果你想数一下它们：

$ printf '%s' "  " $(seq 9)"_"{,,,,,}; echo; \
    awk 'BEGIN{srand(11); printf("%.63f\n",rand())}';\
    printf '  ';printf '^%.0s' $(seq 53); echo "<--- up to here"

  123456789_123456789_123456789_123456789_123456789_123456789_
0.379043180862555506571709429408656433224678039550781250000000000
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^<--- up to here

你会发现有 53 位十进制数字（至少在 Linux GNU 中）。

为什么是53？

这与 awk 中用于表示数字的二进制浮点数尾数中使用的二进制位数完全相同。好吧，至少与“双精度”浮点数（8字节浮点数）为由 IEEE 754 定义

问：是这个原因吗？二进制位数等于十进制位数吗？

答：一言以蔽之：是的。

证明

任何二元分数，即一个零后面跟着一个点，后面跟着几个二进制数字：

0.100110011

可以写成：

1 × 2 ^-1 + ₂_× 2 ^-2 + ₃ × 2 ^-3 + ....

对于某个_i二进制数字序列。

例如：

0.100110011
1×2 ^-1 + 0×2 ^-2 + 0×2 ^-3 + 1×2 ^-4 + 1×2 ^-5 + ....

删除零：

2 ^-1 + 2 ^-4 + 2 ^-5 + 2 ^-8 + 2 ^-9

因式分解 2 ^-9：

( 2 ⁺⁸ + 2 ⁺⁵ + 2 ⁺⁴ + 2 ¹ + 1 ) × 2 ^-9

括号内是一个整数二进制数：

100110011 #（十进制307）

这个分数实际上是一个二进制分数：

307 × 2 ^-9
307 / 2 ⁹

如果我们将分子和分母都乘以 5 ⁹我们得到：

307 × 5 ⁹ / 2 ⁹ × 5 ⁹
307 × 5 ⁹ / 10 ⁹
307 × 1953125 / 10 ⁹
599609375 / 10 ⁹
0.599609375

与二进制分数位数相同的十进制分数。

因此，所有二进制分数都可以转换（确切地) 化为点后位数完全相同的小数（分母的指数相同）。反之则不然。并非所有十进制分数都可以转换为二进制分数。

现在我们知道怎么做了：我们可以尝试更长的分数：

0.10011001100110011001100110011001100110011001100110011
10011001100110011001100110011001100110011001100110011₂ / 2⁵³
5404319552844595₁₀ / 2⁵³
5404319552844595₁₀ × 5⁵³ / 10⁵³
5404319552844595 × 11102230246251565404236316680908203125 / 10⁵³
59999999999999997779553950749686919152736663818359375 / 10⁵³
0.59999999999999997779553950749686919152736663818359375

这正是 awk 给出的0.653 位表示形式：

$ awk 'BEGIN{printf("%.60g\n",0.6)}'
0.59999999999999997779553950749686919152736663818359375

因此，53 位十进制数字是 awk 可以给出的 53 位尾数浮点数的最大值。

好吧，读作 53重要的数字，因为某些数字可能有前导零：

$ awk 'BEGIN{printf("%.90f\n",3^-20)}'
0.000000000286797199079244134930566254988964884631297280748185585252940654754638671875000000

自由数字。

问：但是所有浮点数（小数）都以 5 结尾，是否存在某种潜在的力量使数字不随机？

答：是的。

描述

任何二进制数字都有十进制的精确表示。如上所述，二进制分数是：

1 × 2 ^-1 + ₂_× 2 ^-2 + ₃ × 2 ^-3 + ....

_{对于 a i}的某个序列。每个指数的值是众所周知的：

2 ^-1 = 0.5
2 ^-2 = 0.25
2 ^-3 = 0.125
2 ^-4 = 0.0625
2 ^-5 = 0.03125
2 ^-6 = 0.015625
2 ^-7 = 0.0078125
2 ^-8 = 0.00390625
2 ^-9 = 0.001953125
2 ^-10 = 0.0009765625
...

我们可以看到为什么以及如何用连续的二进制分数来近似像 0.6 这样的数字。
添加的每个连续分数必须来自以下。所有分数都相加，无法返回到更小的值。

2 ^-1 = 0.5 ==> 0.5

第一个二进制数字贡献了 0.5，我们距离 0.6 还差 0.1。下一个：0.25和0.125之后的一个比需要添加的要大。所以，它们不能被使用。可以添加接下来的两个。第一个 2 ^-4 (0.0625) 小于 0.1 差值，可以相加。第二个 2 ^-5 (0.03125) 小于第一个留下的 0.375 差值，也可以相加。

2<sup>-1</sup>   = 0.5                     ==> 0.5
2<sup>-4</sup>   = 0.0625                  ==> 0.5625
2<sup>-5</sup>   = 0.03125                 ==> 0.59375
----------------------^ <== digit being approximated
-----------------------*** <== trailing digits of each fraction.

随着每个连续的二进制位添加到 0.6 的表示中，结果变得更接近该值：

2<sup>-8</sup>   = 0.00390625              ==> 0.59765625
2<sup>-9</sup>   = 0.001953125             ==> 0.599609375

2<sup>-12</sup>  = 0.000244140625          ==> 0.599853515625
2<sup>-13</sup>  = 0.0001220703125         ==> 0.5999755859375

2<sup>-16</sup>  = 0.0000152587890625      ==> 0.5999908447265625
2<sup>-17</sup>  = 0.00000762939453125     ==> 0.59999847412109375

2<sup>-20</sup>  = 0.00000095367431640625  ==> 0.59999942779541015625
2<sup>-21</sup>  = 0.000000476837158203125 ==> 0.599999904632568359375    
digit being approximated-------------------------------| <==
Accumulated trailing digits. ---------------------------^^^^^^^^^^^^^^

因此，当我们设置前 6 位数字时，我们已经使用了 21 个二进制数字，并且根据上面的结果，已经生成了 21 个十进制数字。但这些数字是不免费。它们与前 6 位十进制数字的值相关。

然而，尝试从特定示例生成一般规则是不可能的。

一般来说：

使用更高层次的数学，我们可以说：

问：对于截断的位数，多少个十进制数字是“有效”的？

答：2^(b-1) >= 10^d - 1

这是他 1967 年论文中的 Matula 公式：D._W.马图拉，“Base_conversion_mappings”，_1967_Spring_Joint_Computer_Conf.，_AFIPS_Proc.，_vol._30.，_pp._311-318

应用于十进制数字 (d) 转换为二进制数字 (b)

正如我们通常知道一个浮点数能够存储多少个二进制位，我们可以求解 d（往返 b 个二进制数字的十进制数字）：

2^(b-1) >= 10^d - 1 # 使用>唯一（去掉 - 1）
2^(b-1) > 10^d # 应用日志
log ₁₀ (2) × (b-1) > d

所以（最大整数）：

d = int( log ₁₀ (2) × (b-1) )
d = int( 0.30102999566 * (b-1) ) # 足够接近。

 Bits  5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101 105 109 113  
digits 1 2  3  4  6  7  8  9 10 12 13 14 15 16 18 19 20 21 22 24 25 26 27 28  30  31  32  33

如上所示，21 个二进制位生成 0.599999904632568359375，但只有 6 个（四舍五入）数字可以信任。 0.599999 必须向上舍入为 0.6，因为下一位是 9。

所以：0.6 往返二进制并再次变为 0.6。
具有 21 个二进制位：最多可以可靠地转换 6 位十进制数字。

最终的

那么，可以生成多少个（有效）数字rand：

使用的浮点数可以从二进制转换回尽可能多的浮点数。（使用上表）。

对于 53 位二进制来说，可信的数字不超过 15 个。

使用：

$ awk -M -vPREC=101 'BEGIN{printf("%.33g\n",0.6)}'
0.599999999999999999999999999999921

如果您需要浮点数至少有 30 位小数。

但还存在其他限制问题，例如 LFSR 代码中使用的位数。这是本答案开头提到的限制。

Question 2

我使用的是 GNU Awk 4.1.3，API：1.1（GNU MPFR 3.1.4，GNU MP 6.1.0）

我创建了一百万个精确到 10 位数字的随机数，并获得了 999744 个唯一值。这些值并没有切断我所看到的。然而，高值似乎比低值复制得更多，并且减少的速度快于低值的增长速度，所以我不确定分布是否是线性的。

Paul--) echo 1000000 | 
> awk 'BEGIN { srand();}
> { for (j = 0; j < $1; j++) 
>   printf ("%12.10f\n", rand()); }' > foo.rand
Paul--) wc foo.rand
 1000000  1000000 13000000 foo.rand
Paul--) sort foo.rand | uniq | wc -l
999744
Paul--) sort foo.rand | uniq -c | sort -n | head -n 5
  1 0.0000011418
  1 0.0000023860
  1 0.0000025611
  1 0.0000035479
  1 0.0000037365
Paul--) sort foo.rand | uniq -c | sort -nr | head -n 5
  2 0.9966602395
  2 0.9950194126
  2 0.9909849539
  2 0.9852069067
  2 0.9822554230

Answer

我使用的是 GNU Awk 4.1.3，API：1.1（GNU MPFR 3.1.4，GNU MP 6.1.0）

我创建了一百万个精确到 10 位数字的随机数，并获得了 999744 个唯一值。这些值并没有切断我所看到的。然而，高值似乎比低值复制得更多，并且减少的速度快于低值的增长速度，所以我不确定分布是否是线性的。

Paul--) echo 1000000 | 
> awk 'BEGIN { srand();}
> { for (j = 0; j < $1; j++) 
>   printf ("%12.10f\n", rand()); }' > foo.rand
Paul--) wc foo.rand
 1000000  1000000 13000000 foo.rand
Paul--) sort foo.rand | uniq | wc -l
999744
Paul--) sort foo.rand | uniq -c | sort -n | head -n 5
  1 0.0000011418
  1 0.0000023860
  1 0.0000025611
  1 0.0000035479
  1 0.0000037365
Paul--) sort foo.rand | uniq -c | sort -nr | head -n 5
  2 0.9966602395
  2 0.9950194126
  2 0.9909849539
  2 0.9852069067
  2 0.9822554230

自由数字。

答案1

明显

有效的

证明

自由数字。

描述

一般来说：

最终的

答案2

相关内容