logo资料库

GMP大数运算库中文使用教程.pdf

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：0.41M 资料格式：pdf 举报 版权申诉
第1页 / 共58页
第2页 / 共58页
第3页 / 共58页
第4页 / 共58页
第5页 / 共58页
第6页 / 共58页
第7页 / 共58页
第8页 / 共58页
资料共58页，剩余部分请下载后查看
    目目目录录录 1 GMP 及及及其其其安安安装装装 1.1 介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 GMP 在 UNIX 类系统下的安装 . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 GMP 在 Windows 系统下的安装 . . . . . . . . . . . . . . . . . . . . . . . . 2 GMP 基基基础础础 2.1 头文件与库文件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 术语与类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 函数类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 变量约定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 参数约定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 内存管理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 重入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 有用的宏和常量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 与其它版本的兼容 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 示例程序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.11 效率 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.12 其他编译链接相关内容 (略) . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 整整整数数数函函函数数数 3.1 初始化函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 赋值函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 初始化赋值组合函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 转换函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 算术函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 除法函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 指数函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 求根开方函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 数论函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 比较函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.11 逻辑和位操作函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12 输入输出函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.13 随机数函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.14 整数引入和导出 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.15 杂类函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 有有有理理理数数数函函函数数数 4.1 初始化和赋值函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 转换函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 算术运算函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 比较函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 2 4 4 4 5 5 6 6 7 7 7 8 8 10 11 11 12 13 13 14 15 16 17 17 19 19 20 21 22 23 24 24 25 25 26 I
    II 4.5 应用整数函数于有理数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 输入输出函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 浮浮浮点点点函函函数数数 5.1 初始化函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 赋值函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 初始化赋值组合函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 转换函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 算术函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 比较函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7 输入输出函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.8 杂类函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 低低低级级级函函函数数数 6.1 Nails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 随随随机机机数数数函函函数数数 7.1 随机状态初始化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 随机状态种子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 格格格式式式输输输出出出 8.1 格式字符串 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 格格格式式式输输输入入入 9.1 格式输入字符串 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 格式输入函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 用用用户户户内内内存存存分分分配配配 11 内内内部部部结结结构构构 11.1 整数内部结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 有理数内部结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3 浮点数内部结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.4 Raw 输出内部结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 参参参考考考文文文献献献 目录 26 26 28 28 29 30 31 31 32 33 33 35 40 42 42 43 44 44 46 47 47 49 50 52 52 52 53 54 55
    序序序言言言 本翻译稿只为方便大家查阅手册使用，最好对照原英文手册阅读。稿中难免有很多 不准确之处，应以英文为准，见仁见智。 只对手册作了部分翻译，陈旧的、高深的以及 C++ 相关的内容没有翻译，读者自己 把握。 译者 2005 年 6 月 30 日 III
    第第第 一一一 章章章 GMP 及及及其其其安安安装装装 1.1 介介介绍绍绍 GNU MP 是用 C 语言写成的一个便携式库，它可以进行整数、有理数和浮点数的任 意精度算术，其目标是为所有需要不能由基本 C 类型直接支持的多精度类型的应用提供 可能最快的算术。 许多应用只需要几百 bit 的精度，但是有些应用需要上千甚至上百万 bit 精度。通过 根据操作数的规模选择算法，通过仔细的保持开销最小化，GMP 被设计成为各种应用提 供最好的性能。 通过把整个字作为基本算术类型，通过使用精益求精的算法，通过为大部分的内部 循环针对不同 CPU 包含认真优化的汇编代码，通过对速度 (与简洁性和优雅性不同) 的强 调，GMP 实现了较快的速度。 如果希望获得关于 GMP 的最新消息，可以访问 http : //swox.com/gmp/ 可以从该网站上获得 GMP 的最新源码和安装包 gmp-4.1.4.tar.bz2，或者从 GNU 官方 ftp 网址 ftp : //ftp.gnu.org/gnu/gmp 上获得，当然使用离你最近的镜像站点是最好的选择。本文针对 GMP 的 4.1.4 版，主要 参考 gmp-4.1.4 用户手册。 1.2 GMP 在在在 UNIX 类类类系系系统统统下下下的的的安安安装装装 GMP 有一个基于 autoconf/automake/libtool 的配置系统，在 UNIX 类系统环境下基 本编译可以通过 来完成，这时 autoconf 使用默认配置选项。自测试通过 ./configure make 完成，你可以通过 make check make install 来安装 GMP(默认安装在’/usr/local/’ 目录下)。GMP 的安装配置选项是可以被修改的， 假设 gmp-4.1.4.tar.bz2 解压缩于 ∼/gmp-4.1.4/，进入该目录键入 ./configure --help 可以看到 GMP 的所有安装配置选项信息，下面对其中重要的几个作一些简单介绍。 “--prefix”和“--exec-prefix” 1
    2 第 一 章 GMP 及其安装 “--prefix”指定 GMP 安装目录，在 &prefix 下建立安装目录树，主要是 将 库 文 件 libgmp.a 等 安 装 在 &prefix/lib/ 下 ， 而 将 头 文 件 gmp.h 等 安 装 在 &prefix/include/ 下，默认选项是‘--prefix=/usr/local/’。如果希望 将库文件安装在不同的目录下，可以设置“--exec-prefix”，这时需要保证头 文件在 &prefix/include/ 以及库文件在 &exec-prefix/lib/ 都是可编译链接 的。 “--disable-shared”和“--disable-static” 在默认情形下动态和静态链接库会同时建立 (如果可能)，但是可以其中之一可 以不建立。动态链接库可以实现更小的可执行文件体积并允许在不同的处理器 之间共享代码，但是在有些 CPU 上动态链接库可能有一些慢因为需要额外的函 数调用开销。 “--enable-cxx” GMP 的 C++ 支持可以通过‘--enable-cxx’来实现，这时需要一个 C++ 编 译器。C++ 支持有库文件 libgmpxx.a 和头文件 gmpxx.h 组成，在 GMP 中采 用了分离的库文件 libgmpxx.a 而不是在库文件 libgmp.a 中包含 C++ 对象，这 是为了保证动态链接 C 程序时不会因为要依赖 C++ 标准库而变得庞大，并且 避免链接普通 C 程序时需要使用 C++ 编译器。libgmpxx.a 依赖于 libgmp.a， 不同版本的 libgmp.a 是不能支持 libgmpxx.a 的，而且，libgmpxx.a 只能配合编 译它的 C++ 编译器使用，因为在不同的编译器中名字处理和运行时库通常是不 兼容的。 “--enable-mpbsd” 只有当‘--enable-mpbsd’被使用时，用于 Berkley MP 函数兼容的库文件 libmp.a 和头文件 mp.h 被建立和安装。 “--enable-mpfr” MPFR 包含很多快速的浮点运算函数，现在也被集成在 GMP 的安装包中，只 有当‘--enable-mpfr’被使用时，可选的 MPFR 函数库文件 libmpfr.a 和头文 件 mpfr.h,mpf2mpfr.h,mpfrxx.h 被建立和安装。 GMP 安装还有其他很多配置选项，这里就不做介绍了，实际上 autoconf 会自动收 集 CPU, 编译器等信息，所以这些不需要我们手动设置。下面是一个推荐配置: ./configure --enable-mpbsd --enable-mpfr --enable-cxx --disable-shared 1.3 GMP 在在在 Windows 系系系统统统下下下的的的安安安装装装 GMP 包是在 UNIX 类系统上开发出来的，不幸的是 UNIX 类系统操作的不直观性使 得很多人对它望而却步，而宁愿选择需要花钱的 Windows 操作系统。为了在 Windows 操 作系统上使用 GMP 包，我们需要在 Windows 操作系统上模拟 UNIX 环境，有很多方法 来实现它，其中 MinGW 和 Cygwin 是两个不错的选择。MinGW 直接应用 Windows 系统 的 C 运行时库 msvcrt.dll 进行 I/O 处理，配合 MinSys，MinGW 可以在 Windows 操作系 统上模拟简单的 UNIX 环境，它也可以配合 Cygwin 使用。Cygwin 定义了自己的动态链 接库 cygwin1.dll，在 Cygwin 内部实现的应用一般都要通过这个动态链接库来运行，但是 如果选用 MinGW 作为内部的编译环境，Cygwin 像 MinGW 那样实现应用。Cygwin 是 一个比较完备的环境，它提供许多 UNIX 应用程序，使用它时你会感觉像在真正的 UNIX 类操作系统上工作一样。可以从网址 http : //www.mingw.org/ http : //www.cygwin.com/
    §1.3 GMP 在 WINDOWS 系统下的安装 3 分别得到 MinGW 和 Cygwin 的有关信息和安装方法。 MinGW 和 MinSys 的二进制安装包可以直接从其官方网站上获得，在得到了它们 的二进制安装包后，应该首先安装 MinGW 再安装 MinSys，一般将 MinGW 安装于目录 为 C:/MinSys/MinGW/，而 MinSys 安装于目录 C:/MinSys/，这样将 MinSys 文件夹拷 贝到其他运行 Windows 的机器 C 盘根目录下，不需要任何其他的设置，MinSys 仍然是 可以直接使用的。当然也可以选择任意的其他安装目录，在 MinSys 安装的最后会提示输 入 MinGW 的安装目录。 下载 Cygwin 安装包一般需要先从其官方网站上获得 setup.exe 程序，运行 setup.exe， 它会要求你选择下载到本地文件夹还是在线安装或者从本地文件夹安装，选定下载到本地 文件夹后，它会提示网络连接方式，接下来就是选择镜像网站了，注意不要同时选择两个 网址，你也可以输入列表中没有的镜像网站，国内有很多大学和机构都作了 Cygwin 的镜 像，例如 ftp : //ftp.ctex.org/pub/cygwin/ ftp : //ftp.tsinghua.edu/pub/cygwin/ 在顺利登陆镜像站点之后，会有一个应用程序树供你选择，除了默认的应用程序之 外，GCC,vi,libtool 等也是必须的，如果网速和空间允许的话建议完全下载，但是安装的 时候没有必要完全安装，那样需要约 1G 的空间，一般根据自己需要选择应用程序。如 果想省去编译 GMP 的麻烦，甚至可以在这些应用程序中找到 GMP，但是由于机器的不 同，直接安装的 GMP 可能不如在本机编译安装的 GMP 速度快。 有了 MinGW+MinSys 或者 Cygwin 之后，可以像上一节那样编译安装 GMP，但是 默认情形下只建立静态库，如果希望建立动态库 DLL，需要使用 ‘--disable-static --enable-shared’ 选项，注意静态库和动态库是不能同时建立的。在建立 DLL 时‘--enable-cxx’是不可 用的，因为目前 libtool 还不支持 C++ DLL。 习惯了 VC 的高手可能希望将 GMP 用于 VC 编程，这似乎不是很好办到，有两种方 法也许可以，首先是使用源码，GMP 的源码就在压缩包 gmp-4.1.4.tar.bz2 中，具体怎么 用 VC 高手也许有办法。其次我们可以用 MinGW 编译 GMP 建立动态库 libgmp.dll，但 是它不会产生.lib 和.exp 文件，这需要通过下面的命令得到: lib /machine:IX86 /def:.libs/libgmp-3.dll-def cp libgmp-3.lib /my/inst/dir/lib cp .libs/libgmp-3.dll-exp /my/inst/dir/lib/libgmp-3.exp 其中/my/inst/dir 是.lib 和.exp 文件安装目录。正如前面所说，MinGW 依赖于 C 运行时 库 msvcrt.dll 处理 I/O，因此在使用 libgmp.dll 进行 VC 编程时需要用“cl /MD”进行编 译。
    第第第 二二二 章章章 GMP 基基基础础础 2.1 头头头文文文件件件与与与库库库文文文件件件 应用 GMP 所需的所有声明都集中在头文件‘gmp.h’中，它被设计为对 C 和 C++ 编译器都可用。 #include 但是需要注意的是只有同时包含了头文件‘stdio.h’，原型包括 FILE* 参数的所有 GMP 函数才可用。 #include #include 类似地，对原型包含 va_list 参数的函数如 gmp_vprintf，头文件 (或者 ) 是必须的；而对原型包含 struct obstack 参数的函数，头文件 也是必须的，例如当 gmp_obstack_printf 可用时。 所有使用 GMP 的程序都必须与“libgmp”库链接，在典型的 UNIX 类系统中，这 通常用参数‘-lgmp’来完成，例如 gcc myprogram.c -lgmp GMP C++ 函数存在于另外的库“libgmpxx”中，这个库在 C++ 支持开启时会建立 (参 见上一章)。 g++ mycxxprog.cc -lgmpxx -lgmp 如果 GMP 不是安装在标准位置，你需要用‘-I’和‘-L’参数来指定头文件和库文件目 录，例如 gcc myprogram.c -I/myincldir/gmp.h -L/mylibdir/libgmp.a 2.2 术术术语语语与与与类类类型型型 在 GMP 库的定义中，整数通常指多精度整数，它的 C 数据类型表示为 mpz_t，下 面的例子显示怎样声明这样的整数： mpz_t sum; struct foo { mpz_t x, y; }; mpz_t vec[20]; 有理数指的是多精度的分数，它的 C 类型表示为 mpq_t，例如， mpq_t quotient; 浮点数或者简称实数，实际上是任意精度的有限定精度指数小数部分的数，这种对象的 C 类型表示为 mpf_t。 limb 指的是刚好能在机器字范围内的多精度数的一部分 (选择 limb 这个词是因为人 体的一部分类似于一位，也许更多，包含几位)。通常一个 limb 表示 32 或 64bit，它的 C 类型表示为 mp_limb_t。 4
    §2.3 函数类 2.3 函函函数数数类类类 GMP 库中有六类函数： 5 1. 名字以 mpz_ 开头的有符号整数算术函数，相关的数据类型是 mpz_t，这一类中有大 约 150 个函数。 2. 名字以 mpq_ 开头的有理数算术函数，相关的数据类型是 mpq_t，这一类中有大约 40 个函数，但是整数函数可以分别应用于对分子和分母的算术。 3. 名字以 mpf_ 开头的有符号整数算术函数，相关的数据类型是 mpf_t，这一类中有大 约 60 个函数。 4. 与 Berkeley MP 相兼容的函数，例如 itom、madd 和 mult，相关的数据类型是 MINT。 5. 作用于自然数的快速低级函数，它们被用于前述的各类函数，对于时间要求极 高的用户编程，也可以直接调用它们。这些函数以 mpn_ 开头，相关的数据类型 是 mp_limb_t，这一类中有大约 30 个函数 (用起来有难度)。 6. 杂类函数，包括建立用户内存分配的函数和生成随机数的函数。 2.4 变变变量量量约约约定定定 GMP 函数一般先写输出变量后写输入变量，这个概念类似于赋值运算符。BSD MP 兼容函数是特例，它们都是后写输出的。 GMP 允许我们在一次调用中使用相同的输入和输出变量，例如作整数乘法的主函 数 mpz_mul，可以计算 x 的平方，然后把输出放回到 x 中， mpz_mul (x, x, x); 在对一个 GMP 变量赋值之前，需要通过调用一个特定的初始化函数对它进行初始化，当 用完了一个 GMP 变量时，需要把它清除掉，你要调用一个实现这个目的的特定函数，具 体用哪一个函数依赖于变量的类型，细节见于关于整数函数、有理数函数和实数函数的章 节。 一个变量只能初始化一次，或者在下一次初始化之前对它进行清除。当一个变量初 始化了以后，它可以被赋值任意多的次数。 为了实现更高的效率，应该尽量减少初始化和清除。通常在函数开始时进行初始化 而在其结束时进行清除： void foo (void) { mpz_t n; int i; mpz_init (n); for (i = 1; i < 100; i++) { mpz_mul (n, ...); mpz_fdiv_q (n, ...); ... } mpz_clear (n); }
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料