GMP库使用方法

时间:2024-05-19 09:24:22

 

 

Linux 下安装GMP库

GMP库使用方法GMP库使用方法

下面是一些常用的大数运算库的地址(有些虽然不是专门的大数运算库,但是带有相关的库)

Crypto++:http://www.eskimo.com/~weidai/cryptlib.html

MIRACL:https://github.com/CertiVox/MIRACL

GNU MP:http://www.swox.com/gmp/

Piologie: http://www.hipilib.de/pidownload.htm

cryptlib:http://www.cs.auckland.ac.nz/~pgut001/cryptlib/

RSAEuro:http://www.rsaeuro.com/products/RSAEuro/

OpenSSL:http://www.openssl.org/

RSARef:http://download.gale.org/rsaref20.tar.Z

GInt:http://triade.studentenweb.org/GInt/gint.html(Delphi)

 

GMP库使用方法

sudo apt-get install m4

如果要增加C++支持,./configure的时候加上--enable-cxx参数。

使用configure的时候要加上 --enable-cxx命令,否则不能使用c++库gmpxx.h

 

新建test.cpp文件

#include <gmpxx.h>

#include <iostream>

#include <stdio.h>

using namespace std;

int main()

{

        mpz_t a,b,c;

        mpz_init(a);

        mpz_init(b);

        mpz_init(c);

        gmp_scanf("%Zd%Zd",a,b);

        mpz_add(c,a,b);

        gmp_printf("c= %Zd\n",c);

        return 0;

}

编译

g++ test.cpp -o test -lgmp

GMP库使用方法GMP库使用方法

GMP库使用方法GMP库使用方法

GMP库使用方法

 

下面我们以求10000!为例说明如何使用gmp。要使用gmp必须先包含gmp的头文件:

 

#include <gmp.h>

求10000!我们需要的数据类型是整数,当然需要的是多精度整数,定义一个多精度整数(multiple precision integer)变量可以用:

 

mpz_t num;

现在我们需要定义三个变量:

 

mpz_t z_i, z_s, z_o;

分别用来迭代1..10000之间的数字、保存结果、保存1这个数字以使得z_i自增。可以用字符串来给多精度数字初始化为一个大数:

 

mpz_init_set_str(z_i, "1", 10);

mpz_init_set_str(z_s, "1", 10);

mpz_init_set_str(z_o, "1", 10);

mpz_init_set_str的原型是:

 

int mpz_init_set_str (mpz_t rop, char *str, int base)

 

这三个参数分别是多精度整数变量,字符串,进制。

 

现在我们循环10000次并进行乘法和加法,乘法和加法的函数分别是mpz_mul,mpz_add,原型分别是:

 

void mpz_add (mpz_t rop, mpz t op1, mpz t op2)

效果为:rop = op1 + op2

 

void mpz_mul (mpz_t rop, mpz t op1, mpz t op2)

效果为:rop = op1 * op2

 

我们的程序可以写为:

 

int i;

for (i = 0; i < 10000; i++)

{

   mpz_mul(z_s, z_s, z_i);

   mpz_add(z_i, z_i, z_o);

}

然后我们按大整数的格式来输出结果,因为是mpz_t类型,不能用一般的printf,只能用gmp_printf:

 

gmp_printf("%Zd\n", z_s);

最后我们释放这几个大整数所占的空间:

 

mpz_clear(z_i);

mpz_clear(z_s);

mpz_clear(z_o);

 

 

 

程序就完毕了。运算结果非常大,显示了几页但是速度却非常快,几乎是一秒不到就做完了还包括了在控制台打印时间。

 

完整的程序如下:

 

 1 #include <gmp.h>

 2 #include <string.h>

 3 int main(int argc, const char *argv[])

 4 {

 5   mpz_t z_i, z_s, z_o;

 6   mpz_init_set_str(z_i, "1", 10);

 7   mpz_init_set_str(z_s, "1", 10);

 8   mpz_init_set_str(z_o, "1", 10);

 9   int i;

10   for (i = 0; i < 10000; i++)

11   {

12     mpz_mul(z_s, z_s, z_i);

13     mpz_add(z_i, z_i, z_o);

14   }

15   gmp_printf("%Zd\n", z_s);

16   mpz_clear(z_i);

17   mpz_clear(z_s);

18   mpz_clear(z_o);

19   getchar();

20   return 0;

21 }

 

GMP Basics

Gmp6.2.0文档

GMP库使用方法

使用GMP时,不要使用本文档未说明的函数、宏、数据类型,否则保证你的程序不与未来版本的GMP兼容。

 

 Headers and Libraries 

GMP库使用方法

使用GMP所需要的一切声明都汇集到了头文件gmp.h里,此头文件同时适用于C和C++。

 

GMP库使用方法

GMP中有些函数接受FILE*参数,只有当同时包含了stdio.h时,这些函数才是可用的。

类似的还有:stdarg.h对应可变参数函数(如gmp_vprintf()),obstack.h对应使用struct obstack参数的函数(gmp_obstack_prif())。

GMP库使用方法

 

编译的时候要链接gmp库gcc prog.c -lgmp。C++函数单独存放在另外的库gmpxx中g++ prog.cpp -lgmpxx -lgmp。

 

 

 

Nomenclature and Types

Nomenclature 命名法

GMP库使用方法

整数(integer)是指高精度整数(multiple precision integer),数据类型mpz_t。

GMP库使用方法

有理数(rational number)是指高精度分数(multiple precision fraction),类型mpq_t。

GMP库使用方法

浮点数(Floating point number,Float)由一个任意精度的尾数(mantissa)和一个极限精度的指数(limited precision exponent)构成。

GMP库使用方法

浮点数函数用mp_exp_t类型接受和返回指数,此类型一般是long,有些机器上是int(为了效率)。

高精度数中等于一个机器字长的部分称为一个limb(汉语意思为肢,四肢的肢)。类型为mp_limb_t。通常一个limb是32位或64位。

一个高精度数包含的limb的数目,用mp_size_t类型保存,此类型一般般是long,某些系统上是int,将来可能是long long。

一个高精度数有的位数用mp_bitcnt_t类型保存,当前此类型总是unsigned long,将来某些系统上可能会变成unsigned long long。

随机状态用类型gmp_randstate_t表示。(Random state means an algorithm selection and current state data.)。

mp_bitcnt_t用于位(bit)的计数以及表示范围;size_t用于给字节和字符计数。

GMP库使用方法

 

GMP库使用方法

 

 

 

 

 

 

 

GMP库使用方法

Analogy 比喻

GMP函数一般把输出参数放在输入参数之前,此约定是受赋值运算符的启发;兼容与BSD MP 的函数是例外:输出参数放在最后。

GMP库使用方法

在一次函数调用中可以把同一个变量同时用作输入输出参数。gmz_mul(x,x,x);此调用计算整数x的平方然后把计算结果再存入x中。

注意:一般自己写的函数不能这么干,要支持这样需要代码特地为此绕一下

GMP库使用方法

使用GMP变量之前,需要先初始化,使用完毕要释放变量。初始化和释放是通过专门的函数调用完成的。

一个变量只需要初始化一次,如果非要多次初始化,在每次初始化操作之间释放变量。初始化后的变量可以进行任意次赋值。

GMP库使用方法

 

一般在函数的开头初始化变量,函数末尾释放变量;为了效率,应避免过多的变量初始化和释放操作。

 

 

 

 

 

Parameter Conventions

GMP库使用方法

mpz_t实际上是长度为1的结构体数组,结构体内部的成员变量仅供库内部使用,如果在程序中访问了结构体成员,在新版GMP库中很可能不兼容。

Gmp中对变量的操作是使用指针,因此不要对变量进行copy!就算是用copy,也只读,不要修改,否则原来的变量也会被修改

GMP库使用方法

把变量作为函数参数传递时,实际上传递的是指针。

GMP库使用方法

    GMP库使用方法GMP库使用方法

gmp类型变量的本质是长度为1的结构体数组,变量的值存储在地址 _mp_d 对应的值中

 

如果自己编写的函数要返回结果,应该仿照GMP的库函数,使用输出参数(即函数的参数有部分参数用于输出值);如果直接使用return语句,返回的仅仅是个指针。

GMP库使用方法

GMP库使用方法

 

上面foo函数的输入参数param设置为const

 

 

Memory Management

GMP库使用方法

GMP自己会管理自己申请的内存。mpz_t和mpq_t在类型的变量需要时会申请更大的内存,但从不会减小内存,为了效率

GMP库使用方法

mpf_t类型的变量使用固定的内存,内存大小根据初始化时的精度设置确定。

GMP库使用方法

 

GMP默认使用malloc系列函数进行内存分配,但这是可设置的。

 

 

Reentrancy

GMP库使用方法

GMP是可重入的且是线程安全的,除了如下例外情况:

GMP库使用方法

编译时使用了--enable-alloca=malloc-notreentrant选项

 

函数mpf_set_default_prec()和mpf_init()使用全局变量保存精度

 

函数mpz_random()以及其它旧随机数生成函数使用全局变量保存随机状态,故是不可重入的。新的随机函数可用,这些函数使用gmp_randstate_t参数

 

gmp_randinit()(已过时)在全局变量中返回错误码,所以不可重入;使用新函数gmp_randinit_default()或gmp_randinit_lc_2exp()

GMP库使用方法

 

mp_set_memory_funcitons()使用全局变量保存内存分配函数

 

如果mp_set_memory_functions()设置的内存分配函数是不可重入的,那么GMP也将是不可重入的。默认的malloc()函数是不可冲入的

 

如果标准IO函数不可重入,则GMP的IO函数也不可重入

 

多个线程同时读一个GMP变量是安全的;但多线程一个读一个写、或多个同时写入都是不安全的;多线程使用同一个gmp_randstate_t变量生成随机数也是不安全的

 

 

 Useful Macros and Constants

GMP库使用方法

const int mp_bits_per_limb 一个limb的位数

GMP库使用方法

const char * const gmp_version x.y.z 格式的GMP版本;例如“6.2.1”

 

 

 

Integer Functions

GMP库使用方法

 Initialization Functions 

GMP库使用方法

GMP库使用方法

void mpz_init(mpz_t x) 初始化x并设其初值为0

void mpz_inits(mpz_t x, ...) 初始化参数列表中的变量,初值设为0. 最后一个参数用NULL,表示结束。

GMP库使用方法

void mpz_clear(mpz_t x), void mpz_clears(mpz_t x, ...) 释放变量

使用mpz_clears更方便!把多个变量一次clear 如mpz_clears(a,b,c,...,NULL);

 

Assignment Functions

 

GMP库使用方法

GMP库使用方法

对浮点数进行截断再赋值

GMP库使用方法

GMP库使用方法

GMP库使用方法

 

 

 

 Combined Initialization and Assignment Functions 

GMP库使用方法

初始化和赋值组合

 Don’t use an initialize-and-set function on a variable already initialized!

GMP库使用方法

GMP库使用方法

 

 

 

Conversion Functions 

GMP库使用方法

这些函数把GMP整数(mpz_t)转换成标准C语言类型。C类型转换到GMP整数,使用赋值函数和输出输出函数。

GMP库使用方法

这一类函数都有mpz_get_前缀,用si、ui、d、str对应signed long、unsigned long、double、char *str类型;返回值都是对应的结果类型。

 

转成整数、浮点数,如果超出了其表示范围,转换过来就没有意义了。可以用mpz_fit_ulong_p(mpz_t op)一族的函数判断一下,在取值范围内,则返回1,否则返回0.

GMP库使用方法

   GMP库使用方法GMP库使用方法

可以用这个方法来获取大整数的bit位!!!

使用NULL时需要手动释放内存,因为GMP默认使用malloc、realloc、free函数来操作动态内存,因此释放内存时使用free函数即可

 

 

 

 

Arithmetic Functions

加、减、乘、取相反数、取绝对值。返回值都是void。add\sub\mul\neg\abs

void mpz_add(mpz_t rop, mpz_t x, mpz_t y)  // x+y ⇒ rop

void mpz_sub(mpz_t rop, mpz_t x, mpz_t y)  // x-y ⇒ rop

void mpz_mul(mpz_t rop, mpz_t x, mpz_t y)  // x*y ⇒ rop

void mpz_neg(mpz_t rop, mpz_t op)    //  -op ⇒ rop

void mpz_abs(mpt_t rop, mpz_t op)    // |op| ⇒ rop

 

而且加减乘都有与signed long和unsigned long对应的变体

void mpz_add_ui(mpz_t rop, mpz_t x, unsigned long y)  // x+y ⇒ rop

void mpz_sub_ui(mpz_t rop, mpz_t x, unsigned long y)  // x-y ⇒ rop

void mpz_ui_sub(mpz_t rop, unsigned long x, mpz_t y)  // x-y ⇒ rop // 留意,减法有两个变体。

void mpz_mul_ui(mpz_t rop, mpz_t x, unsigned long y)  // x*y ⇒ rop

 

把ui换成si就是另外四个变体。

GMP库使用方法

 

 

 

 Division Functions (除法、模运算)

除法除不尽的时候要考虑舍入,GMP的整数除法运算有三种摄入模式:向上取整(ceil)、向下取整(floor)、向零取整(也叫截断,trunct),分别对应cidv,fdiv和tdiv。

GMP库使用方法

基本的除法函数,返回值都是void。

void mpz_cdiv_q(mpz_t q, mpz_t n, mpz_t d)

void mpz_cdiv_r(mpz_t r, mpz_t n, mpz_t d)

void mpz_cdiv_qr(mpz_t q, mpz_t r, mpz_t n, mpz_t d)

其中,n是被除数,d是除数(divisor),q是商(quote),r是余数(remainder)

q仅计算商,r仅计算余数,qr同时计算商和余数,qr函数中,q和r不能使用同一个变量,否则行为不定。

 

基本类型的变体有ui后缀(unsigned long)一种,ui指的是使用unsigned long作为除数。ui变体中 ,余数作为函数返回值返回,因为ui不能表示负数,所以返回的实际是余数的绝对值。

GMP库使用方法

 

fdiv和tdiv的除法函数与之类同。

  

GMP库使用方法

GMP库使用方法

GMP库使用方法

向上取整的除法,余数的符号和d相反;向下取整的符号,余数的符号和d相同;向零取整的除法,余数符号和被除数相同。

三种取整方式都满足n = d*q + r, |r| <= |d|。

GMP库使用方法

GMP库使用方法

GMP库使用方法

 

 

 

 

Exponentiation Functions

GMP库使用方法

Exp参数还支持负数(模逆存在时指数可为负数)

GMP库使用方法

 

 

 

 

Root Extraction Functions

Number Theoretic Functions

Comparison Functions

GMP库使用方法

op1 小于、等于、大于op2的时候分别返回小于零、等于零、大于零的数字。(没说-1,+1)。

而且si、ui、d三个变体实际是宏,所以会对操作数多次求值。

GMP库使用方法

 

比较两个操作数的绝对值得大小。

 

GMP库使用方法

 

 

 

 

 

 

 

 Logical and Bit Manipulation Functions 

  GMP库使用方法GMP库使用方法

普通的位运算,与或非(补)

GMP库使用方法

 

Op为正数时,返回二进制表示中1的个数

Op为负数时,

 

 

 

Formatted Output

GMP库使用方法

函数名,stdio里的格式化输入输出加 gmp_ 前缀就是了。gmp_printf    gmp_scanf

GMP库使用方法

 

 

GMP库使用方法

GMP库使用方法

    GMP库使用方法

GMP库使用方法GMP库使用方法

GMP库使用方法

Format string只翻译成单字节字符,多字节字符无法识别,未来可能会支持

 

 

 

 

 

 

Custom Allocation

GMP库使用方法

 

 

 

 

 

 

 

Internals

内部的实现原理

 Integer Internals

GMP库使用方法

GMP库使用方法

 

未赋值时为0,为负数时,表示在_mp_d对应的值前加个负号

GMP库使用方法

指向 limbs数组的指针,limbs数组的值为变量的绝对值大小,使用小端存储的方式

GMP库使用方法

Limbs数组的长度