随机数

随机数一般可以用来仿真，抽样，生成测试数据来检验正确性。但生成真正的随机数是很难的，下面介绍一种伪随机数算法

线性同余伪随机数生成算法

序列周期取到模数n的称为满周期,c=0称为乘同余法, ,称为混合同余法

code实现

java中java.util.Random类的实现中，发生器的关键代码如下：

1
2
3

private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;

private static final long multiplier = 0x5DEECE66DL;
    private static final long addend = 0xBL;
    private static final long mask = (1L << 48) - 1;

    //如果是32位int,则
    protected int next(int bits) {
        long oldseed, nextseed;
        //用的是long类型
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            //线性同余,mask就是模数,模数取的是2的幂次，所以取余可以这样取
            nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        //转成int型
        return (int)(nextseed >>> (48 - bits));
    }

    public int nextInt() {
        return next(32);
    }

混合同余法满周期的数学原理

定理1

由(模数m,乘数a,增量c和初始值x0)所确定的线性同余序列达到满周期当且仅当：

(c,m)=1
对m的任一素因子p,有
如果4|m则，

a=1的特殊情况

如果 $则同余式变成$ ,显然满足条件2和条件3.且同余式有较简单的表达式:

当 周 期 为 时 ， 有 并 且

又(c,m)=1,故 $又$
这样就证明了充分性.

必要性在a=1时，条件2和条件3是显然满足的,(c,m)互素由 $可知成立$

注意 a=1不具有随机性;

又在 $的情况下$ 根据同余性质,

故下面都假设

下面根据计算机程序设计艺术-第2卷-第3章论文中来介绍一下充分性和必要性,主要思想是得出递推式和x0的关系,将模数m做素数分解,这样会得到一个重要的简化定理，模数m的周期等于模数m素数分解得到的所有因数周期的最小公倍数.

引理1(得到递推式)

设是产生的随机数序列,且,则有

其中

特别的，取 ,即有

证:(用数学归纳法)
当n=0显然成立;
假设当n=k时成立,则当n=k+1时,有

令,即有

引理2(模数做素数分解)

设是线性同余产生的随机数序列,周期为,对m做素数分解,,其中为素数,.

记是由(初始值,乘子,增量,模数)为确定的随机数序列,周期为 ,其中 , 则有：

,即

为

的最小公倍数

证: 先证明素数分解只有2个数的情况,即
故， $两者互素$ ,

,由

定义知：

故根据同余性质,

即

,于是

.同理有

不妨设,下证：

一方面,由周期定义知,,则,由前面的结论知，,从而由周期的定义知,,同理,故有最小公倍数的定义知,,

另一方面,设 $为任一公倍数$ ,则由h是周期的倍数知

递 推 由 的 定 义 由 前 面 结 论

同理有,

综合上面2式，根据同余性质有

故有周期的定义知,,又 $是的任一倍数$ ,
故
对于素数分解2个以上的，由归纳法可知结论成立

引理3(一个数论结论)

设p为素数, $且$ ,

如果 $则$ .

证:(二项式定理展开)
由条件知, $其中且是素数$ ,从而有

其 中

显然,

因 $即当$ ,在组合数中总是可以分出一个p来,凑出这个因子(可分为p=2和p>2来讨论),所以p整除Q中带有组合数的项,但还有单独1这一项，

故

,故

引理4(一个数论结论)

如果 ,则:

对 任 意 都 成 立

证:

则，

于是可以仍然满足引理3的条件，继续应用引理3，得到:

其 中

即

下面证充分性,即要证:

对 任 意 都 成 立

对分子因式分解，化简有

由 命 题 条 件 知 令 可 有 同 余 和 整 除 等 价 性

同 理 对 于 每 个 都 可 以 提 出 一 个 总 共 有 项 但 可 以 多 提 出 一 个 故 总 共 可 以 提 出

因此充分性的得证.
必要性是显然的.因为 $肯定包含一个的因子$

引理5(化简到初始值为0)

由(模数m,乘数a,增量c和初始值x0)所确定的线性同余序列达到满周期当且仅当 $的周期为$
证:
必要性:比较显然，达到满周期的含义是不论x0的初始值是多少都是满周期

充分性: 设另有2个序列, $其中只有初始值不同是满周期$

由 于 和 的 取 值 都 在 之 间 并 且 每 个 值 都 只 会 出 现 一 次 ， 记 经 过 次 迭 代

则 由 周 期 定 义 即

引理6(递推式的性质)

设 $其中为素数$ ,如果

是 使 得 的 最 小 正 整 数 则

当 时 当 时

证:

必要性(用反证法):

$如果$ ,则有

因为,可利用同余和整除的等价性有:

又

,故

,于是当

时

由 同 余 和 整 除 的 等 价 性

但由费马定理知,

,这里和假设矛盾,

p=2时,如果 $则或者$

(1). 如果 ,根据同余和整除等价性,有

等式右边是奇数等式左边是偶数,矛盾
(2). 如果 ,则由引理4知, $这与是最小的矛盾$ ,必要性得证

充分性:
设对于引理中p=2和p>=2的情况，都满足引理3的条件,并且重复应用引理3,可有:

每 次 方 则 模 次 数 加 其 中

,又由引理3的证明过程中，

,令x=a,有

,故有

其 中

特别的,有

这个同余式表示, $是的倍数即$ ,故 $是这种形式又根据同余式知故$

备注
这个引理的充分性的证明在Hull和Dobell的论文Random Number Generators是通过二项式定理展开来证明的

说实话，这段整除性分析我没看懂。在高德纳的书中，是采用引理3的结论来证明的,可以发现，证明方法也是在基于新知识不断改进的

定理1的证明

终于来到主定理的证明了

由引理5,只需要考虑初始值为的情况,由引理1,可以得到一个简单的通项表达式,

由引理2知,只需要证明达到满周期即可,因为m的素数分解各个部分都是互素的,最小公倍数就是它们的乘积
下设

必要性:

用反证法,若 ,则设 $中的项都是位于中$ , 则可以取到1,即

但是 $不互素故而$
,导出矛盾,条件1证毕,接下来,引理5可将命题化简为要证明:
当 $时序列满周期$ .由引理6的必要性知,定理1的必要性成立.

充分性：

还是有引理5,可将命题充分性化简为要证明:
当 $时满足条件条件条件前提下有序列满周期$ .由引理6的充分性知定理1的充分性成立

线性同余统计检验

频数检测
目的是检测待测试二进制序列中，“0”和“1” 数目是否近似相等。
块内频数检测
目的是确定在待测序列中，所有非重叠的长度为M位的块内的“0”和“1”的数目是否表现为随机分布。
还有其他的很多检验指标

线性同余理论检验

待研究补充中

乘线性同余

先直接给出下面的定理,证明待后续补充。当c=0时，由定理1知，不会达到满周期.但选择合适的模数和乘数可以使周期达到m-1,在实际中已经够用了。这一个定理由高斯在他的算术研究中给出.

定理2

当c=0时,可能的极大周期为 ,如果:

x0与m互素
a是以m为模的原根
其中 $是的欧拉函数值$

注意如果m为素数,则可得到长度为m-1的周期

其他随机数算法

梅森旋转算法

总结

随机数这块理论其实很复杂的,尤其是理论证明.不得不膜拜高德纳老爷子的功底.那几本计算机程序设计艺术太难懂了,起码数学专业的博士才能读懂大部分.不过读书是这样的,需要当你把知识基础补充好之后,才能读懂.不过这本书的作者高德纳老爷子是图灵奖的获得者,读不懂也很正常。虽然读不懂，但还是尽量去读，学习顶尖数学家的思想和思维方式.可能TAOCP要我花一辈子去读了吧
读了文献之后，你发现其实一个理论的完善不是一代人搞出来的,是逐步完善. 一开始随机数只证明了的特殊情况,后面证明了充分性,到我们这代才完整的把充分必要性说清楚

猫猫攻城狮的博客

线性同余

随机数