Copyright 1991, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002 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.1 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 GNU Free Documentation License.
printf style output.
scanf style input.
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 2.1 that accompanies the source code,
see COPYING.LIB. Certain demonstration programs are provided under the
terms of the plain General Public License version 2, see COPYING.
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 sophisticated 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 carefully optimized assembly code for these CPUs: ARM, DEC Alpha 21064, 21164, and 21264, AMD 29000, AMD K6, K6-2 and Athlon, 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.
There is a mailing list for GMP users. To join it, send a mail to
gmp-request@swox.com with the word subscribe in the message
body (not in the subject line).
For up-to-date information on GMP, please see the GMP web pages at
http://swox.com/gmp/
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.
Everyone should read GMP Basics. If you need to install the library yourself, then read Installing GMP. If you have a system with multiple ABIs, then read ABI and ISA, 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.
GMP has an autoconf/automake/libtool based configuration system. On a
Unix-like system a basic build can be done with
./configure make
Some self-tests can be run with
make check
And you can install (under /usr/local by default) with
make install
If you experience problems, please report them to bug-gmp@gnu.org. See Reporting Bugs, for information on what to include in useful bug reports.
All the usual autoconf configure options are available, run ./configure
--help for a summary. The file INSTALL.autoconf has some generic
installation information too.
configure requires various Unix-like tools. On an MS-DOS system DJGPP
can be used, and on MS Windows Cygwin or MINGW can be used,
http://www.cygnus.com/cygwin http://www.delorie.com/djgpp http://www.mingw.org
The macos directory contains an unsupported port to MacOS 9 on Power
Macintosh, see macos/README. Note that MacOS X "Darwin" should use
the normal Unix-style ./configure.
It might be possible to build without the help of configure, certainly
all the code is there, but unfortunately you'll be on your own.
cd to that directory, and
prefix the configure command with the path to the GMP source directory. For
example
cd /my/build/dir /my/sources/gmp-4.1/configure
Not all make programs have the necessary features (VPATH) to
support this. In particular, SunOS and Slowaris make have bugs that
make them unable to build in a separate directory. Use GNU make
instead.
--disable-shared, --disable-static
--build=CPU-VENDOR-OS
--build. By default ./configure uses the output from running
./config.guess. On some systems ./config.guess can determine
the exact CPU type, on others it will be necessary to give it explicitly. For
example,
./configure --build=ultrasparc-sun-solaris2.7
In all cases the OS part is important, since it controls how libtool
generates shared libraries. Running ./config.guess is the simplest way
to see what it should be, if you don't know already.
--host=CPU-VENDOR-OS
--build
and the system where the library will run is given by --host. For
example when using a FreeBSD Athlon system to build GNU/Linux m68k binaries,
./configure --build=athlon-pc-freebsd3.5 --host=m68k-mac-linux-gnu
Compiler tools are sought first with the host system type as a prefix. For
example m68k-mac-linux-gnu-ranlib is tried, then plain
ranlib. This makes it possible for a set of cross-compiling tools
to co-exist with native tools. The prefix is the argument to --host,
and this can be an alias, such as m68k-linux. But note that tools
don't have to be setup this way, it's enough to just have a PATH with a
suitable cross-compiling cc etc.
Compiling for a different CPU in the same family as the build system is a form
of cross-compilation, though very possibly this would merely be special
options on a native compiler. In any case ./configure avoids depending
on being able to run code on the build system, which is important when
creating binaries for a newer CPU since they very possibly won't run on the
build system.
In all cases the compiler must be able to produce an executable (of whatever
format) from a standard C main. Although only object files will go to
make up libgmp, ./configure uses linking tests for various
purposes, such as determining what functions are available on the host system.
Currently a warning is given unless an explicit --build is used when
cross-compiling, because it may not be possible to correctly guess the build
system type if the PATH has only a cross-compiling cc.
Note that the --target option is not appropriate for GMP. It's for use
when building compiler tools, with --host being where they will run,
and --target what they'll produce code for. Ordinary programs or
libraries like GMP are only interested in the --host part, being where
they'll run. (Some past versions of GMP used --target incorrectly.)
The following CPUs have specific support. See configure.in for details
of what code and compiler options they select.
alpha,
alphaev5,
alphaev56,
alphapca56,
alphapca57,
alphaev6,
alphaev67,
alphaev68
c90,
j90,
t90,
sv1
hppa1.0,
hppa1.1,
hppa2.0,
hppa2.0n,
hppa2.0w
mips,
mips3,
mips64
m68k,
m68000,
m68010,
m68020,
m68030,
m68040,
m68060,
m68302,
m68360,
m88k,
m88110
power,
power1,
power2,
power2sc
powerpc,
powerpc64,
powerpc401,
powerpc403,
powerpc405,
powerpc505,
powerpc601,
powerpc602,
powerpc603,
powerpc603e,
powerpc604,
powerpc604e,
powerpc620,
powerpc630,
powerpc740,
powerpc7400,
powerpc7450,
powerpc750,
powerpc801,
powerpc821,
powerpc823,
powerpc860,
sparc,
sparcv8,
microsparc,
supersparc,
sparcv9,
ultrasparc,
ultrasparc2,
ultrasparc2i,
ultrasparc3,
sparc64
i386,
i486,
i586,
pentium,
pentiummmx,
pentiumpro,
pentium2,
pentium3,
pentium4,
k6,
k62,
k63,
athlon
a29k,
arm,
clipper,
i960,
ns32k,
pyramid,
sh,
sh2,
vax,
z8k
CPUs not listed will use generic C code.
none. For example,
./configure --host=none-unknown-freebsd3.5
Note that this will run quite slowly, but it should be portable and should at
least make it possible to get something running if all else fails.
ABI
./configure --host=mips64-sgi-irix6 ABI=n32
See ABI and ISA, for the available choices on relevant CPUs, and what
applications need to do.
CC, CFLAGS
gcc normally preferred if it's present. The usual
CC=whatever can be passed to ./configure to choose something
different.
For some systems, default compiler flags are set based on the CPU and
compiler. The usual CFLAGS="-whatever" can be passed to
./configure to use something different or to set good flags for systems
GMP doesn't otherwise know.
The CC and CFLAGS used are printed during ./configure,
and can be found in each generated Makefile. This is the easiest way
to check the defaults when considering changing or adding something.
Note that when CC and CFLAGS are specified on a system
supporting multiple ABIs it's important to give an explicit
ABI=whatever, since GMP can't determine the ABI just from the flags and
won't be able to select the correct assembler code.
If just CC is selected then normal default CFLAGS for that
compiler will be used (if GMP recognises it). For example CC=gcc can
be used to force the use of GCC, with default flags (and default ABI).
CPPFLAGS
-D defines or -I includes required by the
preprocessor should be set in CPPFLAGS rather than CFLAGS.
Compiling is done with both CPPFLAGS and CFLAGS, but
preprocessing uses just CPPFLAGS. This distinction is because most
preprocessors won't accept all the flags the compiler does. Preprocessing is
done separately in some configure tests, and in the ansi2knr support
for K&R compilers.
--enable-cxx
--enable-cxx, in which case a
C++ compiler will be required. As a convenience --enable-cxx=detect
can be used to enable C++ support only if a compiler can be found. The C++
support consists of a library libgmpxx.la and header file
gmpxx.h.
A separate libgmpxx.la has been adopted rather than having C++ objects
within libgmp.la in order to ensure dynamic linked C programs aren't
bloated by a dependency on the C++ standard library, and to avoid any chance
that the C++ compiler could be required when linking plain C programs.
libgmpxx.la will use certain internals from libgmp.la and can
only be expected to work with libgmp.la from the same GMP version.
Future changes to the relevant internals will be accompanied by renaming, so a
mismatch will cause unresolved symbols rather than perhaps mysterious
misbehaviour.
In general libgmpxx.la will be usable only with the C++ compiler that
built it, since name mangling and runtime support are usually incompatible
between different compilers.
CXX, CXXFLAGS
CXX and CXXFLAGS in the usual way. The default for
CXX is the first compiler that works from a list of likely candidates,
with g++ normally preferred when available. The default for
CXXFLAGS is to try CFLAGS, CFLAGS without -g, then
for g++ either -g -O2 or -O2, or for other compilers
-g or nothing. Trying CFLAGS this way is convenient when using
gcc and g++ together, since the flags for gcc will
usually suit g++.
It's important that the C and C++ compilers match, meaning their startup and
runtime support routines are compatible and that they generate code in the
same ABI (if there's a choice of ABIs on the system). ./configure
isn't currently able to check these things very well itself, so for that
reason --disable-cxx is the default, to avoid a build failure due to a
compiler mismatch. Perhaps this will change in the future.
Incidentally, it's normally not good enough to set CXX to the same as
CC. Although gcc for instance recognises foo.cc as
C++ code, only g++ will invoke the linker the right way when
building an executable or shared library from object files.
--enable-alloca=<choice>
GMP allocates temporary workspace using one of the following three methods,
which can be selected with for instance
--enable-alloca=malloc-reentrant.
alloca - C library or compiler builtin.
malloc-reentrant - the heap, in a re-entrant fashion.
malloc-notreentrant - the heap, with global variables.
For convenience, the following choices are also available.
--disable-alloca is the same as --enable-alloca=no.
yes - a synonym for alloca.
no - a synonym for malloc-reentrant.
reentrant - alloca if available, otherwise
malloc-reentrant. This is the default.
notreentrant - alloca if available, otherwise
malloc-notreentrant.
alloca is reentrant and fast, and is recommended, but when working with
large numbers it can overflow the available stack space, in which case one of
the two malloc methods will need to be used. Alternately it might be possible
to increase available stack with limit, ulimit or
setrlimit, or under DJGPP with stubedit or
_stklen. Note that depending on the system the only indication of
stack overflow might be a segmentation violation.
malloc-reentrant is, as the name suggests, reentrant and thread safe,
but malloc-notreentrant is faster and should be used if reentrancy is
not required.
The two malloc methods in fact use the memory allocation functions selected by
mp_set_memory_functions, these being malloc and friends by
default. See Custom Allocation.
An additional choice --enable-alloca=debug is available, to help when
debugging memory related problems (see Debugging).
--disable-fft
--enable-mpbsd
libmp) and header file
(mp.h) are built and installed only if --enable-mpbsd is used.
See BSD Compatible Functions.
--enable-mpfr
The optional MPFR functions are built and installed only if
--enable-mpfr is used. These are in a separate library
libmpfr.a and are documented separately too (see Introduction to MPFR).
--enable-assert
--enable-profiling=prof/gprof
prof or gprof.
This adds -p or -pg respectively to CFLAGS, and for some
systems adds corresponding mcount calls to the assembler code.
See Profiling.
MPN_PATH
sparcv8 has
MPN_PATH="sparc32/v8 sparc32 generic"
which means look first for v8 code, then plain sparc32 (which is v7), and
finally fall back on generic C. Knowledgeable users with special requirements
can specify a different path. Normally this is completely unnecessary.
The demos subdirectory has some sample programs using GMP. These
aren't built or installed, but there's a Makefile with rules for them.
For instance,
make pexpr ./pexpr 68^975+10
gmp.texi. The usual automake
targets are available to make PostScript gmp.ps and/or DVI
gmp.dvi.
HTML can be produced with makeinfo --html, see Generating HTML. Or alternately
texi2html, see Texinfo to HTML.
PDF can be produced with texi2dvi --pdf (see PDF) or with pdftex.
Some supplementary notes can be found in the doc subdirectory.
ABI (Application Binary Interface) refers to the calling conventions between functions, meaning what registers are used and what sizes the various C data types are. ISA (Instruction Set Architecture) refers to the instructions and registers a CPU has available.
Some 64-bit ISA CPUs have both a 64-bit ABI and a 32-bit ABI defined, the
latter for compatibility with older CPUs in the family. GMP supports some
CPUs like this in both ABIs. In fact within GMP ABI means a
combination of chip ABI, plus how GMP chooses to use it. For example in some
32-bit ABIs, GMP may support a limb as either a 32-bit long or a 64-bit
long long.
By default GMP chooses the best ABI available for a given system, and this
generally gives significantly greater speed. But an ABI can be chosen
explicitly to make GMP compatible with other libraries, or particular
application requirements. For example,
./configure ABI=32
In all cases it's vital that all object code used in a given program is compiled for the same ABI.
Usually a limb is implemented as a long. When a long long limb
is used this is encoded in the generated gmp.h. This is convenient for
applications, but it does mean that gmp.h will vary, and can't be just
copied around. gmp.h remains compiler independent though, since all
compilers for a particular ABI will be expected to use the same limb type.
Currently no attempt is made to follow whatever conventions a system has for
installing library or header files built for a particular ABI. This will
probably only matter when installing multiple builds of GMP, and it might be
as simple as configuring with a special libdir, or it might require
more than that. Note that builds for different ABIs need to done separately,
with a fresh ./configure and make each.
hppa2.0*)
ABI=2.0w
cc. gcc support for this is in progress.
Applications must be compiled with
cc +DD64
ABI=2.0n
long long. This is available on HP-UX 10 or up when using
cc. No gcc support is planned for this. Applications
must be compiled with
cc +DA2.0 +e
ABI=1.0
All three ABIs are available for CPUs hppa2.0w and hppa2.0, but
for CPU hppa2.0n only 2.0n or 1.0 are allowed.
mips*-*-irix[6789])
gcc
is required (2.95 for instance).
ABI=n32
long long. Applications must be compiled with
gcc -mabi=n32 cc -n32
ABI=64
gcc -mabi=64 cc -64
Note that MIPS GNU/Linux, as of kernel version 2.2, doesn't have the necessary
support for n32 or 64 and so only gets a 32-bit limb and the MIPS 2 code.
powerpc64*)
ABI=aix64
powerpc64*-*-aix*. Applications must be compiled (and linked) with
gcc -maix64 xlc -q64
ABI=32L
long long in
64-bit registers. Applications must be compiled with
gcc -mpowerpc64
ABI=32
sparcv9 and ultrasparc*)
ABI=64
cc is required. Applications must be compiled with
gcc -m64 -mptr64 -Wa,-xarch=v9 -mcpu=v9 cc -xarch=v9
ABI=32
gcc -mv8plus cc -xarch=v8plus
gcc 2.8 and earlier only supports -mv8 though.
Don't be confused by the names of these sparc -m and -x options,
they're called arch but they effectively control the ABI.
On Solaris 2.7 with the kernel in 32-bit-mode, a normal native build will
reject ABI=64 because the resulting executables won't run.
ABI=64 can still be built if desired by making it look like a
cross-compile, for example
./configure --build=none --host=sparcv9-sun-solaris2.7 ABI=64
GMP should present no great difficulties for packaging in a binary distribution.
Libtool is used to build the library and -version-info is set
appropriately, having started from 3:0:0 in GMP 3.0. The GMP 4 series
will be upwardly binary compatible in each release and will be upwardly binary
compatible with all of the GMP 3 series. Additional function interfaces may
be added in each release, so on systems where libtool versioning is not fully
checked by the loader an auxiliary mechanism may be needed to express that a
dynamic linked application depends on a new enough GMP.
An auxiliary mechanism may also be needed to express that libgmpxx.la
(from --enable-cxx, see Build Options) requires libgmp.la
from the same GMP version, since this is not done by the libtool versioning,
nor otherwise. A mismatch will result in unresolved symbols from the linker,
or perhaps the loader.
Using DESTDIR or a prefix override with make install and
a shared libgmpxx may run into a libtool relinking problem, see
Known Build Problems.
When building a package for a CPU family, care should be taken to use
--host (or --build) to choose the least common denominator among
the CPUs which might use the package. For example this might necessitate
i386 for x86s, or plain sparc (meaning V7) for SPARCs.
Users who care about speed will want GMP built for their exact CPU type, to
make use of the available optimizations. Providing a way to suitably rebuild
a package may be useful. This could be as simple as making it possible for a
user to omit --build (and --host) so ./config.guess will
detect the CPU. But a way to manually specify a --build will be wanted
for systems where ./config.guess is inexact.
Note that gmp.h is a generated file, and will be architecture and ABI
dependent.
*-*-aix[34]* shared libraries are disabled by default, since
some versions of the native ar fail on the convenience libraries
used. A shared build can be attempted with
./configure --enable-shared --disable-static
Note that the --disable-static is necessary because in a shared build
libtool makes libgmp.a a symlink to libgmp.so, apparently for
the benefit of old versions of ld which only recognise .a,
but unfortunately this is done even if a fully functional ld is
available.
arm*-*-*, versions of GCC up to and including 2.95.3 have a
bug in unsigned division, giving wrong results for some operands. GMP
./configure will demand GCC 2.95.4 or later.
*-*-cygwin*, *-*-mingw* and *-*-pw32* by
default GMP builds only a static library, but a DLL can be built instead using
./configure --disable-static --enable-shared
Static and DLL libraries can't both be built, since certain export directives
in gmp.h must be different. --enable-cxx cannot be used when
building a DLL, since libtool doesn't currently support C++ DLLs. This might
change in the future.
GCC is recommended for compiling GMP, but the resulting DLL can be used with
any compiler. On mingw only the standard Windows libraries will be needed, on
Cygwin the usual cygwin runtime will be required.
m68k is taken to mean 68000. m68020 or higher will give a
performance boost on applicable CPUs. m68360 can be used for CPU32
series chips. m68302 can be used for "Dragonball" series chips,
though this is merely a synonym for m68000.
m4 in this release of OpenBSD has a bug in eval that makes it
unsuitable for .asm file processing. ./configure will detect
the problem and either abort or choose another m4 in the PATH. The bug
is fixed in OpenBSD 2.7, so either upgrade or use GNU m4.
power* and powerpc* will each use instructions
not available on the other, so it's important to choose the right one for the
CPU that will be used. Currently GMP has no assembler code support for using
just the common instruction subset. To get executables that run on both, the
current suggestion is to use the generic C code (CPU none), possibly
with appropriate compiler options (like -mcpu=common for
gcc). CPU rs6000 (which is not a CPU but a family of
workstations) is accepted by config.sub, but is currently equivalent to
none.
sparcv8 or supersparc on relevant systems will give a
significant performance increase over the V7 code.
/usr/bin/m4 lacks various features needed to process .asm
files, and instead ./configure will automatically use
/usr/5bin/m4, which we believe is always available (if not then use
GNU m4).
i386 selects generic code which will run reasonably well on all x86
chips.
i586, pentium or pentiummmx code is good for the intended
P5 Pentium chips, but quite slow when run on Intel P6 class chips (PPro, P-II,
P-III). i386 is a better choice when making binaries that must run on
both.
pentium4 and an SSE2 capable assembler are important for best results
on Pentium 4. The specific code is for instance roughly a 2x to
3x speedup over the generic i386 code.
Old versions of gas don't support MMX instructions, in particular
version 1.92.3 that comes with FreeBSD 2.2.8 doesn't (and unfortunately
there's no newer assembler for that system).
Solaris 2.6 and 2.7 as generate incorrect object code for register
to register movq instructions, and so can't be used for MMX code.
Install a recent gas if MMX code is wanted on these systems.
-march=pentiumpro
mpz/powm.c when
-march=pentiumpro was used, so for relevant CPUs that option is only in
the default CFLAGS for GCC 2.95.4 and up.
You might find more up-to-date information at http://swox.com/gmp/.
bash 2.03 is unable to run the configure
script, it exits silently, having died writing a preamble to
config.log. Use bash 2.04 or higher.
make all was found to run out of memory during the final
libgmp.la link on one system tested, despite having 64Mb available. A
separate make libgmp.la helped, perhaps recursing into the various
subdirectories uses up memory.
DESTDIR and shared libgmpxx
make install DESTDIR=/my/staging/area or the same with a prefix
override to install to a temporary directory is not fully supported by current
versions of libtool when building a shared version of a library which depends
on another being built at the same time, like libgmpxx and
libgmp.
The problem is that libgmpxx is relinked at the install stage to ensure
that if the system puts a hard-coded path to libgmp within
libgmpxx then that path will be correct. Naturally the linker is
directed to look only at the final location, not the staging area, so if
libgmp is not already in that final location then the link will fail.
On systems which don't hard-code library paths, for instance SVR4 style
systems such as GNU/Linux, a workaround is to insert a suitable -L in
the relink_command of libgmpxx.la after building but before
installing. This can be automated with something like
sed '/^relink_command/s:libgmp.la:-L /my/staging/area libgmp.la:' \
<libgmpxx.la >libgmpxx.new
mv libgmpxx.new libgmpxx.la
strip
GNU binutils strip should not be used on the static libraries
libgmp.a and libmp.a, neither directly nor via make
install-strip. It can be used on the shared libraries libgmp.so and
libmp.so though.
Currently (binutils 2.10.0), strip unpacks an archive then operates
on the files, but GMP contains multiple object files of the same name
(eg. three versions of init.o), and they overwrite each other, leaving
only the one that happens to be last.
If stripped static libraries are wanted, the suggested workaround is to build
normally, strip the separate object files, and do another make all to
rebuild. Alternately CFLAGS with -g omitted can always be used
if it's just debugging which is unwanted.
make syntax error
make
is unable to handle the long dependencies list for libgmp.la. The
symptom is a "syntax error" on the following line of the top-level
Makefile.
libgmp.la: $(libgmp_la_OBJECTS) $(libgmp_la_DEPENDENCIES)
Either use GNU Make, or as a workaround remove
$(libgmp_la_DEPENDENCIES) from that line (which will make the initial
build work, but if any recompiling is done libgmp.la might not be
rebuilt).
cc. This compiler cannot be used to build GMP, you
need to get a real GCC, and install that. (NeXT may have fixed this in
release 3.3 of their system.)
sed prints an error "Output line too long" when libtool
builds libgmp.la. This doesn't seem to cause any obvious ill effects,
but GNU sed is recommended, to avoid any doubt.
gmp_randinit_lc_2exp_size. The exact cause is unknown,
--disable-shared is recommended.
libgmp, libtool creates wrapper scripts
like t-mul for programs that would normally be t-mul.exe, in
order to setup the right library paths etc. This works fine, but the absence
of t-mul.exe etc causes make to think they need recompiling
every time, which is an annoyance when re-running a make check.
Using functions, macros, data types, etc. not documented in this manual is strongly discouraged. If you do so your application is guaranteed to be incompatible with future versions of GMP.
All declarations needed to use GMP are collected in the include file
gmp.h. It is designed to work with both C and C++ compilers.
#include <gmp.h>
Note however that prototypes for GMP functions with FILE * parameters
are only provided if <stdio.h> is included too.
#include <stdio.h> #include <gmp.h>
Likewise <stdarg.h> (or <varargs.h>) is required for prototypes
with va_list parameters, such as gmp_vprintf. And
<obstack.h> for prototypes with struct obstack parameters, such
as gmp_obstack_printf, when available.
All programs using GMP must link against the libgmp library. On a
typical Unix-like system this can be done with -lgmp, for example
gcc myprogram.c -lgmp
GMP C++ functions are in a separate libgmpxx library. This is built
and installed if C++ support has been enabled (see Build Options). For
example,
g++ mycxxprog.cc -lgmpxx -lgmp
GMP is built using Libtool and an application can use that to link if desired, see Shared library support for GNU
If GMP has been installed to a non-standard location then it may be necessary
to use -I and -L compiler options to point to the right
directories, and some sort of run-time path for a shared library. Consult
your compiler documentation, for instance Introduction.
In this manual, integer usually means a multiple precision integer, as
defined by the GMP library. The C data type for such integers is mpz_t.
Here are some examples of how to declare such integers:
mpz_t sum;
struct foo { mpz_t x, y; };
mpz_t vec[20];
Rational number means a multiple precision fraction. The C data type
for these fractions is mpq_t. For example:
mpq_t quotient;
Floating point number or Float for short, is an arbitrary precision
mantissa with a limited precision exponent. The C data type for such objects
is mpf_t.
A limb means the part of a multi-precision number that fits in a single
machine word. (We chose this word because a limb of the human body is
analogous to a digit, only larger, and containing several digits.) Normally a
limb is 32 or 64 bits. The C data type for a limb is mp_limb_t.
There are six classes of functions in the GMP library:
mpz_. The associated type is mpz_t. There are about 150
functions in this class.
mpq_. The associated type is mpq_t. There are about 40
functions in this class, but the integer functions can be used for arithmetic
on the numerator and denominator separately.
mpf_. The associated type is mpf_t. There are about 60
functions is this class.
itom, madd, and
mult. The associated type is MINT.
mpn_. The associated type is array of mp_limb_t. There are
about 30 (hard-to-use) functions in this class.
GMP functions generally have output arguments before input arguments. This notation is by analogy with the assignment operator. The BSD MP compatibility functions are exceptions, having the output arguments last.
GMP lets you use the same variable for both input and output in one call. For
example, the main function for integer multiplication, mpz_mul, can be
used to square x and put the result back in x with
mpz_mul (x, x, x);
Before you can assign to a GMP variable, you need to initialize it by calling one of the special initialization functions. When you're done with a variable, you need to clear it out, using one of the functions for that purpose. Which function to use depends on the type of variable. See the chapters on integer functions, rational number functions, and floating-point functions for details.
A variable should only be initialized once, or at least cleared between each initialization. After a variable has been initialized, it may be assigned to any number of times.
For efficiency reasons, avoid excessive initializing and clearing. In
general, initialize near the start of a function and clear near the end. For
example,
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);
}
When a GMP variable is used as a function parameter, it's effectively a
call-by-reference, meaning if the function stores a value there it will change
the original in the caller. Parameters which are input-only can be designated
const to provoke a compiler error or warning on attempting to modify
them.
When a function is going to return a GMP result, it should designate a
parameter that it sets, like the library functions do. More than one value
can be returned by having more than one output parameter, again like the
library functions. A return of an mpz_t etc doesn't return the
object, only a pointer, and this is almost certainly not what's wanted.
Here's an example accepting an mpz_t parameter, doing a calculation,
and storing the result to the indicated parameter.
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;
}
foo works even if the mainline passes the same variable for
param and result, just like the library functions. But
sometimes it's tricky to make that work, and an application might not want to
bother supporting that sort of thing.
For interest, the GMP types mpz_t etc are implemented as one-element
arrays of certain structures. This is why declaring a variable creates an
object with the fields GMP needs, but then using it as a parameter passes a
pointer to the object. Note that the actual fields in each mpz_t etc
are for internal use only and should not be accessed directly by code that
expects to be compatible with future GMP releases.
The GMP types like mpz_t are small, containing only a couple of sizes,
and pointers to allocated data. Once a variable is initialized, GMP takes
care of all space allocation. Additional space is allocated whenever a
variable doesn't have enough.
mpz_t and mpq_t variables never reduce their allocated space.
Normally this is the best policy, since it avoids frequent reallocation.
Applications that need to return memory to the heap at some particular point
can use mpz_realloc2, or clear variables no longer needed.
mpf_t variables, in the current implementation, use a fixed amount of
space, determined by the chosen precision and allocated at initialization, so
their size doesn't change.
All memory is allocated using malloc and friends by default, but this
can be changed, see Custom Allocation. Temporary memory on the stack is
also used (via alloca), but this can be changed at build-time if
desired, see Build Options.
GMP is reentrant and thread-safe, with some exceptions:
--enable-alloca=malloc-notreentrant (or with
--enable-alloca=notreentrant when alloca is not available),
then naturally GMP is not reentrant.
mpf_set_default_prec and mpf_init use a global variable for the
selected precision. mpf_init2 can be used instead.
mpz_random and the other old random number functions use a global
random state and are hence not reentrant. The newer random number functions
that accept a gmp_randstate_t parameter can be used instead.
mp_set_memory_functions uses global variables to store the selected
memory allocation functions.
mp_set_memory_functions (or malloc and friends by default) are
not reentrant, then GMP will not be reentrant either.
fwrite are not reentrant then the
GMP I/O functions using them will not be reentrant either.
gmp_randstate_t simultaneously,
since this involves an update of that variable.
<ctype.h> macros use per-file static
variables and may not be reentrant, depending whether the compiler optimizes
away fetches from them. The GMP text-based input functions are affected.
| const int mp_bits_per_limb | Global Constant |
| The number of bits per limb. |
| __GNU_MP_VERSION | Macro |
| __GNU_MP_VERSION_MINOR | Macro |
| __GNU_MP_VERSION_PATCHLEVEL | Macro |
| The major and minor GMP version, and patch level, respectively, as integers. For GMP i.j, these numbers will be i, j, and 0, respectively. For GMP i.j.k, these numbers will be i, j, and k, respectively. |
| const char * const gmp_version | Global Constant |
The GMP version number, as a null-terminated string, in the form "i.j" or
"i.j.k". This release is "4.1".
|
This version of GMP is upwardly binary compatible with all 4.x and 3.x versions, and upwardly compatible at the source level with all 2.x versions, with the following exceptions.
mpn_gcd had its source arguments swapped as of GMP 3.0, for consistency
with other mpn functions.
mpf_get_prec counted precision slightly differently in GMP 3.0 and
3.0.1, but in 3.1 reverted to the 2.x style.
There are a number of compatibility issues between GMP 1 and GMP 2 that of course also apply when porting applications from GMP 1 to GMP 4. Please see the GMP 2 manual for details.
The Berkeley MP compatibility library (see BSD Compatible Functions) is
source and binary compatible with the standard libmp.
libgmp.a should be
used for maximum speed, since the PIC code in the shared libgmp.so will
have a small overhead on each function call and global data address. For many
programs this will be insignificant, but for long calculations there's a gain
to be had.
A language interpreter might want to keep a free list or stack of
initialized variables ready for use. It should be possible to integrate
something like that with a garbage collector too.
mpz_t or mpq_t variable used to hold successively increasing
values will have its memory repeatedly realloced, which could be quite
slow or could fragment memory, depending on the C library. If an application
can estimate the final size then mpz_init2 or mpz_realloc2 can
be called to allocate the necessary space from the beginning
(see Initializing Integers).
It doesn't matter if a size set with mpz_init2 or mpz_realloc2
is too small, since all functions will do a further reallocation if necessary.
Badly overestimating memory required will waste space though.
2exp functions
mpz_mul_2exp when
appropriate. General purpose functions like mpz_mul make no attempt to
identify powers of two or other special forms, because such inputs will
usually be very rare and testing every time would be wasteful.
ui and si functions
ui functions and the small number of si functions exist for
convenience and should be used where applicable. But if for example an
mpz_t contains a value that fits in an unsigned long there's no
need extract it and call a ui function, just use the regular mpz
function.
mpz_abs, mpq_abs, mpf_abs, mpz_neg, mpq_neg
and mpf_neg are fast when used for in-place operations like
mpz_abs(x,x), since in the current implementation only a single field
of x needs changing. On suitable compilers (GCC for instance) this is
inlined too.
mpz_add_ui, mpz_sub_ui, mpf_add_ui and mpf_sub_ui
benefit from an in-place operation like mpz_add_ui(x,x,y), since
usually only one or two limbs of x will need to be changed. The same
applies to the full precision mpz_add etc if y is small. If
y is big then cache locality may be helped, but that's all.
mpz_mul is currently the opposite, a separate destination is slightly
better. A call like mpz_mul(x,x,y) will, unless y is only one
limb, make a temporary copy of x before forming the result. Normally
that copying will only be a tiny fraction of the time for the multiply, so
this is not a particularly important consideration.
mpz_set, mpq_set, mpq_set_num, mpf_set, etc, make
no attempt to recognise a copy of something to itself, so a call like
mpz_set(x,x) will be wasteful. Naturally that would never be written
deliberately, but if it might arise from two pointers to the same object then
a test to avoid it might be desirable.
if (x != y) mpz_set (x, y);
Note that it's never worth introducing extra mpz_set calls just to get
in-place operations. If a result should go to a particular variable then just
direct it there and let GMP take care of data movement.
mpz_divisible_ui_p and mpz_congruent_ui_p are the best functions
for testing whether an mpz_t is divisible by an individual small
integer. They use an algorithm which is faster than mpz_tdiv_ui, but
which gives no useful information about the actual remainder, only whether
it's zero (or a particular value).
However when testing divisibility by several small integers, it's best to take a remainder modulo their product, to save multi-precision operations. For instance to test whether a number is divisible by any of 23, 29 or 31 take a remainder modulo 23*29*31 = 20677 and then test that.
The division functions like mpz_tdiv_q_ui which give a quotient as well
as a remainder are generally a little slower than the remainder-only functions
like mpz_tdiv_ui. If the quotient is only rarely wanted then it's
probably best to just take a remainder and then go back and calculate the
quotient if and when it's wanted (mpz_divexact_ui can be used if the
remainder is zero).
mpq functions operate on mpq_t values with no common factors
in the numerator and denominator. Common factors are checked-for and cast out
as necessary. In general, cancelling factors every time is the best approach
since it minimizes the sizes for subsequent operations.
However, applications that know something about the factorization of the values they're working with might be able to avoid some of the GCDs used for canonicalization, or swap them for divisions. For example when multiplying by a prime it's enough to check for factors of it in the denominator instead of doing a full GCD. Or when forming a big product it might be known that very little cancellation will be possible, and so canonicalization can be left to the end.
The mpq_numref and mpq_denref macros give access to the
numerator and denominator to do things outside the scope of the supplied
mpq functions. See Applying Integer Functions.
The canonical form for rationals allows mixed-type mpq_t and integer
additions or subtractions to be done directly with multiples of the
denominator. This will be somewhat faster than mpq_add. For example,
/* mpq increment */ mpz_add (mpq_numref(q), mpq_numref(q), mpq_denref(q)); /* mpq += unsigned long */ mpz_addmul_ui (mpq_numref(q), mpq_denref(q), 123UL); /* mpq -= mpz */ mpz_submul (mpq_numref(q), mpq_denref(q), z);
mpz_fac_ui, mpz_fib_ui and mpz_bin_uiui
are designed for calculating isolated values. If a range of values is wanted
it's probably best to call to get a starting point and iterate from there.
Maybe we can hope octal will one day become the normal base for everyday use, as proposed by King Charles XII of Sweden and later reformers.
--enable-alloca choices in
Build Options, for how to address this.
init GMP variables will have unpredictable effects, and
corruption arising elsewhere in a program may well affect GMP. Initializing
GMP variables more than once or failing to clear them will cause memory leaks.
In all such cases a malloc debugger is recommended. On a GNU or BSD system
the standard C library malloc has some diagnostic facilities, see
Allocation Debugging, or
man 3 malloc. Other possibilities, in no particular order, include
http://www.inf.ethz.ch/personal/biere/projects/ccmalloc http://quorum.tamu.edu/jon/gnu (debauch) http://dmalloc.com http://www.perens.com/FreeSoftware (electric fence) http://packages.debian.org/fda http://www.gnupdate.org/components/leakbug http://people.redhat.com/~otaylor/memprof http://www.cbmamiga.demon.co.uk/mpatrol
The GMP default allocation routines in memory.c also have a simple
sentinel scheme which can be enabled with #define DEBUG in that file.
This is mainly designed for detecting buffer overruns during GMP development,
but might find other uses.
-fomit-frame-pointer
is used and this generally inhibits stack backtracing. Recompiling without
such options may help while debugging, though the usual caveats about it
potentially moving a memory problem or hiding a compiler bug will apply.
.gdbinit is included in the distribution, showing how to call
some undocumented dump functions to print GMP variables from within GDB. Note
that these functions shouldn't be used in final application code since they're
undocumented and may be subject to incompatible changes in future versions of
GMP.
mpz, mpq, mpf and mpfr each have an
init.c. If the debugger can't already determine the right one it may
help to build with absolute paths on each C file. One way to do that is to
use a separate object directory with an absolute path to the source directory.
cd /my/build/dir /my/source/dir/gmp-4.1/configure
This works via VPATH, and might require GNU make.
Alternately it might be possible to change the .c.lo rules
appropriately.
--enable-assert is available to add some consistency
checks to the library (see Build Options). These are likely to be of
limited value to most applications. Assertion failures are just as likely to
indicate memory corruption as a library or compiler bug.
Applications using the low-level mpn functions, however, will benefit
from --enable-assert since it adds checks on the parameters of most
such functions, many of which have subtle restrictions on their usage. Note
however that only the generic C code has checks, not the assembler code, so
CPU none should be used for maximum checking.
--enable-alloca=debug arranges that each block of
temporary memory in GMP is allocated with a separate call to malloc (or
the allocation function set with mp_set_memory_functions).
This can help a malloc debugger detect accesses outside the intended bounds,
or detect memory not released. In a normal build, on the other hand,
temporary memory is allocated in blocks which GMP divides up for its own use,
or may be allocated with a compiler builtin alloca which will go
nowhere near any malloc debugger hooks.
A build of GMP with checking within GMP itself can be made. This will run
very very slowly. Configure with
./configure --host=none-pc-linux-gnu CC=checkergcc
--host=none must be used, since the GMP assembler code doesn't support
the checking scheme. The GMP C++ features cannot be used, since current
versions of checker (0.9.9.1) don't yet support the standard C++ library.
Current versions (20020226 snapshot) don't support MMX or SSE, so GMP must be
configured for an x86 without those (eg. plain i386), or with a special
MPN_PATH that excludes those subdirectories (see Build Options).
Running a program under a profiler is a good way to find where it's spending most time and where improvements can be best sought.
Depending on the system, it may be possible to get a flat profile, meaning
simple timer sampling of the program counter, with no special GMP build
options, just a -p when compiling the mainline. This is a good way to
ensure minimum interference with normal operation. The necessary symbol type
and size information exists in most of the GMP assembler code.
The --enable-profiling build option can be used to add suitable
compiler flags, either for prof (-p) or gprof
(-pg), see Build Options. Which of the two is available and what
they do will depend on the system, and possibly on support available in
libc. For some systems appropriate corresponding mcount calls
are added to the assembler code too.
On x86 systems prof gives call counting, so that average time spent
in a function can be determined. gprof, where supported, adds call
graph construction, so for instance calls to mpn_add_n from
mpz_add and from mpz_mul can be differentiated.
On x86 and 68k systems -pg and -fomit-frame-pointer are
incompatible, so the latter is not used when gprof profiling is
selected, which may result in poorer code generation. If prof
profiling is selected instead it should still be possible to use
gprof, but only the gprof -p flat profile and call counts can
be expected to be valid, not the gprof -q call graph.
Autoconf based applications can easily check whether GMP is installed. The
only thing to be noted is that GMP library symbols from version 3 onwards have
prefixes like __gmpz. The following therefore would be a simple test,
AC_CHECK_LIB(gmp, __gmpz_init)
This just uses the default AC_CHECK_LIB actions for found or not found,
but an application that must have GMP would want to generate an error if not
found. For example,
AC_CHECK_LIB(gmp, __gmpz_init, , [AC_MSG_ERROR( [GNU MP not found, see http://swox.com/gmp])])
If functions added in some particular version of GMP are required, then one of
those can be used when checking. For example mpz_mul_si was added in
GMP 3.1,
AC_CHECK_LIB(gmp, __gmpz_mul_si, , [AC_MSG_ERROR( [GNU MP not found, or not 3.1 or up, see http://swox.com/gmp])])
An alternative would be to test the version number in gmp.h using say
AC_EGREP_CPP. That would make it possible to test the exact version,
if some particular sub-minor release is known to be necessary.
An application that can use either GMP 2 or 3 will need to test for
__gmpz_init (GMP 3 and up) or mpz_init (GMP 2), and it's also
worth checking for libgmp2 since Debian GNU/Linux systems used that
name in the past. For example,
AC_CHECK_LIB(gmp, __gmpz_init, ,
[AC_CHECK_LIB(gmp, mpz_init, ,
[AC_CHECK_LIB(gmp2, mpz_init)])])
In general it's suggested that applications should simply demand a new enough GMP rather than trying to provide supplements for features not available in past versions.
Occasionally an application will need or want to know the size of a type at
configuration or preprocessing time, not just with sizeof in the code.
This can be done in the normal way with mp_limb_t etc, but GMP 4.0 or
up is best for this, since prior versions needed certain -D defines on
systems using a long long limb. The following would suit Autoconf 2.50
or up,
AC_CHECK_SIZEOF(mp_limb_t, , [#include <gmp.h>])
The optional mpfr functions are provided in a separate
libmpfr.a, and this might be from GMP with --enable-mpfr or
from MPFR installed separately. Either way libmpfr depends on
libgmp, it doesn't stand alone. Currently only a static
libmpfr.a will be available, not a shared library, since upward binary
compatibility is not guaranteed.
AC_CHECK_LIB(mpfr, mpfr_add, , [AC_MSG_ERROR( [Need MPFR either from GNU MP 4 or separate MPFR package. See http://www.mpfr.org or http://swox.com/gmp])
If you think you have found a bug in the GMP library, please investigate it and report it. We have made this library available to you, and it is not too much to ask you to report the bugs you find.
Before you report a bug, check it's not already addressed in Known Build Problems, or perhaps Notes for Particular Systems. You may also want to check http://swox.com/gmp/ for patches for this release.
Please include the following in any report,
where in gdb, or $C in adb).
straces.
gcc, get the version
with gcc -v, otherwise perhaps what `which cc`, or similar.
uname -a.
./config.guess, and from running
./configfsf.guess (might be the same).
configure, then the contents of
config.log.
asm file not assembling, then the contents
of config.m4 and the offending line or lines from the temporary
mpn/tmp-<file>.s.
Please make an effort to produce a self-contained report, with something definite that can be tested or debugged. Vague queries or piecemeal messages are difficult to act on and don't help the development effort.
It is not uncommon that an observed problem is actually due to a bug in the compiler; the GMP code tends to explore interesting corners in compilers.
If your bug report is good, we will do our best to help you get a corrected version of the library; if the bug report is poor, we won't do anything about it (except maybe ask you to send a better report).
Send your report to: bug-gmp@gnu.org.
If you think something in this manual is unclear, or downright incorrect, or if the language needs to be improved, please send a note to the same address.
This chapter describes the GMP functions for performing integer arithmetic.
These functions start with the prefix mpz_.
GMP integers are stored in objects of type mpz_t.
The functions for integer arithmetic assume that all integer objects are
initialized. You do that by calling the function mpz_init. For
example,
{
mpz_t integ;
mpz_init (integ);
...
mpz_add (integ, ...);
...
mpz_sub (integ, ...);
/* Unless the program is about to exit, do ... */
mpz_clear (integ);
}
As you can see, you can store new values any number of times, once an object is initialized.
| void mpz_init (mpz_t integer) | Function |
| Initialize integer, and set its value to 0. |
| void mpz_init2 (mpz_t integer, unsigned long n) | Function |
|
Initialize integer, with space for n bits, and set its value to 0.
n is only the initial space, integer will grow automatically in
the normal way, if necessary, for subsequent values stored. |
| void mpz_clear (mpz_t integer) | Function |
Free the space occupied by integer. Call this function for all
mpz_t variables when you are done with them.
|
| void mpz_realloc2 (mpz_t integer, unsigned long n) | Function |
|
Change the space allocated for integer to n bits. The value in
integer is preserved if it fits, or is set to 0 if not.
This function can be used to increase the space for a variable in order to avoid repeated automatic reallocations, or to decrease it to give memory back to the heap. |
| void mpz_array_init (mpz_t integer_array[], size_t array_size, mp_size_t fixed_num_bits) | Function |
|
This is a special type of initialization. Fixed space of
fixed_num_bits bits is allocated to each of the array_size
integers in integer_array.
The space will not be automatically increased, unlike the normal
For other functions, or if in doubt, the suggestion is to calculate in a
regular
|
| void * _mpz_realloc (mpz_t integer, mp_size_t new_alloc) | Function |
|
Change the space for integer to new_alloc limbs. The value in
integer is preserved if it fits, or is set to 0 if not. The return
value is not useful to applications and should be ignored.
|
These functions assign new values to already initialized integers (see Initializing Integers).
| void mpz_set (mpz_t rop, mpz_t op) | Function |
| void mpz_set_ui (mpz_t rop, unsigned long int op) | Function |
| void mpz_set_si (mpz_t rop, signed long int op) | Function |
| void mpz_set_d (mpz_t rop, double op) | Function |
| void mpz_set_q (mpz_t rop, mpq_t op) | Function |
| void mpz_set_f (mpz_t rop, mpf_t op) | Function |
|
Set the value of rop from op.
|
| int mpz_set_str (mpz_t rop, char *str, int base) | Function |
|
Set the value of rop from str, a null-terminated C string in base
base. White space is allowed in the string, and is simply ignored. The
base may vary from 2 to 36. If base is 0, the actual base is determined
from the leading characters: if the first two characters are "0x" or "0X",
hexadecimal is assumed, otherwise if the first character is "0", octal is
assumed, otherwise decimal is assumed.
This function returns 0 if the entire string is a valid number in base base. Otherwise it returns -1. [It turns out that it is not entirely true that this function ignores
white-space. It does ignore it between digits, but not after a minus sign or
within or after "0x". We are considering changing the definition of this
function, making it fail when there is any white-space in the input, since
that makes a lot of sense. Send your opinion of this change to
bug-gmp@gnu.org. Do you really want it to accept |
| void mpz_swap (mpz_t rop1, mpz_t rop2) | Function |
| Swap the values rop1 and rop2 efficiently. |
For convenience, GMP provides a parallel series of initialize-and-set functions
which initialize the output and then store the value there. These functions'
names have the form mpz_init_set...
Here is an example of using one:
{
mpz_t pie;
mpz_init_set_str (pie, "3141592653589793238462643383279502884", 10);
...
mpz_sub (pie, ...);
...
mpz_clear (pie);
}
Once the integer has been initialized by any of the mpz_init_set...
functions, it can be used as the source or destination operand for the ordinary
integer functions. Don't use an initialize-and-set function on a variable
already initialized!
| void mpz_init_set (mpz_t rop, mpz_t op) | Function |
| void mpz_init_set_ui (mpz_t rop, unsigned long int op) | Function |
| void mpz_init_set_si (mpz_t rop, signed long int op) | Function |
| void mpz_init_set_d (mpz_t rop, double op) | Function |
| Initialize rop with limb space and set the initial numeric value from op. |
| int mpz_init_set_str (mpz_t rop, char *str, int base) | Function |
Initialize rop and set its value like mpz_set_str (see its
documentation above for details).
If the string is a correct base base number, the function returns 0;
if an error occurs it returns -1. rop is initialized even if
an error occurs. (I.e., you have to call |
This section describes functions for converting GMP integers to standard C types. Functions for converting to GMP integers are described in Assigning Integers and I/O of Integers.
| unsigned long int mpz_get_ui (mpz_t op) | Function |
Return the value of op as an unsigned long.
If op is too big to fit an |
| signed long int mpz_get_si (mpz_t op) | Function |
If op fits into a signed long int return the value of op.
Otherwise return the least significant part of op, with the same sign
as op.
If op is too big to fit in a |
| double mpz_get_d (mpz_t op) | Function |
Convert op to a double.
|
| double mpz_get_d_2exp (signed long int *exp, mpz_t op) | Function |
| Find d and exp such that d times 2 raised to exp, with 0.5<=abs(d)<1, is a good approximation to op. |
| char * mpz_get_str (char *str, int base, mpz_t op) | Function |
|
Convert op to a string of digits in base base. The base may vary
from 2 to 36.
If str is If str is not A pointer to the result string is returned, being either the allocated block, or the given str. |
| mp_limb_t mpz_getlimbn (mpz_t op, mp_size_t n) | Function |
|
Return limb number n from op. The sign of op is ignored,
just the absolute value is used. The least significant limb is number 0.
|
| void mpz_add (mpz_t rop, mpz_t op1, mpz_t op2) | Function |
| void mpz_add_ui (mpz_t rop, mpz_t op1, unsigned long int op2) | Function |
| Set rop to op1 + op2. |
| void mpz_sub (mpz_t rop, mpz_t op1, mpz_t op2) | Function |
| void mpz_sub_ui (mpz_t rop, mpz_t op1, unsigned long int op2) | Function |
| void mpz_ui_sub (mpz_t rop, unsigned long int op1, mpz_t op2) | Function |
| Set rop to op1 - op2. |
| void mpz_mul (mpz_t rop, mpz_t op1, mpz_t op2) | Function |
| void mpz_mul_si (mpz_t rop, mpz_t op1, long int op2) | Function |
| void mpz_mul_ui (mpz_t rop, mpz_t op1, unsigned long int op2) | Function |
| Set rop to op1 times op2. |
| void mpz_addmul (mpz_t rop, mpz_t op1, mpz_t op2) | Function |
| void mpz_addmul_ui (mpz_t rop, mpz_t op1, unsigned long int op2) | Function |
| Set rop to rop + op1 times op2. |
| void mpz_submul (mpz_t rop, mpz_t op1, mpz_t op2) | Function |
| void mpz_submul_ui (mpz_t rop, mpz_t op1, unsigned long int op2) | Function |
| Set rop to rop - op1 times op2. |
| void mpz_mul_2exp (mpz_t rop, mpz_t op1, unsigned long int op2) | Function |
| Set rop to op1 times 2 raised to op2. This operation can also be defined as a left shift by op2 bits. |
| void mpz_neg (mpz_t rop, mpz_t op) | Function |
| Set rop to -op. |
| void mpz_abs (mpz_t rop, mpz_t op) | Function |
| Set rop to the absolute value of op. |
Division is undefined if the divisor is zero. Passing a zero divisor to the
division or modulo functions (including the modular powering functions
mpz_powm and mpz_powm_ui), will cause an intentional division by
zero. This lets a program handle arithmetic exceptions in these functions the
same way as for normal C int arithmetic.
| void mpz_cdiv_q (mpz_t q, mpz_t n, mpz_t d) | Function |
| void mpz_cdiv_r (mpz_t r, mpz_t n, mpz_t d) | Function |
| void mpz_cdiv_qr (mpz_t q, mpz_t r, mpz_t n, mpz_t d) | Function |
| unsigned long int mpz_cdiv_q_ui (mpz_t q, mpz_t n, unsigned long int d) | Function |
| unsigned long int mpz_cdiv_r_ui (mpz_t r, mpz_t n, unsigned long int d) | Function |
| unsigned long int mpz_cdiv_qr_ui (mpz_t q, mpz_t r, mpz_t n, unsigned long int d) | Function |
| unsigned long int mpz_cdiv_ui (mpz_t n, unsigned long int d) | Function |
| void mpz_cdiv_q_2exp (mpz_t q, mpz_t n, unsigned long int b) | Function |
| void mpz_cdiv_r_2exp (mpz_t r, mpz_t n, unsigned long int b) | Function |
| void mpz_fdiv_q (mpz_t q, mpz_t n, mpz_t d) | Function |
| void mpz_fdiv_r (mpz_t r, mpz_t n, mpz_t d) | Function |
| void mpz_fdiv_qr (mpz_t q, mpz_t r, mpz_t n, mpz_t d) | Function |
| unsigned long int mpz_fdiv_q_ui (mpz_t q, mpz_t n, unsigned long int d) | Function |
| unsigned long int mpz_fdiv_r_ui (mpz_t r, mpz_t n, unsigned long int d) | Function |
| unsigned long int mpz_fdiv_qr_ui (mpz_t q, mpz_t r, mpz_t n, unsigned long int d) | Function |
| unsigned long int mpz_fdiv_ui (mpz_t n, unsigned long int d) | Function |
| void mpz_fdiv_q_2exp (mpz_t q, mpz_t n, unsigned long int b) | Function |
| void mpz_fdiv_r_2exp (mpz_t r, mpz_t n, unsigned long int b) | Function |
| void mpz_tdiv_q (mpz_t q, mpz_t n, mpz_t d) | Function |
| void mpz_tdiv_r (mpz_t r, mpz_t n, mpz_t d) | Function |
| void mpz_tdiv_qr (mpz_t q, mpz_t r, mpz_t n, mpz_t d) | Function |
| unsigned long int mpz_tdiv_q_ui (mpz_t q, mpz_t n, unsigned long int d) | Function |
| unsigned long int mpz_tdiv_r_ui (mpz_t r, mpz_t n, unsigned long int d) | Function |
| unsigned long int mpz_tdiv_qr_ui (mpz_t q, mpz_t r, mpz_t n, unsigned long int d) | Function |
| unsigned long int mpz_tdiv_ui (mpz_t n, unsigned long int d) | Function |
| void mpz_tdiv_q_2exp (mpz_t q, mpz_t n, unsigned long int b) | Function |
| void mpz_tdiv_r_2exp (mpz_t r, mpz_t n, unsigned long int b) | Function |
|
Divide n by d, forming a quotient q and/or remainder
r. For the
In all cases q and r will satisfy n=q*d+r, and r will satisfy 0<=abs(r)<abs(d). The For the The |
| void mpz_mod (mpz_t r, mpz_t n, mpz_t d) | Function |
| unsigned long int mpz_mod_ui (mpz_t r, mpz_t n, unsigned long int d) | Function |
Set r to n mod d. The sign of the divisor is
ignored; the result is always non-negative.
|
| void mpz_divexact (mpz_t q, mpz_t n, mpz_t d) | Function |
| void mpz_divexact_ui (mpz_t q, mpz_t n, unsigned long d) | Function |
|
Set q to n/d. These functions produce correct results only
when it is known in advance that d divides n.
These routines are much faster than the other division functions, and are the best choice when exact division is known to occur, for example reducing a rational to lowest terms. |
| int mpz_divisible_p (mpz_t n, mpz_t d) | Function |
| int mpz_divisible_ui_p (mpz_t n, unsigned long int d) | Function |
| int mpz_divisible_2exp_p (mpz_t n, unsigned long int b) | Function |
Return non-zero if n is exactly divisible by d, or in the case of
mpz_divisible_2exp_p by 2^b.
|
| int mpz_congruent_p (mpz_t n, mpz_t c, mpz_t d) | Function |
| int mpz_congruent_ui_p (mpz_t n, unsigned long int c, unsigned long int d) | Function |
| int mpz_congruent_2exp_p (mpz_t n, mpz_t c, unsigned long int b) | Function |
Return non-zero if n is congruent to c modulo d, or in the
case of mpz_congruent_2exp_p modulo 2^b.
|
| void mpz_powm (mpz_t rop, mpz_t base, mpz_t exp, mpz_t mod) | Function |
| void mpz_powm_ui (mpz_t rop, mpz_t base, unsigned long int exp, mpz_t mod) | Function |
|
Set rop to (base raised to exp)
modulo mod.
Negative exp is supported if an inverse base^-1 mod
mod exists (see |
| void mpz_pow_ui (mpz_t rop, mpz_t base, unsigned long int exp) | Function |
| void mpz_ui_pow_ui (mpz_t rop, unsigned long int base, unsigned long int exp) | Function |
| Set rop to base raised to exp. The case 0^0 yields 1. |
| int mpz_root (mpz_t rop, mpz_t op, unsigned long int n) | Function |
| Set rop to the truncated integer part of the nth root of op. Return non-zero if the computation was exact, i.e., if op is rop to the nth power. |
| void mpz_sqrt (mpz_t rop, mpz_t op) | Function |
| Set rop to the truncated integer part of the square root of op. |
| void mpz_sqrtrem (mpz_t rop1, mpz_t rop2, mpz_t op) | Function |
Set rop1 to the truncated integer part
of the square root of op, like mpz_sqrt. Set rop2 to the
remainder op-rop1*rop1, which will be zero if op is a
perfect square.
If rop1 and rop2 are the same variable, the results are undefined. |
| int mpz_perfect_power_p (mpz_t op) | Function |
|
Return non-zero if op is a perfect power, i.e., if there exist integers
a and b, with b>1, such that
op equals a raised to the power b.
Under this definition both 0 and 1 are considered to be perfect powers. Negative values of op are accepted, but of course can only be odd perfect powers. |
| int mpz_perfect_square_p (mpz_t op) | Function |
| Return non-zero if op is a perfect square, i.e., if the square root of op is an integer. Under this definition both 0 and 1 are considered to be perfect squares. |
| int mpz_probab_prime_p (mpz_t n, int reps) | Function |
|
Determine whether n is prime. Return 2 if n is definitely prime,
return 1 if n is probably prime (without being certain), or return 0 if
n is definitely composite.
This function does some trial divisions, then some Miller-Rabin probabilistic primality tests. reps controls how many such tests are done, 5 to 10 is a reasonable number, more will reduce the chances of a composite being returned as "probably prime". Miller-Rabin and similar tests can be more properly called compositeness tests. Numbers which fail are known to be composite but those which pass might be prime or might be composite. Only a few composites pass, hence those which pass are considered probably prime. |
| void mpz_nextprime (mpz_t rop, mpz_t op) | Function |
|
Set rop to the next prime greater than op.
This function uses a probabilistic algorithm to identify primes. For practical purposes it's adequate, the chance of a composite passing will be extremely small. |
| void mpz_gcd (mpz_t rop, mpz_t op1, mpz_t op2) | Function |
| Set rop to the greatest common divisor of op1 and op2. The result is always positive even if one or both input operands are negative. |
| unsigned long int mpz_gcd_ui (mpz_t rop, mpz_t op1, unsigned long int op2) | Function |
Compute the greatest common divisor of op1 and op2. If
rop is not NULL, store the result there.
If the result is small enough to fit in an |
| void mpz_gcdext (mpz_t g, mpz_t s, mpz_t t, mpz_t a, mpz_t b) | Function |
|
Set g to the greatest common divisor of a and b, and in
addition set s and t to coefficients satisfying
a*s + b*t = g.
g is always positive, even if one or both of a and b are
negative.
If t is |
| void mpz_lcm (mpz_t rop, mpz_t op1, mpz_t op2) | Function |
| void mpz_lcm_ui (mpz_t rop, mpz_t op1, unsigned long op2) | Function |
| Set rop to the least common multiple of op1 and op2. rop is always positive, irrespective of the signs of op1 and op2. rop will be zero if either op1 or op2 is zero. |
| int mpz_invert (mpz_t rop, mpz_t op1, mpz_t op2) | Function |
| Compute the inverse of op1 modulo op2 and put the result in rop. If the inverse exists, the return value is non-zero and rop will satisfy 0 <= rop < op2. If an inverse doesn't exist the return value is zero and rop is undefined. |
| int mpz_jacobi (mpz_t a, mpz_t b) | Function |
| Calculate the Jacobi symbol (a/b). This is defined only for b odd. |
| int mpz_legendre (mpz_t a, mpz_t p) | Function |
| Calculate the Legendre symbol (a/p). This is defined only for p an odd positive prime, and for such p it's identical to the Jacobi symbol. |
| int mpz_kronecker (mpz_t a, mpz_t b) |