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

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

eastpiger

2018-01-04 16:12:26 +08:00

> 我这段代码是基于将近一个世纪计算机科学逻辑理论基础上写就的。

可是你的这个 topic 里的逻辑怕是都过不了一般大学本科的计算理论课程

另外 @winglight2016：

真随机数本身是一个数学定义，鉴于其容易证伪却几乎难以证真的特点，另外考虑到理想自然噪声本身也是一种理想化数学定义，并不见得真实存在。所以我们只能探讨的是有多大的可信度相信题主的思路。（但是试图证伪一个广泛接受的其他方案并不影响我们探讨楼主方案是否正确）

讨论问题不可能是没有前提的。我们只能假设前提为依据当前科学主流支持的理论为基础进行，这无可厚非。

至于现在人类科学到底是可信的还是胡扯的，That's not our business.

（当然作为科研工作者的一部分，我们还是倾向于相信它可能有一些是胡扯的。不然后人搞科研都要没饭吃了😂😂）

SuperMild

2018-01-04 16:13:28 +08:00

@begeekmyfriend 你钻牛角尖了。请看这个函数：

def func(x) ... return y

其中，x 是参数，省略号是纯代码计算过程，y 是结果。假设 y 就是我们讨论的对象：一个随机数。那么，当我们说 y 是一个纯代码产生的不依赖硬件的真随机数时，意思是指 x 不能与硬件、物理世界有关。

当 x 取自硬件或物理世界，只要 x 是真随机的，那我的计算过程只需要 y=x 就可以得出真随机数了，复杂的计算过程只相当于一个放大器，它可以放大随机效果，但它不是随机的源头。