第1页 / 共144页
第2页 / 共144页
第3页 / 共144页
第4页 / 共144页
第5页 / 共144页
第6页 / 共144页
第7页 / 共144页
第8页 / 共144页
GMP 入门手册 多精度 运算.pdf
GNU MP Copying Conditions
Introduction to GNU MP
How to use this Manual
Installing GMP
Build Options
ABI and ISA
Notes for Package Builds
Notes for Particular Systems
Known Build Problems
Performance optimization
GMP Basics
Headers and Libraries
Nomenclature and Types
Function Classes
Variable Conventions
Parameter Conventions
Memory Management
Reentrancy
Useful Macros and Constants
Compatibility with older versions
Demonstration programs
Efficiency
Debugging
Profiling
Autoconf
Emacs
Reporting Bugs
Integer Functions
Initialization Functions
Assignment Functions
Combined Initialization and Assignment Functions
Conversion Functions
Arithmetic Functions
Division Functions
Exponentiation Functions
Root Extraction Functions
Number Theoretic Functions
Comparison Functions
Logical and Bit Manipulation Functions
Input and Output Functions
Random Number Functions
Integer Import and Export
Miscellaneous Functions
Special Functions
Rational Number Functions
Initialization and Assignment Functions
Conversion Functions
Arithmetic Functions
Comparison Functions
Applying Integer Functions to Rationals
Input and Output Functions
Floating-point Functions
Initialization Functions
Assignment Functions
Combined Initialization and Assignment Functions
Conversion Functions
Arithmetic Functions
Comparison Functions
Input and Output Functions
Miscellaneous Functions
Low-level Functions
Nails
Random Number Functions
Random State Initialization
Random State Seeding
Random State Miscellaneous
Formatted Output
Format Strings
Functions
C++ Formatted Output
Formatted Input
Formatted Input Strings
Formatted Input Functions
C++ Formatted Input
C++ Class Interface
C++ Interface General
C++ Interface Integers
C++ Interface Rationals
C++ Interface Floats
C++ Interface Random Numbers
C++ Interface Limitations
Berkeley MP Compatible Functions
Custom Allocation
Language Bindings
Algorithms
Multiplication
Basecase Multiplication
Karatsuba Multiplication
Toom 3-Way Multiplication
Toom 4-Way Multiplication
FFT Multiplication
Other Multiplication
Unbalanced Multiplication
Division Algorithms
Single Limb Division
Basecase Division
Divide and Conquer Division
Block-Wise Barrett Division
Exact Division
Exact Remainder
Small Quotient Division
Greatest Common Divisor
Binary GCD
Lehmer's algorithm
Subquadratic GCD
Extended GCD
Jacobi Symbol
Powering Algorithms
Normal Powering
Modular Powering
Root Extraction Algorithms
Square Root
Nth Root
Perfect Square
Perfect Power
Radix Conversion
Binary to Radix
Radix to Binary
Other Algorithms
Prime Testing
Factorial
Binomial Coefficients
Fibonacci Numbers
Lucas Numbers
Random Numbers
Assembly Coding
Code Organisation
Assembly Basics
Carry Propagation
Cache Handling
Functional Units
Floating Point
SIMD Instructions
Software Pipelining
Loop Unrolling
Writing Guide
Internals
Integer Internals
Rational Internals
Float Internals
Raw Output Internals
C++ Interface Internals
Contributors
References
Books
Papers
GNU Free Documentation License
Concept Index
Function and Type Index
GNU MP
The GNU Multiple Precision Arithmetic Library
Edition 5.0.1
6 February 2010
by Torbj¨orn Granlund and the GMP development team
This manual describes how to install and use the GNU multiple precision arithmetic library,
version 5.0.1.
Copyright 1991, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
Permission is granted to copy, distribute and/or modify this document under the terms of
the GNU Free Documentation License, Version 1.3 or any later version published by the Free
Software Foundation; with no Invariant Sections, with the Front-Cover Texts being “A GNU
Manual”, and with the Back-Cover Texts being “You have freedom to copy and modify this
GNU Manual, like GNU software”. A copy of the license is included in Appendix C [GNU Free
Documentation License], page 124.
i
Table of Contents
GNU MP Copying Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1
2
Introduction to GNU MP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1 How to use this Manual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Installing GMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Build Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 ABI and ISA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Notes for Package Builds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Notes for Particular Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5 Known Build Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.6 Performance optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 GMP Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1 Headers and Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Nomenclature and Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3 Function Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.4 Variable Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.5 Parameter Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.6 Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.7 Reentrancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.8 Useful Macros and Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.9 Compatibility with older versions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.10 Demonstration programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.11 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.12 Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.13 Profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.14 Autoconf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.15 Emacs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4 Reporting Bugs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5
Integer Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.1
Initialization Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 Assignment Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.3 Combined Initialization and Assignment Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.4 Conversion Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.5 Arithmetic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.6 Division Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.7 Exponentiation Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.8 Root Extraction Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.9 Number Theoretic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.10 Comparison Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.11 Logical and Bit Manipulation Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.12
Input and Output Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.13 Random Number Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
ii
GNU MP 5.0.1
Integer Import and Export . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.14
5.15 Miscellaneous Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.16 Special Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6 Rational Number Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
6.1
Initialization and Assignment Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
6.2 Conversion Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.3 Arithmetic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.4 Comparison Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.5 Applying Integer Functions to Rationals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.6
Input and Output Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
7 Floating-point Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
7.1
Initialization Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
7.2 Assignment Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
7.3 Combined Initialization and Assignment Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.4 Conversion Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.5 Arithmetic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
7.6 Comparison Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
7.7
Input and Output Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
7.8 Miscellaneous Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
8 Low-level Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
8.1 Nails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
9 Random Number Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
9.1 Random State Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
9.2 Random State Seeding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
9.3 Random State Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
10 Formatted Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
10.1 Format Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
10.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
10.3 C++ Formatted Output. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
11 Formatted Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
11.1 Formatted Input Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
11.2 Formatted Input Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
11.3 C++ Formatted Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
12 C++ Class Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
12.1 C++ Interface General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
12.2 C++ Interface Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
12.3 C++ Interface Rationals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
12.4 C++ Interface Floats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
12.5 C++ Interface Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
12.6 C++ Interface Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
13 Berkeley MP Compatible Functions . . . . . . . . . . . . . . . . . . . . . . . 84
iii
14 Custom Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
15 Language Bindings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
16 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
16.1 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
16.1.1 Basecase Multiplication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
16.1.2 Karatsuba Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
16.1.3 Toom 3-Way Multiplication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
16.1.4 Toom 4-Way Multiplication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
16.1.5 FFT Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
16.1.6 Other Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
16.1.7 Unbalanced Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
16.2 Division Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
16.2.1 Single Limb Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
16.2.2 Basecase Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
16.2.3 Divide and Conquer Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
16.2.4 Block-Wise Barrett Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
16.2.5 Exact Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
16.2.6 Exact Remainder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
16.2.7 Small Quotient Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
16.3 Greatest Common Divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
16.3.1 Binary GCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
16.3.2 Lehmer’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
16.3.3 Subquadratic GCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
16.3.4 Extended GCD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
16.3.5 Jacobi Symbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
16.4 Powering Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
16.4.1 Normal Powering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
16.4.2 Modular Powering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
16.5 Root Extraction Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
16.5.1 Square Root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
16.5.2 Nth Root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
16.5.3 Perfect Square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
16.5.4 Perfect Power . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
16.6 Radix Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
16.6.1 Binary to Radix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
16.6.2 Radix to Binary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
16.7 Other Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
16.7.1 Prime Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
16.7.2 Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
16.7.3 Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
16.7.4 Fibonacci Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
16.7.5 Lucas Numbers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
16.7.6 Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
16.8 Assembly Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
16.8.1 Code Organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
16.8.2 Assembly Basics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
16.8.3 Carry Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
16.8.4 Cache Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
16.8.5 Functional Units . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
16.8.6 Floating Point. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
16.8.7 SIMD Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
iv
GNU MP 5.0.1
16.8.8 Software Pipelining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
16.8.9 Loop Unrolling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
16.8.10 Writing Guide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
17
Internals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
17.1
Integer Internals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
17.2 Rational Internals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
17.3 Float Internals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
17.4 Raw Output Internals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
17.5 C++ Interface Internals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Appendix A Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Appendix B References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
B.1 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
B.2 Papers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Appendix C GNU Free Documentation License . . . . . . . . . . . 124
Concept Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
Function and Type Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
GNU MP Copying Conditions
1
GNU MP Copying Conditions
This library is free; this means that everyone is free to use it and free to redistribute it on a free
basis. The library is not in the public domain; it is copyrighted and there are restrictions on its
distribution, but these restrictions are designed to permit everything that a good cooperating
citizen would want to do. What is not allowed is to try to prevent others from further sharing
any version of this library that they might get from you.
Specifically, we want to make sure that you have the right to give away copies of the library,
that you receive source code or else can get it if you want it, that you can change this library
or use pieces of it in new free programs, and that you know you can do these things.
To make sure that everyone has such rights, we have to forbid you to deprive anyone else of
these rights. For example, if you distribute copies of the GNU MP library, you must give the
recipients all the rights that you have. You must make sure that they, too, receive or can get
the source code. And you must tell them their rights.
Also, for our own protection, we must make certain that everyone finds out that there is no
warranty for the GNU MP library. If it is modified by someone else and passed on, we want
their recipients to know that what they have is not what we distributed, so that any problems
introduced by others will not reflect on our reputation.
The precise conditions of the license for the GNU MP library are found in the Lesser General
Public License version 3 that accompanies the source code, see ‘COPYING.LIB’. Certain demon-
stration programs are provided under the terms of the plain General Public License version 3,
see ‘COPYING’.
2
GNU MP 5.0.1
1 Introduction to GNU MP
GNU MP is a portable library written in C for arbitrary precision arithmetic on integers, rational
numbers, and floating-point numbers. It aims to provide the fastest possible arithmetic for all
applications that need higher precision than is directly supported by the basic C types.
Many applications use just a few hundred bits of precision; but some applications may need
thousands or even millions of bits. GMP is designed to give good performance for both, by
choosing algorithms based on the sizes of the operands, and by carefully keeping the overhead
at a minimum.
The speed of GMP is achieved by using fullwords as the basic arithmetic type, by using sophis-
ticated algorithms, by including carefully optimized assembly code for the most common inner
loops for many different CPUs, and by a general emphasis on speed (as opposed to simplicity
or elegance).
There is assembly code for these CPUs: ARM, DEC Alpha 21064, 21164, and 21264, AMD
29000, AMD K6, K6-2, Athlon, and Athlon64, Hitachi SuperH and SH-2, HPPA 1.0, 1.1 and
2.0, Intel Pentium, Pentium Pro/II/III, Pentium 4, generic x86, Intel IA-64, i960, Motorola
MC68000, MC68020, MC88100, and MC88110, Motorola/IBM PowerPC 32 and 64, National
NS32000, IBM POWER, MIPS R3000, R4000, SPARCv7, SuperSPARC, generic SPARCv8,
UltraSPARC, DEC VAX, and Zilog Z8000. Some optimizations also for Cray vector systems,
Clipper, IBM ROMP (RT), and Pyramid AP/XP.
For up-to-date information on GMP, please see the GMP web pages at
http://gmplib.org/
The latest version of the library is available at
ftp://ftp.gnu.org/gnu/gmp/
Many sites around the world mirror ‘ftp.gnu.org’, please use a mirror near you, see
http://www.gnu.org/order/ftp.html for a full list.
There are three public mailing lists of interest. One for release announcements, one for general
questions and discussions about usage of the GMP library and one for bug reports. For more
information, see
http://gmplib.org/mailman/listinfo/.
The proper place for bug reports is gmp-bugs@gmplib.org. See Chapter 4 [Reporting Bugs],
page 28 for information about reporting bugs.
1.1 How to use this Manual
Everyone should read Chapter 3 [GMP Basics], page 16.
If you need to install the library
yourself, then read Chapter 2 [Installing GMP], page 3.
If you have a system with multiple
ABIs, then read Section 2.2 [ABI and ISA], page 8, for the compiler options that must be used
on applications.
The rest of the manual can be used for later reference, although it is probably a good idea to
glance through it.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
