这是一个创建于 2516 天前的主题，其中的信息可能已经有所发展或是发生改变。
在 OJ 平台上刷题注意到一个现象，有的题用同一份代码，测试 benchmark 落点很稳定，有的在一个时间区间范围内跳跃，不太稳定。用方差描述的话叫做，benchmark 稳定方差小，不稳定方差大。
这就让我突发奇想，能否用一段代码的 benchmark 作为随机数？如果是真·随机数，那么这段代码岂不是可以用来作为随机数生成器了？
如何检验随机性？我考虑可以用 benchmark 落点概率分布来衡量。我设计了一套简陋的代码，其中调用了一些库函数 /系统函数，包括 random、usleep、malloc、free，还有 clock_gettime 用做 benchmark。循环 N 次，统计 benchmark 的所有落点，在终端输出，能够观测概率分布。代码在gist上。翻墙不便的直接贴出来
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
int main(void)
{
int i, j, k;
int dim = 11;
int num = 1024 * 1024;
int loop = 1000;
struct timespec start, end;
size_t stat[200] = { 0 };
for (k = 0; k < loop; k++) {
usleep(50000);
srandom(time(NULL));
clock_gettime(CLOCK_MONOTONIC, &start);
for (i = 0; i < num; i++) {
double *vector = malloc(dim * sizeof(double));
for (j = 0; j < dim; j++) {
vector[j] = (double) random() / RAND_MAX * 20 - 10;
}
free(vector);
}
clock_gettime(CLOCK_MONOTONIC, &end);
size_t rand_ms = (end.tv_sec - start.tv_sec)*1000 + (end.tv_nsec - start.tv_nsec)/1000000;
stat[rand_ms]++;
}
for (i = 0; i < sizeof(stat)/sizeof(*stat); i++) {
printf("[%d](%f\%):", i, 100.0 * stat[i] / loop);
for (j = 0; j < stat[i]; j++) {
putchar('-');
}
putchar('\n');
}
return 0;
}
目前循环次数为 1000，运行时间大约 4~5 分钟（机器好可以缩短到 3~4 分钟），我曾经设成 10W 次迭代跑了一个晚上。 原先预想的是，假设系统（或 runtime ）稳定的话，benchmark 落点应该近似于正态分布。遗憾的是从终端输出上看，并没有达到随机的效果，但又不是收敛到一个稳定值上，分布比较离散化。
我的几点疑问：
- 是什么造成了同样一段代码的 benchmark 落点存在偏差：random、usleep、malloc or clock_gettime ？
- 假如改动代码逻辑能够调整 benchmark 的期望值和方差的话，能否做到正态分布？
- 能否用纯粹的代码得到真·随机数？
由于仅凭终端输出，这段 C 代码在可视化上有局限，特别当样本量很大的话。Python 好的同学可以试试可视化的库。
第 1 条附言 · 2018-01-04 15:25:24 +08:00
还有一个疑问，就是每次迭代的 benchmark 样本，是否满足独立同分布的假设？
第 2 条附言 · 2018-01-04 16:09:06 +08:00
说随机性不好的同学，可以用
size_t rand_ns = (end.tv_nsec - start.tv_nsec) % 1000
替代rand_ms
 |
1
eastpiger 2018-01-04 14:23:31 +08:00
不可能
存在偏差的原因很复杂，OS 底层上看到的，或许有进程调度问题，有 IO 请求的延迟等待，有可能遇到内存页 miss，有可能即将执行的指令被 CPU 尝试预测到了等等。尽管看起来很复杂，但是这些大部分在系统层面都是可预测的可重现的。而且分布不可预测。目测并不会有很均匀的随机效果 > 假设系统（或 runtime ）稳定的话 如何定义一个系统是“稳定”的呢。扣字眼一点的话，只有正常运转与不正常运转之分。压力大与小只要没有崩溃，这个系统都是稳定正确的呢。 一般情况下也不是很需要真随机数的吧。真的特别需要的话，https://www.random.org/ 是个好选择。 |
 |
2
begeekmyfriend OP @eastpiger 分布不均匀的话，还能否等同于随机？或者说随机数生成器必须是均匀分布的？
|
|
3
eastpiger 2018-01-04 14:45:05 +08:00
> Randomness is the lack of pattern or predictability in events.[1] A random sequence of events, symbols or steps has no order and does not follow an intelligible pattern or combination. Individual random events are by definition unpredictable, but in many cases the frequency of different outcomes over a large number of events (or "trials") is predictable. For example, when throwing two dice, the outcome of any particular roll is unpredictable, but a sum of 7 will occur twice as often as 4. In this view, randomness is a measure of uncertainty of an outcome, rather than haphazardness, and applies to concepts of chance, probability, and information entropy.
来自 wikipedia 词条 Randomness 个人理解，随机与分布没有相关性。随机的定义是围绕在数据不可预测和无规律上。而分布究竟如何，并不是一个限制条件，只是不同类型的随机分布的 feature 罢了。 |
|
4
begeekmyfriend OP @eastpiger 既然满足不可预测和无规律这个条件就可以定义为“随机”的话，我觉得貌似存在一些参数，或一些技巧，可以将程序设计成运行时间“不可预测和无规律”的，比如我现在的随机值是 ms，那我可以用 ns 然后取余行不行？
|
 |
5
JKeita 2018-01-04 14:52:55 +08:00
只要是代码生成的都是假随机数吧。
|
|
6
begeekmyfriend OP @JKeita 如何证伪？
|
 |
7
fcten 2018-01-04 15:06:28 +08:00
结果确实是随机数，但是随机性不好，缺少实用价值
顺便，这个随机数算法的性能太差了 |
|
8
begeekmyfriend OP @fcten 性能其实不是问题，总是可以优化的，你甚至可以用底层语言去实现一个。至于随机性，我说过用 ns 取余等技巧。问题是如果是真·随机，那么已经证明纯代码是可以生成真·随机数的。
|
 |
9
akira 2018-01-04 15:25:05 +08:00
真·随机数 是否存在是个哲学问题。
纯代码生成随机数，因为机器的状态是有限的，最终在数学上是可以证明有规律的。也就是公认的伪随机数了。 目前常见的号称 真·随机数的做法，都是依赖外部物理输入来产生的。 |
|
10
begeekmyfriend OP @akira 宇宙的粒子数目也是有限的，那么状态也是有限的，难道这证明宇宙不存在随机？
|
|
11
eastpiger 2018-01-04 15:30:45 +08:00
这里看你的真随机数定义是怎么样了。
目前常见理解里，最为严格的定义观点来看，这个世界上只有一种真随机：取量子观测数据。 而目前比较广泛接受的稍微弱化一些的定义，一般认为来自物理学环境观测的数据属于真随机。常见用于各种硬件随机数生成器，比如热噪声或者光噪声采集卡。这种数据本身弱于量子观测数据，但是对于当前人类技术而言也还算可以、 至于程序生成的各种算法上。除了民用日用的并不严格的领域以外，基本上也没人承认过其能达到真随机的地步。 |
 |
12
MonoLogueChi 2018-01-04 15:32:24 +08:00 via Android
按分布密度来说，现在能找到的随机数生成放到应该都能生成分布密度符合要求的随机数，但是从定义上来说，这些随机数都不是真随机数。想要验证可以把生成的随机数保存成日志，然后分析这些随机数的分布概率密度
|
|
13
begeekmyfriend OP @MonoLogueChi 也存在无法分析概率密度的随机值
|
|
14
eastpiger 2018-01-04 15:34:47 +08:00
> 宇宙的粒子数目也是有限的，那么状态也是有限的，难道这证明宇宙不存在随机？
有限数据与随机性并无直接关联。有限数据是可以构成不可预测的随机序列的。 况且量子观测数据的理论重点在于其在观测前，叠加态无法预测 CPU 的运转这种相比之下已经很宏观的事情，还没有这个底气跟量子力学比试比试，甚至就连比比物理噪声都差得远 |
|
15
begeekmyfriend OP @eastpiger 谁说 CPU 运行就没有物理噪声了？
|
|
16
fcten 2018-01-04 15:39:25 +08:00
@begeekmyfriend
1、O(n)的算法再怎么优化也不可能实现 O(1)的性能 2、这不是代码产生的随机数，代码产生的随机数应当与硬件无关，而 CPU 运算时间是一个与硬件有关的数据 3、依赖硬件产生真随机数的方法有很多 |
|
17
eastpiger 2018-01-04 15:41:53 +08:00
当然可以认为 everything 都受到物理噪声的影响。但是 CPU 并不是噪声发生器，其本身信号数据的信噪比非常高（不然我们的电脑还怎么运转呢）。你给出的方法更大程度上取决于 OS 层级的调度，CPU 层级的优化和实现，时钟信号和外部重点数据 IO，噪声在内部根本就是忽略不计的量级。
所以说啊，不能因为 CPU 本身有噪声，就认为 CPU 拿到的数据就是噪声影响的。实际上很可能那点噪声的影响根本都不到一个最小观测单位呢。 楼主小心走向啊民科啊 [逃 |
|
18
begeekmyfriend OP @fcten
1、O(1)也是可以的，实际上 OJ 刷题是就碰到过用 hashmap 的题目 benchmark 在区间跳跃的，这些都是技巧实现细节的问题 2、样本就是 benchmark，这不是代码生成还是什么生成的？ 3、纯代码生成真·随机的不知还有啥方法？ |
 |
19
nigelvon 2018-01-04 15:45:39 +08:00
和粒子数有啥关系，0 和 1 两种状态就够了啊。
|
|
20
begeekmyfriend OP @eastpiger 我不是民科，我是炼丹，就跟机器学习一样，真炼出来就“科学”了。另外，就算很大程度上依赖于 OS 调度，CPU 时钟等，那就说明真·随机数生成器本身是可以被设计的。
|
|
21
fcten 2018-01-04 15:52:13 +08:00  1
@begeekmyfriend
我已经说了，benchmark = CPU 运算时间，这是硬件输出的结果。如 17 楼所说，你是把 CPU 作为了噪声发生器。CPU 是一个硬件，不是代码的一部分。 如果你觉得这是纯代码生成的随机数，那么任何程序通过传感器、磁盘 IO 时间、键盘输入、鼠标位置等数据产生随机数也可以认为是纯代码生成的随机数。 |
|
22
eastpiger 2018-01-04 15:54:11 +08:00
楼主确实像炼丹，而不是现代制药
区别在于后者是在现有理论和逻辑学定义基础内的发展和研究，前者是一股脑扔进去看看。 不过也不是说这样没用，毕竟上次炼丹成功的那位，不是发明了火药了嘛:-D 最严格的真随机数生成器，比如对量子态的观测数据，是不可被设计和预测的。（除非楼主打算把量子力学也革命一发了） |
|
23
begeekmyfriend OP @fcten 你见过什么代码不依赖硬件的，把代码送给你，输出给我看？
|
|
24
begeekmyfriend OP @eastpiger 我这段代码是基于将近一个世纪计算机科学逻辑理论基础上写就的。
|
|
25
fcten 2018-01-04 15:57:37 +08:00
|
|
26
begeekmyfriend OP @fcten 你是说没有硬件你只能算 1+1=2 了是吧？我通过对一个计算机编程来生成随机数，本身有问题吗？
|
|
27
fcten 2018-01-04 16:01:42 +08:00 2
@begeekmyfriend 没问题啊，但是这不是什么大发现，也没有必要在 v2 上发帖
这看上去就好像“我发现太阳每天是从东边升起来的”一样可笑 |
 |
28
winglight2016 2018-01-04 16:03:07 +08:00
个人觉得，大家之所以认为微观粒子的量子态是 i.i.d，只是因为量子态就是这么定义的，但是，是不是客观事实（真随机），也没法通过观测证实，换句话说，还是用了数学模型去套的，只是精度很高、吻合得很好，所以，这种随机性如果可以衡量的话，跟 netflix 那个熔岩随机发生器可能差不多
|
 |
29
zhx1991 2018-01-04 16:05:21 +08:00 1
只有量子是真随机
|
|
30
eastpiger 2018-01-04 16:12:26 +08:00
> 我这段代码是基于将近一个世纪计算机科学逻辑理论基础上写就的。
可是你的这个 topic 里的逻辑怕是都过不了一般大学本科的计算理论课程 另外 @winglight2016： 真随机数本身是一个数学定义，鉴于其容易证伪却几乎难以证真的特点，另外考虑到理想自然噪声本身也是一种理想化数学定义，并不见得真实存在。所以我们只能探讨的是有多大的可信度相信题主的思路。（但是试图证伪一个广泛接受的其他方案并不影响我们探讨楼主方案是否正确） 讨论问题不可能是没有前提的。我们只能假设前提为依据当前科学主流支持的理论为基础进行，这无可厚非。 至于现在人类科学到底是可信的还是胡扯的，That's not our business. （当然作为科研工作者的一部分，我们还是倾向于相信它可能有一些是胡扯的。不然后人搞科研都要没饭吃了😂😂） |
 |
31
takato 2018-01-04 16:13:12 +08:00
see:
 观测结果上，很多计算机随机出来的东西都是可以被深度学习压缩的。。也就是客观上存在“规律” 所以我个人认为用“巨观物体”其实是不可能做出真随机的。。 |
 |
32
SuperMild 2018-01-04 16:13:28 +08:00
@begeekmyfriend 你钻牛角尖了。请看这个函数：
def func(x) ... return y 其中，x 是参数，省略号是纯代码计算过程，y 是结果。假设 y 就是我们讨论的对象：一个随机数。那么，当我们说 y 是一个纯代码产生的不依赖硬件的真随机数时，意思是指 x 不能与硬件、物理世界有关。 当 x 取自硬件或物理世界，只要 x 是真随机的，那我的计算过程只需要 y=x 就可以得出真随机数了，复杂的计算过程只相当于一个放大器，它可以放大随机效果，但它不是随机的源头。 |
|
33
begeekmyfriend OP @SuperMild 你的模型想的太狭隘了，def benchmark(code) ... return y，代码难道不能作为数据输入？
|
|
34
SuperMild 2018-01-04 16:29:11 +08:00 1
@begeekmyfriend 你连 x 是什么也不懂吗？ x 可以是任何，当然也可以是代码。
重点是在你的模型中，你输入了一个 “ CPU 运算时间”，这个东西不是纯代码产生的。你依赖了一个硬件的误差。 注意，纯代码无法产生误差，误差是硬件产生的。 |
|
35
begeekmyfriend OP @SuperMild 你的意思是纯代码就必须是 immutable 的？这并不成立
|
|
36
SuperMild 2018-01-04 16:35:21 +08:00
@begeekmyfriend 你是怎么联想到 immutable，能不能分享一下心路历程？
|
|
37
winglight2016 2018-01-04 17:26:16 +08:00
@eastpiger 数学定义是没什么问题了，只是既然在讨论程序中的实现哪一个随机性更好，这就不是数学理论一定证明的结论，所以我的观点是，微观粒子的随机性仅仅是数学定义，既没法通过实验证实真随机性，也没法去和熔岩随机数去比较哪一个“更”随机，那么观察熔岩可能是最佳的方案之一了
|
 |
38
fyyz 2018-01-04 19:23:50 +08:00 via Android
楼主这么倔大家还是不要和他讲道理了吧，我看他也听不进去
|
 |
39
Shura 2018-01-04 19:27:46 +08:00
人为不可能实现真随机的，只能通过物理实现。
|
 |
40
wecan 2018-01-04 19:37:43 +08:00 via Android
楼主真为你捉急
|
 |
41
facetest 2018-01-04 21:16:12 +08:00 via Android
不要以为代码行数多，看起来复杂就是真随机，之前听说过有些真随机数是用地球实时大气数据来生成的。
|
 |
42
teloti 2018-01-04 21:30:31 +08:00
楼主是不是不太懂硬件……
entropy source （ https://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide ） |
 |
43
Valyrian 2018-01-04 21:43:05 +08:00
clock_gettime usleep 这些都是实实在在的方程，没有任何随机性。里面会像内核发 system call，然后内核会运行一些明确定义的代码。代码会在明确定义的 cpu 速度下运行，没有随机性
|
 |
44
jason2017 2018-01-04 22:16:11 +08:00
真随机，目前只存在量子力学中。
而且，未来可能证实量子力学也未必是真随机。 |
 |
45
alvinbone88 2018-01-04 23:10:17 +08:00
|
 |
46
hjuj91 2018-01-04 23:19:21 +08:00
确定状态机怎么搞也搞不出真随机的
|
 |
47
ipwx 2018-01-04 23:32:10 +08:00
读得太少，想得太多。
首先，随机数生成器得尽量减少相邻输出的关联性。这个 @alvinbone88 提到了。如果一个随机数生成器的相邻相关性太强，恭喜你，依赖这个随机数生成器的系统是存在安全漏洞，可以被攻击的。另外基于采样的各种蒙特卡洛算法在随机数生成器有相邻相关性的情况下都会 BOOOOOOOOOOOM。比如通过样本均值求期望（一种数值积分常用方法），相关性的存在会使得计算结果的方差上升，然后你的程序就跪了。 除了相关性，我觉得你的脑洞最糟糕的问题在于，你根本不知道这个“随机数生成器”生成的分布是什么。所以你既不能用它算东西（比如算积分），也不能用它产生别的分布（比如接受 /拒绝方法，借助一个均匀分布为代理来采别的分布的样本。一般用于别的分布非常难以采样，但是容易计算概率密度的情况）。根本不能拿来计算，那你这个随机数生成器到底有啥用？ |
 |
48
kanex 2018-01-05 00:55:21 +08:00
lz 需要补习一些密码学基础知识，这样的代码是不可能生成真随机数的，生成的结果必定会存在一些概率（等等）模型上的 pattern
|
 |
49
lepig 2018-01-05 09:09:32 +08:00
感觉楼上在神仙打架 我看不懂
|
 |
50
arzterk 2018-01-05 09:28:21 +08:00
楼主的算法跟从一个内存里面随机位置读个数没啥区别啊
|
 |
51
bramblex 2018-01-05 09:31:16 +08:00
楼主，你心里有民科的种子呀。
|
 |
52
xAx 2018-01-05 09:50:27 +08:00
请搜索伪随机，向楼上说的，这是民科
|
 |
53
zzNucker 2018-01-05 10:34:56 +08:00
楼主可能是语文学的不好，一个输入和纯代码的问题给他说了好几楼了都没转过来
|
 |
54
youxiachai 2018-01-05 10:52:39 +08:00 3
土法炼随机数.....
反正这种时候...lz 开心就好了... 我们点头是是是就好了.. |
 |
55
eurokingbai2 2018-01-05 11:11:21 +08:00
确实伪随机。你这段代码放到一个嵌入式芯片的单进程系统上跑，近乎于等值输出。
|
 |
56
realpg 2018-01-05 13:10:08 +08:00
连真随机数是啥都不知道的就可以写真随机算法了……
我觉得还是别用什么 benchmark 了还得写代码，直接读一下风扇转速当随机数就行 |
 |
58
fantasua 2018-01-05 14:50:50 +08:00
不是说真正的随机数只存在现实世界中的物理现象中么，比如高斯白噪声什么的
|
 |
59
860670496 2018-01-05 14:51:05 +08:00
@begeekmyfriend #10 单纯针对这楼发表一下意见，应该修正为“可观测宇宙”的“原子”数量是有限的，大约为 10^79，粒子数量暂时无法估计（拼图拼完了没有都还模糊着呢
另外我也觉的真随机数的定义就极难用实践方法证明 |
 |
60
GeruzoniAnsasu 2018-01-05 15:06:13 +08:00
随机不等于均匀
随机数的分布更不一定是正态分布 真随机数的生成其实很简单，引入随机用户输入即可，benchmark 结果的随机也是由于系统各种运行环境影响产生的，而环境因素与过去历史用户操作密切相关，你其实就是期望通过引入系统运行不稳定性来制造随机 然而系统稳定性是可控的，我们完全可预测可计算 bechmark 什么时候结束，对于你这个算法来说，实际上期望结果是稳定的，完全不随机。 既然期望都是不随机的，你怎么还会想用它来制造随机数？？？ 就算误差无法避免，这个算法中也没有过程来放大误差，假设误差时间在 1ms 到 10ms 之间，那随机数种子就只有 1 到 10 这么点结果，随机性能好到哪里去？？？ 如果想靠计时误差来产生非可预测随机，首先记时精度一定要够高，并且，需要多次记时并引入混沌过程放大误差结果并消除可逆性，这样才能使种子足够“无法预测” 但无法预测是不是等于随机，抱歉，仍不知道 产生一个不可预测数后，返回固定分布的数很简单，筛子就行 |
|
61
begeekmyfriend OP @GeruzoniAnsasu 我的确是引入系统运行环境的误差来，引入随机性。至于期望的可预测性，可以通过纳秒取余等一些附加技巧解决，这样的随机数很难预测分布，也就是说可以引入附加处理获得熵增。
|
 |
62
KevZhi 2018-01-05 16:40:54 +08:00
你为什么不把这段代码产生的随机数生成一个 bitmap 呢？
如果你的随机数是一个伪随机数，通过足够大的 bitmap 很容易就能看出露馅了。 这种土法练真随机数的问题还是不要拿到 V2EX 上来问了，blocked |
 |
63
ZackB0T 2018-01-05 17:09:50 +08:00 via Android
“ RNG 处理器是一个以连续模拟噪声为基础的随机数发生器，在主机读数时提供一个 32 位的随机数。”
没有硬件估计是做不到的。 |
 |
64
noNOno 2018-01-05 17:15:09 +08:00
是是是...
|
 |
65
mooncakejs 2018-01-05 17:19:21 +08:00 1
是，这是真的随机数，“图灵奖” 拿去。
|
 |
66
sutra 2018-01-05 17:35:04 +08:00
实际上只要给定边界条件，真随机数并不存在。
|
|
67
sutra 2018-01-05 17:43:10 +08:00
我们可以收集硬件中断时间间隔、键盘敲击、WiFi 信号强度变化等外部信号来作为随机数等种子，在该计算机范围内并不能重现该随机数，但是我们把边界扩展到这些外部信号所在到时空时，则又是可以重现的。
|
 |
68
xlrtx 2018-01-05 17:49:47 +08:00
随机, 信息熵, 压缩, 第二热力学定律, 量子力学
另外一个脑洞 |
 |
69
t6attack 2018-01-05 17:53:22 +08:00
“真随机”不是计算机问题，是物理学问题。
就连抛硬币都是伪随机，只要计算条件绝对充分，结果是可预测的。 |
 |
70
jjianwen68 2018-01-05 17:58:35 +08:00
https://www.onlinegdb.com/ compile failed
|
|
71
begeekmyfriend OP @jjianwen68 Its runtime sucks...
|
 |
72
MeteorCat 2018-01-05 18:50:45 +08:00 via Android
一般上概率分布图
|
 |
73
jimzhong 2018-01-06 05:10:10 +08:00
取决于你如何定义“随机”。如果只要求均匀分布的话，很多算法都可以做到。但是密码学里面的随机数有更严格的要求，请看 https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator
@t6attack 微观世界很多现象是随机的，可以通过观测物理现象（比如热噪声，放射性元素衰变）获得真随机数。很多 crypto coprocessor 里有真随机数生成器。部分 Intel 处理器里面也有。 |
 |
76
Admstor 2018-01-06 12:35:38 +08:00
你要求均匀分布本身就不"随机"
例如简单的一个四象,如果已经三个象限各有一个点了,如果算法要保证均匀分布,那么几乎可以肯定下一个点必然出现在没有点的那个象限 均匀分布是随机的结果,但并不是保证随机的前提 也就是说,你观察到你的结果是均匀分布,但是并不能说你这个算法是足够真随机 真随机完全可以出现所有结果都出现在同一个象限的情况 |
|
77
begeekmyfriend OP @Admstor 实际上我的测试样本分布并不均匀啊
|
 |
79
nyanyh 2018-01-07 00:07:31 +08:00
散了吧，LZ 坚持他自己的想法并且只反驳他有能力反驳的，上面那么多人给了充足的理由都视而不见
|
Select Language