这段代码是否生成真·随机数

2018-01-04 14:12:42 +08:00
 begeekmyfriend

在 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 落点应该近似于正态分布。遗憾的是从终端输出上看,并没有达到随机的效果,但又不是收敛到一个稳定值上,分布比较离散化。

我的几点疑问:

由于仅凭终端输出,这段 C 代码在可视化上有局限,特别当样本量很大的话。Python 好的同学可以试试可视化的库。

5092 次点击
所在节点    程序员
79 条回复
begeekmyfriend
2018-01-05 15:53:42 +08:00
@GeruzoniAnsasu 我的确是引入系统运行环境的误差来,引入随机性。至于期望的可预测性,可以通过纳秒取余等一些附加技巧解决,这样的随机数很难预测分布,也就是说可以引入附加处理获得熵增。
KevZhi
2018-01-05 16:40:54 +08:00
你为什么不把这段代码产生的随机数生成一个 bitmap 呢?
如果你的随机数是一个伪随机数,通过足够大的 bitmap 很容易就能看出露馅了。

这种土法练真随机数的问题还是不要拿到 V2EX 上来问了,blocked
ZackB0T
2018-01-05 17:09:50 +08:00
“ RNG 处理器是一个以连续模拟噪声为基础的随机数发生器,在主机读数时提供一个 32 位的随机数。”
没有硬件估计是做不到的。
noNOno
2018-01-05 17:15:09 +08:00
是是是...
mooncakejs
2018-01-05 17:19:21 +08:00
是,这是真的随机数,“图灵奖” 拿去。
sutra
2018-01-05 17:35:04 +08:00
实际上只要给定边界条件,真随机数并不存在。
sutra
2018-01-05 17:43:10 +08:00
我们可以收集硬件中断时间间隔、键盘敲击、WiFi 信号强度变化等外部信号来作为随机数等种子,在该计算机范围内并不能重现该随机数,但是我们把边界扩展到这些外部信号所在到时空时,则又是可以重现的。
xlrtx
2018-01-05 17:49:47 +08:00
随机, 信息熵, 压缩, 第二热力学定律, 量子力学
<amp-youtube data-videoid="sMb00lz-IfE" layout="responsive" width="480" height="270"></amp-youtube>
另外一个脑洞
<amp-youtube data-videoid="loaw30eqC5o" layout="responsive" width="480" height="270"></amp-youtube>
t6attack
2018-01-05 17:53:22 +08:00
“真随机”不是计算机问题,是物理学问题。
就连抛硬币都是伪随机,只要计算条件绝对充分,结果是可预测的。
jjianwen68
2018-01-05 17:58:35 +08:00
begeekmyfriend
2018-01-05 18:07:46 +08:00
@jjianwen68 Its runtime sucks...
MeteorCat
2018-01-05 18:50:45 +08:00
一般上概率分布图
jimzhong
2018-01-06 05:10:10 +08:00
取决于你如何定义“随机”。如果只要求均匀分布的话,很多算法都可以做到。但是密码学里面的随机数有更严格的要求,请看 https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator

@t6attack 微观世界很多现象是随机的,可以通过观测物理现象(比如热噪声,放射性元素衰变)获得真随机数。很多 crypto coprocessor 里有真随机数生成器。部分 Intel 处理器里面也有。
honeycomb
2018-01-06 11:38:42 +08:00
@jimzhong Linux 内核不信任 intel 那个随机数生成器
jimzhong
2018-01-06 12:03:10 +08:00
@honeycomb 这样啊,大部分 TPM 也提供 TRNG
Admstor
2018-01-06 12:35:38 +08:00
你要求均匀分布本身就不"随机"
例如简单的一个四象,如果已经三个象限各有一个点了,如果算法要保证均匀分布,那么几乎可以肯定下一个点必然出现在没有点的那个象限

均匀分布是随机的结果,但并不是保证随机的前提
也就是说,你观察到你的结果是均匀分布,但是并不能说你这个算法是足够真随机

真随机完全可以出现所有结果都出现在同一个象限的情况
begeekmyfriend
2018-01-06 12:51:09 +08:00
@Admstor 实际上我的测试样本分布并不均匀啊
eastpiger
2018-01-06 23:27:00 +08:00
@LeoNG 移植完主题之后就在赶 paper,两三个月没 care 过博客的事情了
(其实主要是我懒啦)
nyanyh
2018-01-07 00:07:31 +08:00
散了吧,LZ 坚持他自己的想法并且只反驳他有能力反驳的,上面那么多人给了充足的理由都视而不见

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/420022

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX