GMP库的使用

发表于 更新于 分类于 本文字数： 2.8k 阅读时长 ≈ 5 分钟

概述

   GMP 是一个执行任意精度数值计算的可移植 C/C++ 库，它支持整数、有理数和浮点数。无论是对于低精度还是高精度计算，GMP 都可以提供很好的性能。

   GMP 的高性能来自于以下几点特性：使用字符串(fullword)作为基础数据类型；使用精心设计的算法；在底层，针对通用内部循环使用精心优化的汇编代码（支持不同的 CPU ）。

参考 GMP Manual。

安装

基本使用

头文件和库

主要头文件（支持C/C++编译器）：

1
2
3
4
#include <gmp.h>

// 对于 C++，也可直接使用<gmpxx.h>
#include <gmpxx.h>

如果需要使用带有FILE*参数的函数，需要增加<stdio.h>：

1
2
#include <stdio.h>
#include <gmp.h>

如果需要使用支持带有va_list参数的函数（如gmp_vprintf），需要增加 <stdarg.h>：

1
2
#include <stdarg.h>
#include <gmp.h>

编译应用程序时的链接选项：

1
2
3
4
$ gcc test.c -lgmp

# 对于 C++
$ g++ test.cpp -lgmpxx -lgmp

术语和类型

对于多精度整数，使用mpz_t类型：

1
2
3
mpz_t x, y, z;
struct {mpz_t x;};
mpz_t vec[20];

对于多精度分数（即有理数），使用mpq_t类型。
对于浮点数，使用mqf_t类型。

浮点数函数的形参类型和返回类型是其指数， 用 C 类型表示为mp_exp_t。mp_exp_t类型通常等价于long，出于效率考虑，在一些系统上可能为int。

limb 代表多精度数的一部分，该部分刚好可以填充到一个机器字中。对应的 C 类型为 mp_limb_t，它可能为 32 位或者 64 位。

一个多精度数的 limb 的个数使用mp_size_t类型表示。

一个多精度数的 bit 的个数使用 mp_bitcnt_t类型表示。

Random state 代表选择的算法和当前的状态数据，使用mp_randstate_t类型表示。

函数 API

在 GMP 库中有 6 种类型的函数：

  1. 对于有符号整数的计算，使用以mpz_ 开头的函数；这一类函数大约有 150 个。
  2. 对于有理数的计算，使用以mpq_开头的函数；
  3. 对于浮点数的计算，使用以mpf_开头的函数；
  4. 对于操作底层的原生数值类型，使用以mpn_开头的函数，关联的数据类型是mp_limb_t的数组。
  5. 设置custom allocation的函数；
  6. 生成随机数的函数。

变量

在对一个 GMP 变量赋值前，用户需要首先使用对应的初始化函数对它进行初始化。当该变量不再使用时，用户需要使用对应的清除函数清除它。示例如下：

1
2
3
4
5
6
7
8
9
10
11
void foo(void) {
    mpz_t n;
    mpz_init(n);
    
    for(int i=0; i<100; i++) {
        mpz_mul(n,...);
        ...
    }
    
    mpz_clear(n);
}

对于mpz_t这样的 GMP 类型，底层实现为单元素的数组。相应的变量实际上是 指针，它指向实际的对象(object)。如果使用C++的术语的话，变量是左值引用，对象是右值。 出于效率和正确性的考虑，不建议作对象拷贝（或者说右值拷贝），其内部成员也不应该被用户访问。

函数参数

在上一节，我们说 GMP 的变量实际上是左值引用，因此对于使用 GMP 变量作为其参数的函数，可以在函数体中修改其参数指向的数据内容。如果只是读参数指向的数据内容，可以将形参声明为const。示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void foo (mpz_t result, const mpz_t param, unsigned long n)
{
  unsigned long  i;
  mpz_mul_ui (result, param, n);
  for (i = 1; i < n; i++)
    mpz_add_ui (result, result, i*7);
}

int main (void)
{
  mpz_t  r, n;
  mpz_init (r);
  mpz_init_set_str (n, "123456", 0);
  foo (r, n, 20L);
  gmp_printf ("%Zd\n", r);
  return 0;
}

C++绑定

GMP 的 C++接口相对 C 接口来说，更加方便使用。如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <gmpxx.h>

using namespace std;

int main(int argc, char *argv[]) {
    mpz_class a, b, c;
    mpz_class d(0);
    
    a = 12500;
    b = "12300000000000";
    
    c = a+d;
    c = sqrt(c);
    
    mpf_class f("1.23e12");
    f = f * f;
    
    cout << a << " " << b << " " << c << " " << d << endl;
    cout << f << endl;
}

编译：

1
$ g++ -o cpp_binding_test cpp_binding_test.cpp -lgmp -lgmpxx

输出结果：

1
2
3
$ ./cpp_binding_test
12500 12300000000000 111 0
1.5129e+24

串行化

   如果我们在 MPI 编程中需要发送或者接收 mpz_class/mpf_class 的数据结构,该如何做呢?
参考: https://gmplib.org/list-archives/gmp-discuss/2002-December/000194.html