使用GMP库生成随机数

本文讲解使用GMP库生成随机数的方法，主要讲解gmp_randclass的使用方法。

算法初始化

GMP库提供状态初始化一共有三种方式，底层的函数分别如下：

1. gmp_randinit_mt (gmp_randstate_t state)
2. void gmp_randinit_lc_2exp (gmp_randstate_t state, const mpz_t a, unsigned long c, mp_bitcnt_t m2exp)
3. int gmp_randinit_lc_2exp_size (gmp_randstate_t state, mp_bitcnt_t size)

第一种方法使用的是梅森旋转算法。使用gmp_randclass初始化则可以写成如下代码：

gmp_randclass st(gmp_randinit_mt);

第二种方法使用的是线性同余算法，每次从旧状态\(X\)迭代出来的新状态\(X'\)满足\(X'=(aX+c) \bmod 2^{\texttt{m2exp}}\)。使用gmp_randclass初始化则可以写成如下代码：

// mpz_class a=13;
// unsigned long int c = 133;
// mp_bitcnt_t m2exp = 66;
gmp_randclass st(gmp_randinit_lc_2exp,a,c,m2exp);

第三种方法则是由第二种方法改进而来。同样使用线性同余算法，给定\(\mathtt{size}\)，那么\(a,c,\texttt{m2exp}\)从固定的表中选择，满足\(\mathtt{m2exp\ge size}\)。使用gmp_randclass初始化则可以写成如下代码：

// mp_bitcnt_t size = 64;
gmp_randclass st(gmp_randinit_lc_2exp_size,size);

需要注意的是，这种方法下参数size不能大于\(128\)。

此外还有一个方法gmp_randinit_default，这是GMP库中采用的默认初始化方法，也就是梅森旋转算法。也就是说，这个方法和gmp_randinit_mt是完全一样的。使用gmp_randclass初始化则可以写成如下代码：

gmp_randclass st(gmp_randinit_default);
// 与gmp_randclass st(gmp_randinit_mt);完全一样。

随机数种子

gmp_randclass中有一个方法gmp_randclass::seed()用来给当前状态赋予随机数种子。分别接受以下两种不同类型的种子输入：

void gmp_randclass::seed (unsigned long int s)
void gmp_randclass::seed (mpz_class s)

类似的，和使用srand(time(NULL))时一样，以time(NULL)传入随机数参数时，也可以写成：

gmp_randclass st(gmp_randinit_mt);
st.seed(time(NULL));

产生随机数

gmp_randclass中有三种产生整数的方法：

1. mpz_class gmp_randclass::get_z_bits (mp_bitcnt_t l)
2. mpz_class gmp_randclass::get_z_range (mpz_class n)
3. mpf_class gmp_randclass::get_f (mp_bitcnt_t prec)

第一种方法用于均匀产生\([0,2^{l}-1]\)中的所有\(l\)比特整数。其中入参还可以是mpz_class类型。

第二种方法用于均匀产生\([0,n-1]\)中的所有整数。

第三种方法用于均匀产生\([0,1)\)中的所有精确到前prec比特的小数。如果没有prec入参，那么生成的浮点数默认精度。

示例程序

为了保证程序能够复现，这里不引入时间作为随机数种子。

# include <bits/stdc++.h>
# include "gmpxx.h"
using namespace std;
int main(){
    gmp_randclass st(gmp_randinit_mt);
    // st.seed(time(NULL));
    const int N=20;
    mpz_class n = 1000;
    for(int i=0;i<N;i++){
        mpz_class r = st.get_z_range(n);
        gmp_printf("%Zd ",r);
    }
}

//Output: 116 331 303 963 456 225 827 381 99 649 395 975 566 213 694 254 629 303 597 980 

# include <bits/stdc++.h>
# include "gmpxx.h"
using namespace std;
int main(){
    gmp_randclass st(gmp_randinit_mt);
    //st.seed(time(NULL));
    const int N=20;
    mpz_class l = 4;
    for(int i=0;i<N;i++){
        mpz_class r = st.get_z_bits(l);
        gmp_printf("%Zd ",r);
    }
}

//Output: 4 11 15 3 8 1 11 13 3 9 11 15 6 5 6 14 5 15 5 4 

# include <bits/stdc++.h>
# include "gmpxx.h"
using namespace std;
int main(){
    gmp_randclass st(gmp_randinit_mt);
    //st.seed(time(NULL));
    const int N=20;
    mp_bitcnt_t prec = 20;
    for(int i=0;i<N;i++){
        mpf_class f = st.get_f(prec);
        gmp_printf("%.22Ff\n",f);
    }
}
/*Output:
0.7911262512207031250000
0.1536359786987304687500
0.0110311508178710937500
0.4970121383666992187500
0.7338333129882812500000
0.6095895767211914062500
0.6580152511596679687500
0.0511445999145507812500
0.4043912887573242187500
0.9683923721313476562500
0.8597517013549804687500
0.8515157699584960937500
0.2153835296630859375000
0.0910234451293945312500
0.4176540374755859375000
0.1262187957763671875000
0.3004045486450195312500
0.4612264633178710937500
0.7027177810668945312500
0.9579658508300781250000
 */