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

在 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 好的同学可以试试可视化的库。

ipwx

2018-01-04 23:32:10 +08:00

读得太少，想得太多。

首先，随机数生成器得尽量减少相邻输出的关联性。这个 @alvinbone88 提到了。如果一个随机数生成器的相邻相关性太强，恭喜你，依赖这个随机数生成器的系统是存在安全漏洞，可以被攻击的。另外基于采样的各种蒙特卡洛算法在随机数生成器有相邻相关性的情况下都会 BOOOOOOOOOOOM。比如通过样本均值求期望（一种数值积分常用方法），相关性的存在会使得计算结果的方差上升，然后你的程序就跪了。

除了相关性，我觉得你的脑洞最糟糕的问题在于，你根本不知道这个“随机数生成器”生成的分布是什么。所以你既不能用它算东西（比如算积分），也不能用它产生别的分布（比如接受 /拒绝方法，借助一个均匀分布为代理来采别的分布的样本。一般用于别的分布非常难以采样，但是容易计算概率密度的情况）。根本不能拿来计算，那你这个随机数生成器到底有啥用？

GeruzoniAnsasu

2018-01-05 15:06:13 +08:00

随机不等于均匀
随机数的分布更不一定是正态分布

真随机数的生成其实很简单，引入随机用户输入即可，benchmark 结果的随机也是由于系统各种运行环境影响产生的，而环境因素与过去历史用户操作密切相关，你其实就是期望通过引入系统运行不稳定性来制造随机

然而系统稳定性是可控的，我们完全可预测可计算 bechmark 什么时候结束，对于你这个算法来说，实际上期望结果是稳定的，完全不随机。

既然期望都是不随机的，你怎么还会想用它来制造随机数？？？

就算误差无法避免，这个算法中也没有过程来放大误差，假设误差时间在 1ms 到 10ms 之间，那随机数种子就只有 1 到 10 这么点结果，随机性能好到哪里去？？？

如果想靠计时误差来产生非可预测随机，首先记时精度一定要够高，并且，需要多次记时并引入混沌过程放大误差结果并消除可逆性，这样才能使种子足够“无法预测”

但无法预测是不是等于随机，抱歉，仍不知道

产生一个不可预测数后，返回固定分布的数很简单，筛子就行