X-Git-Url: http://git.xonotic.org/?p=xonotic%2Fxonotic.git;a=blobdiff_plain;f=misc%2Fbuilddeps%2Flinux32%2Fgmp%2Fshare%2Finfo%2Fgmp.info-1;fp=misc%2Fbuilddeps%2Flinux32%2Fgmp%2Fshare%2Finfo%2Fgmp.info-1;h=d1360599bdbbe5e1953a8f893e061c634bbb9740;hp=0000000000000000000000000000000000000000;hb=85864bd56ab6212ceba8b493afe8a54b14a9abb2;hpb=493accd7676823aa175639b70ad31242e6abdbd8 diff --git a/misc/builddeps/linux32/gmp/share/info/gmp.info-1 b/misc/builddeps/linux32/gmp/share/info/gmp.info-1 new file mode 100644 index 00000000..d1360599 --- /dev/null +++ b/misc/builddeps/linux32/gmp/share/info/gmp.info-1 @@ -0,0 +1,7084 @@ +This is ../../gmp/doc/gmp.info, produced by makeinfo version 4.8 from +../../gmp/doc/gmp.texi. + + 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 *Note GNU Free Documentation License::. + +INFO-DIR-SECTION GNU libraries +START-INFO-DIR-ENTRY +* gmp: (gmp). GNU Multiple Precision Arithmetic Library. +END-INFO-DIR-ENTRY + + +File: gmp.info, Node: Top, Next: Copying, Prev: (dir), Up: (dir) + +GNU MP +****** + + 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 *Note GNU Free Documentation License::. + + +* Menu: + +* Copying:: GMP Copying Conditions (LGPL). +* Introduction to GMP:: Brief introduction to GNU MP. +* Installing GMP:: How to configure and compile the GMP library. +* GMP Basics:: What every GMP user should know. +* Reporting Bugs:: How to usefully report bugs. +* Integer Functions:: Functions for arithmetic on signed integers. +* Rational Number Functions:: Functions for arithmetic on rational numbers. +* Floating-point Functions:: Functions for arithmetic on floats. +* Low-level Functions:: Fast functions for natural numbers. +* Random Number Functions:: Functions for generating random numbers. +* Formatted Output:: `printf' style output. +* Formatted Input:: `scanf' style input. +* C++ Class Interface:: Class wrappers around GMP types. +* BSD Compatible Functions:: All functions found in BSD MP. +* Custom Allocation:: How to customize the internal allocation. +* Language Bindings:: Using GMP from other languages. +* Algorithms:: What happens behind the scenes. +* Internals:: How values are represented behind the scenes. + +* Contributors:: Who brings you this library? +* References:: Some useful papers and books to read. +* GNU Free Documentation License:: +* Concept Index:: +* Function Index:: + + +File: gmp.info, Node: Copying, Next: Introduction to GMP, Prev: Top, Up: Top + +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 demonstration programs are +provided under the terms of the plain General Public License version 3, +see `COPYING'. + + +File: gmp.info, Node: Introduction to GMP, Next: Installing GMP, Prev: Copying, Up: Top + +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 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 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 . See +*Note Reporting Bugs:: for information about reporting bugs. + + +1.1 How to use this Manual +========================== + +Everyone should read *Note GMP Basics::. If you need to install the +library yourself, then read *Note Installing GMP::. If you have a +system with multiple ABIs, then read *Note 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. + + +File: gmp.info, Node: Installing GMP, Next: GMP Basics, Prev: Introduction to GMP, Up: Top + +2 Installing GMP +**************** + +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 +. See *Note Reporting Bugs::, for information on +what to include in useful bug reports. + +* Menu: + +* Build Options:: +* ABI and ISA:: +* Notes for Package Builds:: +* Notes for Particular Systems:: +* Known Build Problems:: +* Performance optimization:: + + +File: gmp.info, Node: Build Options, Next: ABI and ISA, Prev: Installing GMP, Up: Installing GMP + +2.1 Build Options +================= + +All the usual autoconf configure options are available, run `./configure +--help' for a summary. The file `INSTALL.autoconf' has some generic +installation information too. + +Tools + `configure' requires various Unix-like tools. See *Note Notes for + Particular Systems::, for some options on non-Unix systems. + + 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. + +Build Directory + To compile in a separate build directory, `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-5.0.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. + +`--prefix' and `--exec-prefix' + The `--prefix' option can be used in the normal way to direct GMP + to install under a particular tree. The default is `/usr/local'. + + `--exec-prefix' can be used to direct architecture-dependent files + like `libgmp.a' to a different location. This can be used to share + architecture-independent parts like the documentation, but + separate the dependent parts. Note however that `gmp.h' and + `mp.h' are architecture-dependent since they encode certain + aspects of `libgmp', so it will be necessary to ensure both + `$prefix/include' and `$exec_prefix/include' are available to the + compiler. + +`--disable-shared', `--disable-static' + By default both shared and static libraries are built (where + possible), but one or other can be disabled. Shared libraries + result in smaller executables and permit code sharing between + separate running processes, but on some CPUs are slightly slower, + having a small cost on each function call. + +Native Compilation, `--build=CPU-VENDOR-OS' + For normal native compilation, the system can be specified with + `--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. + +Cross Compilation, `--host=CPU-VENDOR-OS' + When cross-compiling, the system used for compiling is given by + `--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.) + +CPU types + In general, if you want a library that runs as fast as possible, + you should configure GMP for the exact CPU type your system uses. + However, this may mean the binaries won't run on older members of + the family, and might run slower on other members, older or newer. + The best idea is always to build GMP for the exact machine type + you intend to run it on. + + The following CPUs have specific support. See `configure.in' for + details of what code and compiler options they select. + + * Alpha: alpha, alphaev5, alphaev56, alphapca56, alphapca57, + alphaev6, alphaev67, alphaev68 alphaev7 + + * Cray: c90, j90, t90, sv1 + + * HPPA: hppa1.0, hppa1.1, hppa2.0, hppa2.0n, hppa2.0w, hppa64 + + * IA-64: ia64, itanium, itanium2 + + * MIPS: mips, mips3, mips64 + + * Motorola: m68k, m68000, m68010, m68020, m68030, m68040, + m68060, m68302, m68360, m88k, m88110 + + * POWER: power, power1, power2, power2sc + + * PowerPC: powerpc, powerpc64, powerpc401, powerpc403, + powerpc405, powerpc505, powerpc601, powerpc602, powerpc603, + powerpc603e, powerpc604, powerpc604e, powerpc620, powerpc630, + powerpc740, powerpc7400, powerpc7450, powerpc750, powerpc801, + powerpc821, powerpc823, powerpc860, powerpc970 + + * SPARC: sparc, sparcv8, microsparc, supersparc, sparcv9, + ultrasparc, ultrasparc2, ultrasparc2i, ultrasparc3, sparc64 + + * x86 family: i386, i486, i586, pentium, pentiummmx, pentiumpro, + pentium2, pentium3, pentium4, k6, k62, k63, athlon, amd64, + viac3, viac32 + + * Other: a29k, arm, clipper, i960, ns32k, pyramid, sh, sh2, vax, + z8k + + CPUs not listed will use generic C code. + +Generic C Build + If some of the assembly code causes problems, or if otherwise + desired, the generic C code can be selected with CPU `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. + +Fat binary, `--enable-fat' + Using `--enable-fat' selects a "fat binary" build on x86, where + optimized low level subroutines are chosen at runtime according to + the CPU detected. This means more code, but gives good + performance on all x86 chips. (This option might become available + for more architectures in the future.) + +`ABI' + On some systems GMP supports multiple ABIs (application binary + interfaces), meaning data type sizes and calling conventions. By + default GMP chooses the best ABI available, but a particular ABI + can be selected. For example + + ./configure --host=mips64-sgi-irix6 ABI=n32 + + See *Note ABI and ISA::, for the available choices on relevant + CPUs, and what applications need to do. + +`CC', `CFLAGS' + By default the C compiler used is chosen from among some likely + candidates, with `gcc' normally preferred if it's present. The + usual `CC=whatever' can be passed to `./configure' to choose + something different. + + For various 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 assembly 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' + Any flags like `-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. + +`CC_FOR_BUILD' + Some build-time programs are compiled and run to generate + host-specific data tables. `CC_FOR_BUILD' is the compiler used + for this. It doesn't need to be in any particular ABI or mode, it + merely needs to generate executables that can run. The default is + to try the selected `CC' and some likely candidates such as `cc' + and `gcc', looking for something that works. + + No flags are used with `CC_FOR_BUILD' because a simple invocation + like `cc foo.c' should be enough. If some particular options are + required they can be included as for instance `CC_FOR_BUILD="cc + -whatever"'. + +C++ Support, `--enable-cxx' + C++ support in GMP can be enabled with `--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' (*note Headers and + Libraries::). + + 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' + When C++ support is enabled, the C++ compiler and its flags can be + set with variables `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 C++ object files. + +Temporary Memory, `--enable-alloca=' + 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 `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. It actually + allocates just small blocks on the stack; larger ones use + malloc-reentrant. + + `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. *Note Custom Allocation::. + + An additional choice `--enable-alloca=debug' is available, to help + when debugging memory related problems (*note Debugging::). + +FFT Multiplication, `--disable-fft' + By default multiplications are done using Karatsuba, 3-way Toom, + and Fermat FFT. The FFT is only used on large to very large + operands and can be disabled to save code size if desired. + +Berkeley MP, `--enable-mpbsd' + The Berkeley MP compatibility library (`libmp') and header file + (`mp.h') are built and installed only if `--enable-mpbsd' is used. + *Note BSD Compatible Functions::. + +Assertion Checking, `--enable-assert' + This option enables some consistency checking within the library. + This can be of use while debugging, *note Debugging::. + +Execution Profiling, `--enable-profiling=prof/gprof/instrument' + Enable profiling support, in one of various styles, *note + Profiling::. + +`MPN_PATH' + Various assembly versions of each mpn subroutines are provided. + For a given CPU, a search is made though a path to choose a + version of each. For example `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. + +Documentation + The source for the document you're now reading is `doc/gmp.texi', + in Texinfo format, see *Note Texinfo: (texinfo)Top. + + Info format `doc/gmp.info' is included in the distribution. The + usual automake targets are available to make PostScript, DVI, PDF + and HTML (these will require various TeX and Texinfo tools). + + DocBook and XML can be generated by the Texinfo `makeinfo' program + too, see *Note Options for `makeinfo': (texinfo)makeinfo options. + + Some supplementary notes can also be found in the `doc' + subdirectory. + + + +File: gmp.info, Node: ABI and ISA, Next: Notes for Package Builds, Prev: Build Options, Up: Installing GMP + +2.2 ABI and ISA +=============== + +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. + + +AMD64 (`x86_64') + On AMD64 systems supporting both 32-bit and 64-bit modes for + applications, the following ABI choices are available. + + `ABI=64' + The 64-bit ABI uses 64-bit limbs and pointers and makes full + use of the chip architecture. This is the default. + Applications will usually not need special compiler flags, + but for reference the option is + + gcc -m64 + + `ABI=32' + The 32-bit ABI is the usual i386 conventions. This will be + slower, and is not recommended except for inter-operating + with other code not yet 64-bit capable. Applications must be + compiled with + + gcc -m32 + + (In GCC 2.95 and earlier there's no `-m32' option, it's the + only mode.) + + +HPPA 2.0 (`hppa2.0*', `hppa64') + + `ABI=2.0w' + The 2.0w ABI uses 64-bit limbs and pointers and is available + on HP-UX 11 or up. Applications must be compiled with + + gcc [built for 2.0w] + cc +DD64 + + `ABI=2.0n' + The 2.0n ABI means the 32-bit HPPA 1.0 ABI and all its normal + calling conventions, but with 64-bit instructions permitted + within functions. GMP uses a 64-bit `long long' for a limb. + This ABI is available on hppa64 GNU/Linux and on HP-UX 10 or + higher. Applications must be compiled with + + gcc [built for 2.0n] + cc +DA2.0 +e + + Note that current versions of GCC (eg. 3.2) don't generate + 64-bit instructions for `long long' operations and so may be + slower than for 2.0w. (The GMP assembly code is the same + though.) + + `ABI=1.0' + HPPA 2.0 CPUs can run all HPPA 1.0 and 1.1 code in the 32-bit + HPPA 1.0 ABI. No special compiler options are needed for + applications. + + All three ABIs are available for CPU types `hppa2.0w', `hppa2.0' + and `hppa64', but for CPU type `hppa2.0n' only 2.0n or 1.0 are + considered. + + Note that GCC on HP-UX has no options to choose between 2.0n and + 2.0w modes, unlike HP `cc'. Instead it must be built for one or + the other ABI. GMP will detect how it was built, and skip to the + corresponding `ABI'. + + +IA-64 under HP-UX (`ia64*-*-hpux*', `itanium*-*-hpux*') + HP-UX supports two ABIs for IA-64. GMP performance is the same in + both. + + `ABI=32' + In the 32-bit ABI, pointers, `int's and `long's are 32 bits + and GMP uses a 64 bit `long long' for a limb. Applications + can be compiled without any special flags since this ABI is + the default in both HP C and GCC, but for reference the flags + are + + gcc -milp32 + cc +DD32 + + `ABI=64' + In the 64-bit ABI, `long's and pointers are 64 bits and GMP + uses a `long' for a limb. Applications must be compiled with + + gcc -mlp64 + cc +DD64 + + On other IA-64 systems, GNU/Linux for instance, `ABI=64' is the + only choice. + + +MIPS under IRIX 6 (`mips*-*-irix[6789]') + IRIX 6 always has a 64-bit MIPS 3 or better CPU, and supports ABIs + o32, n32, and 64. n32 or 64 are recommended, and GMP performance + will be the same in each. The default is n32. + + `ABI=o32' + The o32 ABI is 32-bit pointers and integers, and no 64-bit + operations. GMP will be slower than in n32 or 64, this + option only exists to support old compilers, eg. GCC 2.7.2. + Applications can be compiled with no special flags on an old + compiler, or on a newer compiler with + + gcc -mabi=32 + cc -32 + + `ABI=n32' + The n32 ABI is 32-bit pointers and integers, but with a + 64-bit limb using a `long long'. Applications must be + compiled with + + gcc -mabi=n32 + cc -n32 + + `ABI=64' + The 64-bit ABI is 64-bit pointers and integers. Applications + must be compiled with + + 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. + + +PowerPC 64 (`powerpc64', `powerpc620', `powerpc630', `powerpc970', `power4', `power5') + + `ABI=aix64' + The AIX 64 ABI uses 64-bit limbs and pointers and is the + default on PowerPC 64 `*-*-aix*' systems. Applications must + be compiled with + + gcc -maix64 + xlc -q64 + + `ABI=mode64' + The `mode64' ABI uses 64-bit limbs and pointers, and is the + default on 64-bit GNU/Linux, BSD, and Mac OS X/Darwin + systems. Applications must be compiled with + + gcc -m64 + + `ABI=mode32' + The `mode32' ABI uses a 64-bit `long long' limb but with the + chip still in 32-bit mode and using 32-bit calling + conventions. This is the default on for systems where the + true 64-bit ABIs are unavailable. No special compiler + options are needed for applications. + + `ABI=32' + This is the basic 32-bit PowerPC ABI, with a 32-bit limb. No + special compiler options are needed for applications. + + GMP speed is greatest in `aix64' and `mode32'. In `ABI=32' only + the 32-bit ISA is used and this doesn't make full use of a 64-bit + chip. On a suitable system we could perhaps use more of the ISA, + but there are no plans to do so. + + +Sparc V9 (`sparc64', `sparcv9', `ultrasparc*') + + `ABI=64' + The 64-bit V9 ABI is available on the various BSD sparc64 + ports, recent versions of Sparc64 GNU/Linux, and Solaris 2.7 + and up (when the kernel is in 64-bit mode). GCC 3.2 or + higher, or Sun `cc' is required. On GNU/Linux, depending on + the default `gcc' mode, applications must be compiled with + + gcc -m64 + + On Solaris applications must be compiled with + + gcc -m64 -mptr64 -Wa,-xarch=v9 -mcpu=v9 + cc -xarch=v9 + + On the BSD sparc64 systems no special options are required, + since 64-bits is the only ABI available. + + `ABI=32' + For the basic 32-bit ABI, GMP still uses as much of the V9 + ISA as it can. In the Sun documentation this combination is + known as "v8plus". On GNU/Linux, depending on the default + `gcc' mode, applications may need to be compiled with + + gcc -m32 + + On Solaris, no special compiler options are required for + applications, though using something like the following is + recommended. (`gcc' 2.8 and earlier only support `-mv8' + though.) + + gcc -mv8plus + cc -xarch=v8plus + + GMP speed is greatest in `ABI=64', so it's the default where + available. The speed is partly because there are extra registers + available and partly because 64-bits is considered the more + important case and has therefore had better code written for it. + + Don't be confused by the names of the `-m' and `-x' compiler + options, they're called `arch' but effectively control both ABI + and ISA. + + On Solaris 2.6 and earlier, only `ABI=32' is available since the + kernel doesn't save all registers. + + 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 + + +File: gmp.info, Node: Notes for Package Builds, Next: Notes for Particular Systems, Prev: ABI and ISA, Up: Installing GMP + +2.3 Notes for Package Builds +============================ + +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 (*note Library +interface versions: (libtool)Versioning.). + + 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', *note 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. + + 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 mean plain +`sparc' (meaning V7) for SPARCs. + + For x86s, `--enable-fat' sets things up for a fat binary build, +making a runtime selection of optimized low level routines. This is a +good choice for packaging to run on a range of x86 chips. + + Users who care about speed will want GMP built for their exact CPU +type, to make best 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. + + On systems with multiple ABIs, a packaged build will need to decide +which among the choices is to be provided, see *Note ABI and ISA::. A +given run of `./configure' etc will only build one ABI. If a second +ABI is also required then a second run of `./configure' etc must be +made, starting from a clean directory tree (`make distclean'). + + As noted under "ABI and ISA", currently no attempt is made to follow +system conventions for install locations that vary with ABI, such as +`/usr/lib/sparcv9' for `ABI=64' as opposed to `/usr/lib' for `ABI=32'. +A package build can override `libdir' and other standard variables as +necessary. + + Note that `gmp.h' is a generated file, and will be architecture and +ABI dependent. When attempting to install two ABIs simultaneously it +will be important that an application compile gets the correct `gmp.h' +for its desired ABI. If compiler include paths don't vary with ABI +options then it might be necessary to create a `/usr/include/gmp.h' +which tests preprocessor symbols and chooses the correct actual `gmp.h'. + + +File: gmp.info, Node: Notes for Particular Systems, Next: Known Build Problems, Prev: Notes for Package Builds, Up: Installing GMP + +2.4 Notes for Particular Systems +================================ + +AIX 3 and 4 + On systems `*-*-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 + On systems `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. + +Compaq C++ + Compaq C++ on OSF 5.1 has two flavours of `iostream', a standard + one and an old pre-standard one (see `man iostream_intro'). GMP + can only use the standard one, which unfortunately is not the + default but must be selected by defining `__USE_STD_IOSTREAM'. + Configure with for instance + + ./configure --enable-cxx CPPFLAGS=-D__USE_STD_IOSTREAM + +Floating Point Mode + On some systems, the hardware floating point has a control mode + which can set all operations to be done in a particular precision, + for instance single, double or extended on x86 systems (x87 + floating point). The GMP functions involving a `double' cannot be + expected to operate to their full precision when the hardware is + in single precision mode. Of course this affects all code, + including application code, not just GMP. + +MS-DOS and MS Windows + On an MS-DOS system DJGPP can be used to build GMP, and on an MS + Windows system Cygwin, DJGPP and MINGW can be used. All three are + excellent ports of GCC and the various GNU tools. + + `http://www.cygwin.com/' + `http://www.delorie.com/djgpp/' + `http://www.mingw.org/' + + Microsoft also publishes an Interix "Services for Unix" which can + be used to build GMP on Windows (with a normal `./configure'), but + it's not free software. + +MS Windows DLLs + On systems `*-*-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. + + A MINGW DLL build of GMP can be used with Microsoft C. Libtool + doesn't install a `.lib' format import library, but it can be + created with MS `lib' as follows, and copied to the install + directory. Similarly for `libmp' and `libgmpxx'. + + cd .libs + lib /def:libgmp-3.dll.def /out:libgmp-3.lib + + MINGW uses the C runtime library `msvcrt.dll' for I/O, so + applications wanting to use the GMP I/O routines must be compiled + with `cl /MD' to do the same. If one of the other C runtime + library choices provided by MS C is desired then the suggestion is + to use the GMP string functions and confine I/O to the application. + +Motorola 68k CPU Types + `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'. + +OpenBSD 2.6 + `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 CPU Types + In GMP, CPU types `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 assembly 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'. + +Sparc CPU Types + `sparcv8' or `supersparc' on relevant systems will give a + significant performance increase over the V7 code selected by plain + `sparc'. + +Sparc App Regs + The GMP assembly code for both 32-bit and 64-bit Sparc clobbers the + "application registers" `g2', `g3' and `g4', the same way that the + GCC default `-mapp-regs' does (*note SPARC Options: (gcc)SPARC + Options.). + + This makes that code unsuitable for use with the special V9 + `-mcmodel=embmedany' (which uses `g4' as a data segment pointer), + and for applications wanting to use those registers for special + purposes. In these cases the only suggestion currently is to + build GMP with CPU `none' to avoid the assembly code. + +SunOS 4 + `/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). + +x86 CPU Types + `i586', `pentium' or `pentiummmx' code is good for its 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. + +x86 MMX and SSE2 Code + If the CPU selected has MMX code but the assembler doesn't support + it, a warning is given and non-MMX code is used instead. This + will be an inferior build, since the MMX code that's present is + there because it's faster than the corresponding plain integer + code. The same applies to SSE2. + + Old versions of `gas' don't support MMX instructions, in particular + version 1.92.3 that comes with FreeBSD 2.2.8 or the more recent + OpenBSD 3.1 doesn't. + + 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. + + +File: gmp.info, Node: Known Build Problems, Next: Performance optimization, Prev: Notes for Particular Systems, Up: Installing GMP + +2.5 Known Build Problems +======================== + +You might find more up-to-date information at `http://gmplib.org/'. + +Compiler link options + The version of libtool currently in use rather aggressively strips + compiler options when linking a shared library. This will + hopefully be relaxed in the future, but for now if this is a + problem the suggestion is to create a little script to hide them, + and for instance configure with + + ./configure CC=gcc-with-my-options + +DJGPP (`*-*-msdosdjgpp*') + The DJGPP port of `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. Running `make libgmp.la' directly helped, perhaps + recursing into the various subdirectories uses up memory. + +GNU binutils `strip' prior to 2.12 + `strip' from GNU binutils 2.11 and earlier should not be used on + the static libraries `libgmp.a' and `libmp.a' since it will + discard all but the last of multiple archive members with the same + name, like the three versions of `init.o' in `libgmp.a'. Binutils + 2.12 or higher can be used successfully. + + The shared libraries `libgmp.so' and `libmp.so' are not affected by + this and any version of `strip' can be used on them. + +`make' syntax error + On certain versions of SCO OpenServer 5 and IRIX 6.5 the native + `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). + +MacOS X (`*-*-darwin*') + Libtool currently only knows how to create shared libraries on + MacOS X using the native `cc' (which is a modified GCC), not a + plain GCC. A static-only build should work though + (`--disable-shared'). + +NeXT prior to 3.3 + The system compiler on old versions of NeXT was a massacred and + old GCC, even if it called itself `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.) + +POWER and PowerPC + Bugs in GCC 2.7.2 (and 2.6.3) mean it can't be used to compile GMP + on POWER or PowerPC. If you want to use GCC for these machines, + get GCC 2.7.2.1 (or later). + +Sequent Symmetry + Use the GNU assembler instead of the system assembler, since the + latter has serious bugs. + +Solaris 2.6 + The 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. + +Sparc Solaris 2.7 with gcc 2.95.2 in `ABI=32' + A shared library build of GMP seems to fail in this combination, + it builds but then fails the tests, apparently due to some + incorrect data relocations within `gmp_randinit_lc_2exp_size'. + The exact cause is unknown, `--disable-shared' is recommended. + + +File: gmp.info, Node: Performance optimization, Prev: Known Build Problems, Up: Installing GMP + +2.6 Performance optimization +============================ + +For optimal performance, build GMP for the exact CPU type of the target +computer, see *Note Build Options::. + + Unlike what is the case for most other programs, the compiler +typically doesn't matter much, since GMP uses assembly language for the +most critical operation. + + In particular for long-running GMP applications, and applications +demanding extremely large numbers, building and running the `tuneup' +program in the `tune' subdirectory, can be important. For example, + + cd tune + make tuneup + ./tuneup + + will generate better contents for the `gmp-mparam.h' parameter file. + + To use the results, put the output in the file file indicated in the +`Parameters for ...' header. Then recompile from scratch. + + The `tuneup' program takes one useful parameter, `-f NNN', which +instructs the program how long to check FFT multiply parameters. If +you're going to use GMP for extremely large numbers, you may want to +run `tuneup' with a large NNN value. + + +File: gmp.info, Node: GMP Basics, Next: Reporting Bugs, Prev: Installing GMP, Up: Top + +3 GMP Basics +************ + +*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.* + +* Menu: + +* 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:: + + +File: gmp.info, Node: Headers and Libraries, Next: Nomenclature and Types, Prev: GMP Basics, Up: GMP Basics + +3.1 Headers and Libraries +========================= + +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 + + Note however that prototypes for GMP functions with `FILE *' +parameters are only provided if `' is included too. + + #include + #include + + Likewise `' (or `') is required for prototypes +with `va_list' parameters, such as `gmp_vprintf'. And `' +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 (*note Build +Options::). For example, + + g++ mycxxprog.cc -lgmpxx -lgmp + + GMP is built using Libtool and an application can use that to link +if desired, *note GNU Libtool: (libtool)Top. + + 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. + + +File: gmp.info, Node: Nomenclature and Types, Next: Function Classes, Prev: Headers and Libraries, Up: GMP Basics + +3.2 Nomenclature and Types +========================== + +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'. For example: + + mpf_t fp; + + The floating point functions accept and return exponents in the C +type `mp_exp_t'. Currently this is usually a `long', but on some +systems it's an `int' for efficiency. + + 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'. + + Counts of limbs of a multi-precision number represented in the C type +`mp_size_t'. Currently this is normally a `long', but on some systems +it's an `int' for efficiency, and on some systems it will be `long +long' in the future. + + Counts of bits of a multi-precision number are represented in the C +type `mp_bitcnt_t'. Currently this is always an `unsigned long', but on +some systems it will be an `unsigned long long' in the future . + + "Random state" means an algorithm selection and current state data. +The C data type for such objects is `gmp_randstate_t'. For example: + + gmp_randstate_t rstate; + + Also, in general `mp_bitcnt_t' is used for bit counts and ranges, and +`size_t' is used for byte or character counts. + + +File: gmp.info, Node: Function Classes, Next: Variable Conventions, Prev: Nomenclature and Types, Up: GMP Basics + +3.3 Function Classes +==================== + +There are six classes of functions in the GMP library: + + 1. Functions for signed integer arithmetic, with names beginning with + `mpz_'. The associated type is `mpz_t'. There are about 150 + functions in this class. (*note Integer Functions::) + + 2. Functions for rational number arithmetic, with names beginning with + `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. (*note + Rational Number Functions::) + + 3. Functions for floating-point arithmetic, with names beginning with + `mpf_'. The associated type is `mpf_t'. There are about 60 + functions is this class. (*note Floating-point Functions::) + + 4. Functions compatible with Berkeley MP, such as `itom', `madd', and + `mult'. The associated type is `MINT'. (*note BSD Compatible + Functions::) + + 5. Fast low-level functions that operate on natural numbers. These + are used by the functions in the preceding groups, and you can + also call them directly from very time-critical user programs. + These functions' names begin with `mpn_'. The associated type is + array of `mp_limb_t'. There are about 30 (hard-to-use) functions + in this class. (*note Low-level Functions::) + + 6. Miscellaneous functions. Functions for setting up custom + allocation and functions for generating random numbers. (*note + Custom Allocation::, and *note Random Number Functions::) + + +File: gmp.info, Node: Variable Conventions, Next: Parameter Conventions, Prev: Function Classes, Up: GMP Basics + +3.4 Variable Conventions +======================== + +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); + } + + +File: gmp.info, Node: Parameter Conventions, Next: Memory Management, Prev: Variable Conventions, Up: GMP Basics + +3.5 Parameter Conventions +========================= + +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. + + +File: gmp.info, Node: Memory Management, Next: Reentrancy, Prev: Parameter Conventions, Up: GMP Basics + +3.6 Memory Management +===================== + +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 *Note Custom Allocation::. Temporary memory +on the stack is also used (via `alloca'), but this can be changed at +build-time if desired, see *Note Build Options::. + + +File: gmp.info, Node: Reentrancy, Next: Useful Macros and Constants, Prev: Memory Management, Up: GMP Basics + +3.7 Reentrancy +============== + +GMP is reentrant and thread-safe, with some exceptions: + + * If configured with `--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, and in the + C++ interface an explicit precision to the `mpf_class' constructor. + + * `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. + + * `gmp_randinit' (obsolete) returns an error indication through a + global variable, which is not thread safe. Applications are + advised to use `gmp_randinit_default' or `gmp_randinit_lc_2exp' + instead. + + * `mp_set_memory_functions' uses global variables to store the + selected memory allocation functions. + + * If the memory allocation functions set by a call to + `mp_set_memory_functions' (or `malloc' and friends by default) are + not reentrant, then GMP will not be reentrant either. + + * If the standard I/O functions such as `fwrite' are not reentrant + then the GMP I/O functions using them will not be reentrant either. + + * It's safe for two threads to read from the same GMP variable + simultaneously, but it's not safe for one to read while the + another might be writing, nor for two threads to write + simultaneously. It's not safe for two threads to generate a + random number from the same `gmp_randstate_t' simultaneously, + since this involves an update of that variable. + + +File: gmp.info, Node: Useful Macros and Constants, Next: Compatibility with older versions, Prev: Reentrancy, Up: GMP Basics + +3.8 Useful Macros and Constants +=============================== + + -- Global Constant: const int mp_bits_per_limb + The number of bits per limb. + + -- Macro: __GNU_MP_VERSION + -- Macro: __GNU_MP_VERSION_MINOR + -- Macro: __GNU_MP_VERSION_PATCHLEVEL + 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. + + -- Global Constant: const char * const gmp_version + The GMP version number, as a null-terminated string, in the form + "i.j.k". This release is "5.0.1". Note that the format "i.j" was + used when k was zero was used before version 4.3.0. + + -- Macro: __GMP_CC + -- Macro: __GMP_CFLAGS + The compiler and compiler flags, respectively, used when compiling + GMP, as strings. + + +File: gmp.info, Node: Compatibility with older versions, Next: Demonstration Programs, Prev: Useful Macros and Constants, Up: GMP Basics + +3.9 Compatibility with older versions +===================================== + +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 (*note BSD Compatible +Functions::) is source and binary compatible with the standard `libmp'. + + +File: gmp.info, Node: Demonstration Programs, Next: Efficiency, Prev: Compatibility with older versions, Up: GMP Basics + +3.10 Demonstration programs +=========================== + +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 + +The following programs are provided + + * `pexpr' is an expression evaluator, the program used on the GMP + web page. + + * The `calc' subdirectory has a similar but simpler evaluator using + `lex' and `yacc'. + + * The `expr' subdirectory is yet another expression evaluator, a + library designed for ease of use within a C program. See + `demos/expr/README' for more information. + + * `factorize' is a Pollard-Rho factorization program. + + * `isprime' is a command-line interface to the `mpz_probab_prime_p' + function. + + * `primes' counts or lists primes in an interval, using a sieve. + + * `qcn' is an example use of `mpz_kronecker_ui' to estimate quadratic + class numbers. + + * The `perl' subdirectory is a comprehensive perl interface to GMP. + See `demos/perl/INSTALL' for more information. Documentation is + in POD format in `demos/perl/GMP.pm'. + + As an aside, consideration has been given at various times to some +sort of expression evaluation within the main GMP library. Going +beyond something minimal quickly leads to matters like user-defined +functions, looping, fixnums for control variables, etc, which are +considered outside the scope of GMP (much closer to language +interpreters or compilers, *Note Language Bindings::.) Something +simple for program input convenience may yet be a possibility, a +combination of the `expr' demo and the `pexpr' tree back-end perhaps. +But for now the above evaluators are offered as illustrations. + + +File: gmp.info, Node: Efficiency, Next: Debugging, Prev: Demonstration Programs, Up: GMP Basics + +3.11 Efficiency +=============== + +Small Operands + On small operands, the time for function call overheads and memory + allocation can be significant in comparison to actual calculation. + This is unavoidable in a general purpose variable precision + library, although GMP attempts to be as efficient as it can on + both large and small operands. + +Static Linking + On some CPUs, in particular the x86s, the static `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. + +Initializing and Clearing + Avoid excessive initializing and clearing of variables, since this + can be quite time consuming, especially in comparison to otherwise + fast operations like addition. + + 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. + +Reallocations + An `mpz_t' or `mpq_t' variable used to hold successively increasing + values will have its memory repeatedly `realloc'ed, 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 (*note 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 + It's up to an application to call functions like `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 + The `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. + +In-Place Operations + `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. + +Divisibility Testing (Small Integers) + `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). + +Rational Arithmetic + The `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. *Note 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); + +Number Sequences + Functions like `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. + +Text Input/Output + Hexadecimal or octal are suggested for input or output in text + form. Power-of-2 bases like these can be converted much more + efficiently than other bases, like decimal. For big numbers + there's usually nothing of particular interest to be seen in the + digits, so the base doesn't matter much. + + 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. + + +File: gmp.info, Node: Debugging, Next: Profiling, Prev: Efficiency, Up: GMP Basics + +3.12 Debugging +============== + +Stack Overflow + Depending on the system, a segmentation violation or bus error + might be the only indication of stack overflow. See + `--enable-alloca' choices in *Note Build Options::, for how to + address this. + + In new enough versions of GCC, `-fstack-check' may be able to + ensure an overflow is recognised by the system before too much + damage is done, or `-fstack-limit-symbol' or + `-fstack-limit-register' may be able to add checking if the system + itself doesn't do any (*note Options for Code Generation: + (gcc)Code Gen Options.). These options must be added to the + `CFLAGS' used in the GMP build (*note Build Options::), adding + them just to an application will have no effect. Note also + they're a slowdown, adding overhead to each function call and each + stack allocation. + +Heap Problems + The most likely cause of application problems with GMP is heap + corruption. Failing to `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 *Note Allocation Debugging: (libc)Allocation + Debugging, or `man 3 malloc'. Other possibilities, in no + particular order, include + + `http://www.inf.ethz.ch/personal/biere/projects/ccmalloc/' + `http://dmalloc.com/' + `http://www.perens.com/FreeSoftware/' (electric fence) + `http://packages.debian.org/stable/devel/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. + +Stack Backtraces + On some systems the compiler options GMP uses by default can + interfere with debugging. In particular on x86 and 68k systems + `-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. + +GDB, the GNU Debugger + A sample `.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. + +Source File Paths + GMP has multiple source files with the same name, in different + directories. For example `mpz', `mpq' and `mpf' 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-5.0.1/configure + + This works via `VPATH', and might require GNU `make'. Alternately + it might be possible to change the `.c.lo' rules appropriately. + +Assertion Checking + The build option `--enable-assert' is available to add some + consistency checks to the library (see *Note 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 assembly code, so CPU `none' should be + used for maximum checking. + +Temporary Memory Checking + The build option `--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. + +Maximum Debuggability + To summarize the above, a GMP build for maximum debuggability + would be + + ./configure --disable-shared --enable-assert \ + --enable-alloca=debug --host=none CFLAGS=-g + + For C++, add `--enable-cxx CXXFLAGS=-g'. + +Checker + The GCC checker (`http://savannah.nongnu.org/projects/checker/') + can be used with GMP. It contains a stub library which means GMP + applications compiled with checker can use a normal GMP build. + + A build of GMP with checking within GMP itself can be made. This + will run very very slowly. On GNU/Linux for example, + + ./configure --host=none-pc-linux-gnu CC=checkergcc + + `--host=none' must be used, since the GMP assembly 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. + +Valgrind + The valgrind program (`http://valgrind.org/') is a memory checker + for x86s. It translates and emulates machine instructions to do + strong checks for uninitialized data (at the level of individual + bits), memory accesses through bad pointers, and memory leaks. + + Recent versions of Valgrind are getting support for MMX and + SSE/SSE2 instructions, for past versions GMP will need to be + configured not to use those, ie. for an x86 without them (for + instance plain `i486'). + +Other Problems + Any suspected bug in GMP itself should be isolated to make sure + it's not an application problem, see *Note Reporting Bugs::. + + +File: gmp.info, Node: Profiling, Next: Autoconf, Prev: Debugging, Up: GMP Basics + +3.13 Profiling +============== + +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. The +profiling choices for a GMP build are as follows. + +`--disable-profiling' + The default is to add nothing special for profiling. + + It should be possible to just compile the mainline of a program + with `-p' and use `prof' to get a profile consisting of + timer-based sampling of the program counter. Most of the GMP + assembly code has the necessary symbol information. + + This approach has the advantage of minimizing interference with + normal program operation, but on most systems the resolution of + the sampling is quite low (10 milliseconds for instance), + requiring long runs to get accurate information. + +`--enable-profiling=prof' + Build with support for the system `prof', which means `-p' added + to the `CFLAGS'. + + This provides call counting in addition to program counter + sampling, which allows the most frequently called routines to be + identified, and an average time spent in each routine to be + determined. + + The x86 assembly code has support for this option, but on other + processors the assembly routines will be as if compiled without + `-p' and therefore won't appear in the call counts. + + On some systems, such as GNU/Linux, `-p' in fact means `-pg' and in + this case `--enable-profiling=gprof' described below should be used + instead. + +`--enable-profiling=gprof' + Build with support for `gprof', which means `-pg' added to the + `CFLAGS'. + + This provides call graph construction in addition to call counting + and program counter sampling, which makes it possible to count + calls coming from different locations. For example the number of + calls to `mpn_mul' from `mpz_mul' versus the number from + `mpf_mul'. The program counter sampling is still flat though, so + only a total time in `mpn_mul' would be accumulated, not a + separate amount for each call site. + + The x86 assembly code has support for this option, but on other + processors the assembly routines will be as if compiled without + `-pg' and therefore not be included in the call counts. + + On x86 and m68k systems `-pg' and `-fomit-frame-pointer' are + incompatible, so the latter is omitted from the default flags in + that case, which might result in poorer code generation. + + Incidentally, it should be possible to use the `gprof' program + with a plain `--enable-profiling=prof' build. But in that case + only the `gprof -p' flat profile and call counts can be expected + to be valid, not the `gprof -q' call graph. + +`--enable-profiling=instrument' + Build with the GCC option `-finstrument-functions' added to the + `CFLAGS' (*note Options for Code Generation: (gcc)Code Gen + Options.). + + This inserts special instrumenting calls at the start and end of + each function, allowing exact timing and full call graph + construction. + + This instrumenting is not normally a standard system feature and + will require support from an external library, such as + + `http://sourceforge.net/projects/fnccheck/' + + This should be included in `LIBS' during the GMP configure so that + test programs will link. For example, + + ./configure --enable-profiling=instrument LIBS=-lfc + + On a GNU system the C library provides dummy instrumenting + functions, so programs compiled with this option will link. In + this case it's only necessary to ensure the correct library is + added when linking an application. + + The x86 assembly code supports this option, but on other + processors the assembly routines will be as if compiled without + `-finstrument-functions' meaning time spent in them will + effectively be attributed to their caller. + + +File: gmp.info, Node: Autoconf, Next: Emacs, Prev: Profiling, Up: GMP Basics + +3.14 Autoconf +============= + +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://gmplib.org/])]) + + 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://gmplib.org/])]) + + 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. + + In general it's recommended 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 ]) + + +File: gmp.info, Node: Emacs, Prev: Autoconf, Up: GMP Basics + +3.15 Emacs +========== + + (`info-lookup-symbol') is a good way to find documentation on +C functions while editing (*note Info Documentation Lookup: (emacs)Info +Lookup.). + + The GMP manual can be included in such lookups by putting the +following in your `.emacs', + + (eval-after-load "info-look" + '(let ((mode-value (assoc 'c-mode (assoc 'symbol info-lookup-alist)))) + (setcar (nthcdr 3 mode-value) + (cons '("(gmp)Function Index" nil "^ -.* " "\\>") + (nth 3 mode-value))))) + + +File: gmp.info, Node: Reporting Bugs, Next: Integer Functions, Prev: GMP Basics, Up: Top + +4 Reporting Bugs +**************** + +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 *Note +Known Build Problems::, or perhaps *Note Notes for Particular +Systems::. You may also want to check `http://gmplib.org/' for patches +for this release. + + Please include the following in any report, + + * The GMP version number, and if pre-packaged or patched then say so. + + * A test program that makes it possible for us to reproduce the bug. + Include instructions on how to run the program. + + * A description of what is wrong. If the results are incorrect, in + what way. If you get a crash, say so. + + * If you get a crash, include a stack backtrace from the debugger if + it's informative (`where' in `gdb', or `$C' in `adb'). + + * Please do not send core dumps, executables or `strace's. + + * The configuration options you used when building GMP, if any. + + * The name of the compiler and its version. For `gcc', get the + version with `gcc -v', otherwise perhaps `what `which cc`', or + similar. + + * The output from running `uname -a'. + + * The output from running `./config.guess', and from running + `./configfsf.guess' (might be the same). + + * If the bug is related to `configure', then the compressed contents + of `config.log'. + + * If the bug is related to an `asm' file not assembling, then the + contents of `config.m4' and the offending line or lines from the + temporary `mpn/tmp-.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: . + + 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. + + +File: gmp.info, Node: Integer Functions, Next: Rational Number Functions, Prev: Reporting Bugs, Up: Top + +5 Integer Functions +******************* + +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'. + +* Menu: + +* Initializing Integers:: +* Assigning Integers:: +* Simultaneous Integer Init & Assign:: +* Converting Integers:: +* Integer Arithmetic:: +* Integer Division:: +* Integer Exponentiation:: +* Integer Roots:: +* Number Theoretic Functions:: +* Integer Comparisons:: +* Integer Logic and Bit Fiddling:: +* I/O of Integers:: +* Integer Random Numbers:: +* Integer Import and Export:: +* Miscellaneous Integer Functions:: +* Integer Special Functions:: + + +File: gmp.info, Node: Initializing Integers, Next: Assigning Integers, Prev: Integer Functions, Up: Integer Functions + +5.1 Initialization Functions +============================ + +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. + + -- Function: void mpz_init (mpz_t X) + Initialize X, and set its value to 0. + + -- Function: void mpz_inits (mpz_t X, ...) + Initialize a NULL-terminated list of `mpz_t' variables, and set + their values to 0. + + -- Function: void mpz_init2 (mpz_t X, mp_bitcnt_t N) + Initialize X, with space for N-bit numbers, and set its value to 0. + Calling this function instead of `mpz_init' or `mpz_inits' is never + necessary; reallocation is handled automatically by GMP when + needed. + + N is only the initial space, X will grow automatically in the + normal way, if necessary, for subsequent values stored. + `mpz_init2' makes it possible to avoid such reallocations if a + maximum size is known in advance. + + -- Function: void mpz_clear (mpz_t X) + Free the space occupied by X. Call this function for all `mpz_t' + variables when you are done with them. + + -- Function: void mpz_clears (mpz_t X, ...) + Free the space occupied by a NULL-terminated list of `mpz_t' + variables. + + -- Function: void mpz_realloc2 (mpz_t X, mp_bitcnt_t N) + Change the space allocated for X to N bits. The value in X is + preserved if it fits, or is set to 0 if not. + + Calling this function is never necessary; reallocation is handled + automatically by GMP when needed. But 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. + + +File: gmp.info, Node: Assigning Integers, Next: Simultaneous Integer Init & Assign, Prev: Initializing Integers, Up: Integer Functions + +5.2 Assignment Functions +======================== + +These functions assign new values to already initialized integers +(*note Initializing Integers::). + + -- Function: 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) + Set the value of ROP from OP. + + `mpz_set_d', `mpz_set_q' and `mpz_set_f' truncate OP to make it an + integer. + + -- Function: int mpz_set_str (mpz_t ROP, char *STR, int BASE) + 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 62, or if BASE is 0, then the leading + characters are used: `0x' and `0X' for hexadecimal, `0b' and `0B' + for binary, `0' for octal, or decimal otherwise. + + For bases up to 36, case is ignored; upper-case and lower-case + letters have the same value. For bases 37 to 62, upper-case + letter represent the usual 10..35 while lower-case letter + represent 36..61. + + This function returns 0 if the entire string is a valid number in + base BASE. Otherwise it returns -1. + + -- Function: void mpz_swap (mpz_t ROP1, mpz_t ROP2) + Swap the values ROP1 and ROP2 efficiently. + + +File: gmp.info, Node: Simultaneous Integer Init & Assign, Next: Converting Integers, Prev: Assigning Integers, Up: Integer Functions + +5.3 Combined Initialization and Assignment Functions +==================================================== + +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! + + -- Function: 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) + Initialize ROP with limb space and set the initial numeric value + from OP. + + -- Function: int mpz_init_set_str (mpz_t ROP, char *STR, int BASE) + 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 `mpz_clear' for it.) + + +File: gmp.info, Node: Converting Integers, Next: Integer Arithmetic, Prev: Simultaneous Integer Init & Assign, Up: Integer Functions + +5.4 Conversion Functions +======================== + +This section describes functions for converting GMP integers to +standard C types. Functions for converting _to_ GMP integers are +described in *Note Assigning Integers:: and *Note I/O of Integers::. + + -- Function: unsigned long int mpz_get_ui (mpz_t OP) + Return the value of OP as an `unsigned long'. + + If OP is too big to fit an `unsigned long' then just the least + significant bits that do fit are returned. The sign of OP is + ignored, only the absolute value is used. + + -- Function: signed long int mpz_get_si (mpz_t OP) + 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 `signed long int', the returned + result is probably not very useful. To find out if the value will + fit, use the function `mpz_fits_slong_p'. + + -- Function: double mpz_get_d (mpz_t OP) + Convert OP to a `double', truncating if necessary (ie. rounding + towards zero). + + If the exponent from the conversion is too big, the result is + system dependent. An infinity is returned where available. A + hardware overflow trap may or may not occur. + + -- Function: double mpz_get_d_2exp (signed long int *EXP, mpz_t OP) + Convert OP to a `double', truncating if necessary (ie. rounding + towards zero), and returning the exponent separately. + + The return value is in the range 0.5<=abs(D)<1 and the exponent is + stored to `*EXP'. D * 2^EXP is the (truncated) OP value. If OP + is zero, the return is 0.0 and 0 is stored to `*EXP'. + + This is similar to the standard C `frexp' function (*note + Normalization Functions: (libc)Normalization Functions.). + + -- Function: char * mpz_get_str (char *STR, int BASE, mpz_t OP) + Convert OP to a string of digits in base BASE. The base argument + may vary from 2 to 62 or from -2 to -36. + + For BASE in the range 2..36, digits and lower-case letters are + used; for -2..-36, digits and upper-case letters are used; for + 37..62, digits, upper-case letters, and lower-case letters (in + that significance order) are used. + + If STR is `NULL', the result string is allocated using the current + allocation function (*note Custom Allocation::). The block will be + `strlen(str)+1' bytes, that being exactly enough for the string and + null-terminator. + + If STR is not `NULL', it should point to a block of storage large + enough for the result, that being `mpz_sizeinbase (OP, BASE) + 2'. + The two extra bytes are for a possible minus sign, and the + null-terminator. + + A pointer to the result string is returned, being either the + allocated block, or the given STR. + + +File: gmp.info, Node: Integer Arithmetic, Next: Integer Division, Prev: Converting Integers, Up: Integer Functions + +5.5 Arithmetic Functions +======================== + + -- Function: 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) + Set ROP to OP1 + OP2. + + -- Function: 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) + Set ROP to OP1 - OP2. + + -- Function: 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) + Set ROP to OP1 times OP2. + + -- Function: 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) + Set ROP to ROP + OP1 times OP2. + + -- Function: 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) + Set ROP to ROP - OP1 times OP2. + + -- Function: void mpz_mul_2exp (mpz_t ROP, mpz_t OP1, mp_bitcnt_t OP2) + Set ROP to OP1 times 2 raised to OP2. This operation can also be + defined as a left shift by OP2 bits. + + -- Function: void mpz_neg (mpz_t ROP, mpz_t OP) + Set ROP to -OP. + + -- Function: void mpz_abs (mpz_t ROP, mpz_t OP) + Set ROP to the absolute value of OP. + + +File: gmp.info, Node: Integer Division, Next: Integer Exponentiation, Prev: Integer Arithmetic, Up: Integer Functions + +5.6 Division Functions +====================== + +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. + + -- Function: 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, mp_bitcnt_t B) + -- Function: void mpz_cdiv_r_2exp (mpz_t R, mpz_t N, mp_bitcnt_t 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, mp_bitcnt_t B) + -- Function: void mpz_fdiv_r_2exp (mpz_t R, mpz_t N, mp_bitcnt_t 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, mp_bitcnt_t B) + -- Function: void mpz_tdiv_r_2exp (mpz_t R, mpz_t N, mp_bitcnt_t B) + + Divide N by D, forming a quotient Q and/or remainder R. For the + `2exp' functions, D=2^B. The rounding is in three styles, each + suiting different applications. + + * `cdiv' rounds Q up towards +infinity, and R will have the + opposite sign to D. The `c' stands for "ceil". + + * `fdiv' rounds Q down towards -infinity, and R will have the + same sign as D. The `f' stands for "floor". + + * `tdiv' rounds Q towards zero, and R will have the same sign + as N. The `t' stands for "truncate". + + In all cases Q and R will satisfy N=Q*D+R, and R will satisfy + 0<=abs(R) 0 and that MOD is odd. + + This function is designed to take the same time and have the same + cache access patterns for any two same-size arguments, assuming + that function arguments are placed at the same position and that + the machine state is identical upon function entry. This function + is intended for cryptographic purposes, where resilience to + side-channel attacks is desired. + + -- Function: 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) + Set ROP to BASE raised to EXP. The case 0^0 yields 1. + + +File: gmp.info, Node: Integer Roots, Next: Number Theoretic Functions, Prev: Integer Exponentiation, Up: Integer Functions + +5.8 Root Extraction Functions +============================= + + -- Function: int mpz_root (mpz_t ROP, mpz_t OP, unsigned long int N) + 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. + + -- Function: void mpz_rootrem (mpz_t ROOT, mpz_t REM, mpz_t U, + unsigned long int N) + Set ROOT to the truncated integer part of the Nth root of U. Set + REM to the remainder, U-ROOT**N. + + -- Function: void mpz_sqrt (mpz_t ROP, mpz_t OP) + Set ROP to the truncated integer part of the square root of OP. + + -- Function: void mpz_sqrtrem (mpz_t ROP1, mpz_t ROP2, mpz_t OP) + 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. + + -- Function: int mpz_perfect_power_p (mpz_t OP) + 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. + + -- Function: int mpz_perfect_square_p (mpz_t OP) + 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. + + +File: gmp.info, Node: Number Theoretic Functions, Next: Integer Comparisons, Prev: Integer Roots, Up: Integer Functions + +5.9 Number Theoretic Functions +============================== + + -- Function: int mpz_probab_prime_p (mpz_t N, int REPS) + 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. + + -- Function: void mpz_nextprime (mpz_t ROP, mpz_t OP) + 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. + + -- Function: void mpz_gcd (mpz_t ROP, mpz_t OP1, mpz_t OP2) + 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. + + -- Function: unsigned long int mpz_gcd_ui (mpz_t ROP, mpz_t OP1, + unsigned long int OP2) + 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 `unsigned long int', it + is returned. If the result does not fit, 0 is returned, and the + result is equal to the argument OP1. Note that the result will + always fit if OP2 is non-zero. + + -- Function: void mpz_gcdext (mpz_t G, mpz_t S, mpz_t T, mpz_t A, + mpz_t B) + 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. The value + in G is always positive, even if one or both of A and B are + negative. The values in S and T are chosen such that abs(S) <= + abs(B) and abs(T) <= abs(A). + + If T is `NULL' then that value is not computed. + + -- Function: 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) + 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. + + -- Function: int mpz_invert (mpz_t ROP, mpz_t OP1, mpz_t OP2) + 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. + + -- Function: int mpz_jacobi (mpz_t A, mpz_t B) + Calculate the Jacobi symbol (A/B). This is defined only for B odd. + + -- Function: int mpz_legendre (mpz_t A, mpz_t P) + 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. + + -- Function: int mpz_kronecker (mpz_t A, mpz_t B) + -- Function: int mpz_kronecker_si (mpz_t A, long B) + -- Function: int mpz_kronecker_ui (mpz_t A, unsigned long B) + -- Function: int mpz_si_kronecker (long A, mpz_t B) + -- Function: int mpz_ui_kronecker (unsigned long A, mpz_t B) + Calculate the Jacobi symbol (A/B) with the Kronecker extension + (a/2)=(2/a) when a odd, or (a/2)=0 when a even. + + When B is odd the Jacobi symbol and Kronecker symbol are + identical, so `mpz_kronecker_ui' etc can be used for mixed + precision Jacobi symbols too. + + For more information see Henri Cohen section 1.4.2 (*note + References::), or any number theory textbook. See also the + example program `demos/qcn.c' which uses `mpz_kronecker_ui'. + + -- Function: mp_bitcnt_t mpz_remove (mpz_t ROP, mpz_t OP, mpz_t F) + Remove all occurrences of the factor F from OP and store the + result in ROP. The return value is how many such occurrences were + removed. + + -- Function: void mpz_fac_ui (mpz_t ROP, unsigned long int OP) + Set ROP to OP!, the factorial of OP. + + -- Function: void mpz_bin_ui (mpz_t ROP, mpz_t N, unsigned long int K) + -- Function: void mpz_bin_uiui (mpz_t ROP, unsigned long int N, + unsigned long int K) + Compute the binomial coefficient N over K and store the result in + ROP. Negative values of N are supported by `mpz_bin_ui', using + the identity bin(-n,k) = (-1)^k * bin(n+k-1,k), see Knuth volume 1 + section 1.2.6 part G. + + -- Function: void mpz_fib_ui (mpz_t FN, unsigned long int N) + -- Function: void mpz_fib2_ui (mpz_t FN, mpz_t FNSUB1, unsigned long + int N) + `mpz_fib_ui' sets FN to to F[n], the N'th Fibonacci number. + `mpz_fib2_ui' sets FN to F[n], and FNSUB1 to F[n-1]. + + These functions are designed for calculating isolated Fibonacci + numbers. When a sequence of values is wanted it's best to start + with `mpz_fib2_ui' and iterate the defining F[n+1]=F[n]+F[n-1] or + similar. + + -- Function: void mpz_lucnum_ui (mpz_t LN, unsigned long int N) + -- Function: void mpz_lucnum2_ui (mpz_t LN, mpz_t LNSUB1, unsigned + long int N) + `mpz_lucnum_ui' sets LN to to L[n], the N'th Lucas number. + `mpz_lucnum2_ui' sets LN to L[n], and LNSUB1 to L[n-1]. + + These functions are designed for calculating isolated Lucas + numbers. When a sequence of values is wanted it's best to start + with `mpz_lucnum2_ui' and iterate the defining L[n+1]=L[n]+L[n-1] + or similar. + + The Fibonacci numbers and Lucas numbers are related sequences, so + it's never necessary to call both `mpz_fib2_ui' and + `mpz_lucnum2_ui'. The formulas for going from Fibonacci to Lucas + can be found in *Note Lucas Numbers Algorithm::, the reverse is + straightforward too. + + +File: gmp.info, Node: Integer Comparisons, Next: Integer Logic and Bit Fiddling, Prev: Number Theoretic Functions, Up: Integer Functions + +5.10 Comparison Functions +========================= + + -- Function: int mpz_cmp (mpz_t OP1, mpz_t OP2) + -- Function: int mpz_cmp_d (mpz_t OP1, double OP2) + -- Macro: int mpz_cmp_si (mpz_t OP1, signed long int OP2) + -- Macro: int mpz_cmp_ui (mpz_t OP1, unsigned long int OP2) + Compare OP1 and OP2. Return a positive value if OP1 > OP2, zero + if OP1 = OP2, or a negative value if OP1 < OP2. + + `mpz_cmp_ui' and `mpz_cmp_si' are macros and will evaluate their + arguments more than once. `mpz_cmp_d' can be called with an + infinity, but results are undefined for a NaN. + + -- Function: int mpz_cmpabs (mpz_t OP1, mpz_t OP2) + -- Function: int mpz_cmpabs_d (mpz_t OP1, double OP2) + -- Function: int mpz_cmpabs_ui (mpz_t OP1, unsigned long int OP2) + Compare the absolute values of OP1 and OP2. Return a positive + value if abs(OP1) > abs(OP2), zero if abs(OP1) = abs(OP2), or a + negative value if abs(OP1) < abs(OP2). + + `mpz_cmpabs_d' can be called with an infinity, but results are + undefined for a NaN. + + -- Macro: int mpz_sgn (mpz_t OP) + Return +1 if OP > 0, 0 if OP = 0, and -1 if OP < 0. + + This function is actually implemented as a macro. It evaluates + its argument multiple times. + + +File: gmp.info, Node: Integer Logic and Bit Fiddling, Next: I/O of Integers, Prev: Integer Comparisons, Up: Integer Functions + +5.11 Logical and Bit Manipulation Functions +=========================================== + +These functions behave as if twos complement arithmetic were used +(although sign-magnitude is the actual implementation). The least +significant bit is number 0. + + -- Function: void mpz_and (mpz_t ROP, mpz_t OP1, mpz_t OP2) + Set ROP to OP1 bitwise-and OP2. + + -- Function: void mpz_ior (mpz_t ROP, mpz_t OP1, mpz_t OP2) + Set ROP to OP1 bitwise inclusive-or OP2. + + -- Function: void mpz_xor (mpz_t ROP, mpz_t OP1, mpz_t OP2) + Set ROP to OP1 bitwise exclusive-or OP2. + + -- Function: void mpz_com (mpz_t ROP, mpz_t OP) + Set ROP to the one's complement of OP. + + -- Function: mp_bitcnt_t mpz_popcount (mpz_t OP) + If OP>=0, return the population count of OP, which is the number + of 1 bits in the binary representation. If OP<0, the number of 1s + is infinite, and the return value is the largest possible + `mp_bitcnt_t'. + + -- Function: mp_bitcnt_t mpz_hamdist (mpz_t OP1, mpz_t OP2) + If OP1 and OP2 are both >=0 or both <0, return the hamming + distance between the two operands, which is the number of bit + positions where OP1 and OP2 have different bit values. If one + operand is >=0 and the other <0 then the number of bits different + is infinite, and the return value is the largest possible + `mp_bitcnt_t'. + + -- Function: mp_bitcnt_t mpz_scan0 (mpz_t OP, mp_bitcnt_t STARTING_BIT) + -- Function: mp_bitcnt_t mpz_scan1 (mpz_t OP, mp_bitcnt_t STARTING_BIT) + Scan OP, starting from bit STARTING_BIT, towards more significant + bits, until the first 0 or 1 bit (respectively) is found. Return + the index of the found bit. + + If the bit at STARTING_BIT is already what's sought, then + STARTING_BIT is returned. + + If there's no bit found, then the largest possible `mp_bitcnt_t' is + returned. This will happen in `mpz_scan0' past the end of a + negative number, or `mpz_scan1' past the end of a nonnegative + number. + + -- Function: void mpz_setbit (mpz_t ROP, mp_bitcnt_t BIT_INDEX) + Set bit BIT_INDEX in ROP. + + -- Function: void mpz_clrbit (mpz_t ROP, mp_bitcnt_t BIT_INDEX) + Clear bit BIT_INDEX in ROP. + + -- Function: void mpz_combit (mpz_t ROP, mp_bitcnt_t BIT_INDEX) + Complement bit BIT_INDEX in ROP. + + -- Function: int mpz_tstbit (mpz_t OP, mp_bitcnt_t BIT_INDEX) + Test bit BIT_INDEX in OP and return 0 or 1 accordingly. + + +File: gmp.info, Node: I/O of Integers, Next: Integer Random Numbers, Prev: Integer Logic and Bit Fiddling, Up: Integer Functions + +5.12 Input and Output Functions +=============================== + +Functions that perform input from a stdio stream, and functions that +output to a stdio stream. Passing a `NULL' pointer for a STREAM +argument to any of these functions will make them read from `stdin' and +write to `stdout', respectively. + + When using any of these functions, it is a good idea to include +`stdio.h' before `gmp.h', since that will allow `gmp.h' to define +prototypes for these functions. + + -- Function: size_t mpz_out_str (FILE *STREAM, int BASE, mpz_t OP) + Output OP on stdio stream STREAM, as a string of digits in base + BASE. The base argument may vary from 2 to 62 or from -2 to -36. + + For BASE in the range 2..36, digits and lower-case letters are + used; for -2..-36, digits and upper-case letters are used; for + 37..62, digits, upper-case letters, and lower-case letters (in + that significance order) are used. + + Return the number of bytes written, or if an error occurred, + return 0. + + -- Function: size_t mpz_inp_str (mpz_t ROP, FILE *STREAM, int BASE) + Input a possibly white-space preceded string in base BASE from + stdio stream STREAM, and put the read integer in ROP. + + The BASE may vary from 2 to 62, or if BASE is 0, then the leading + characters are used: `0x' and `0X' for hexadecimal, `0b' and `0B' + for binary, `0' for octal, or decimal otherwise. + + For bases up to 36, case is ignored; upper-case and lower-case + letters have the same value. For bases 37 to 62, upper-case + letter represent the usual 10..35 while lower-case letter + represent 36..61. + + Return the number of bytes read, or if an error occurred, return 0. + + -- Function: size_t mpz_out_raw (FILE *STREAM, mpz_t OP) + Output OP on stdio stream STREAM, in raw binary format. The + integer is written in a portable format, with 4 bytes of size + information, and that many bytes of limbs. Both the size and the + limbs are written in decreasing significance order (i.e., in + big-endian). + + The output can be read with `mpz_inp_raw'. + + Return the number of bytes written, or if an error occurred, + return 0. + + The output of this can not be read by `mpz_inp_raw' from GMP 1, + because of changes necessary for compatibility between 32-bit and + 64-bit machines. + + -- Function: size_t mpz_inp_raw (mpz_t ROP, FILE *STREAM) + Input from stdio stream STREAM in the format written by + `mpz_out_raw', and put the result in ROP. Return the number of + bytes read, or if an error occurred, return 0. + + This routine can read the output from `mpz_out_raw' also from GMP + 1, in spite of changes necessary for compatibility between 32-bit + and 64-bit machines. + + +File: gmp.info, Node: Integer Random Numbers, Next: Integer Import and Export, Prev: I/O of Integers, Up: Integer Functions + +5.13 Random Number Functions +============================ + +The random number functions of GMP come in two groups; older function +that rely on a global state, and newer functions that accept a state +parameter that is read and modified. Please see the *Note Random +Number Functions:: for more information on how to use and not to use +random number functions. + + -- Function: void mpz_urandomb (mpz_t ROP, gmp_randstate_t STATE, + mp_bitcnt_t N) + Generate a uniformly distributed random integer in the range 0 to + 2^N-1, inclusive. + + The variable STATE must be initialized by calling one of the + `gmp_randinit' functions (*Note Random State Initialization::) + before invoking this function. + + -- Function: void mpz_urandomm (mpz_t ROP, gmp_randstate_t STATE, + mpz_t N) + Generate a uniform random integer in the range 0 to N-1, inclusive. + + The variable STATE must be initialized by calling one of the + `gmp_randinit' functions (*Note Random State Initialization::) + before invoking this function. + + -- Function: void mpz_rrandomb (mpz_t ROP, gmp_randstate_t STATE, + mp_bitcnt_t N) + Generate a random integer with long strings of zeros and ones in + the binary representation. Useful for testing functions and + algorithms, since this kind of random numbers have proven to be + more likely to trigger corner-case bugs. The random number will + be in the range 0 to 2^N-1, inclusive. + + The variable STATE must be initialized by calling one of the + `gmp_randinit' functions (*Note Random State Initialization::) + before invoking this function. + + -- Function: void mpz_random (mpz_t ROP, mp_size_t MAX_SIZE) + Generate a random integer of at most MAX_SIZE limbs. The generated + random number doesn't satisfy any particular requirements of + randomness. Negative random numbers are generated when MAX_SIZE + is negative. + + This function is obsolete. Use `mpz_urandomb' or `mpz_urandomm' + instead. + + -- Function: void mpz_random2 (mpz_t ROP, mp_size_t MAX_SIZE) + Generate a random integer of at most MAX_SIZE limbs, with long + strings of zeros and ones in the binary representation. Useful + for testing functions and algorithms, since this kind of random + numbers have proven to be more likely to trigger corner-case bugs. + Negative random numbers are generated when MAX_SIZE is negative. + + This function is obsolete. Use `mpz_rrandomb' instead. + + +File: gmp.info, Node: Integer Import and Export, Next: Miscellaneous Integer Functions, Prev: Integer Random Numbers, Up: Integer Functions + +5.14 Integer Import and Export +============================== + +`mpz_t' variables can be converted to and from arbitrary words of binary +data with the following functions. + + -- Function: void mpz_import (mpz_t ROP, size_t COUNT, int ORDER, + size_t SIZE, int ENDIAN, size_t NAILS, const void *OP) + Set ROP from an array of word data at OP. + + The parameters specify the format of the data. COUNT many words + are read, each SIZE bytes. ORDER can be 1 for most significant + word first or -1 for least significant first. Within each word + ENDIAN can be 1 for most significant byte first, -1 for least + significant first, or 0 for the native endianness of the host CPU. + The most significant NAILS bits of each word are skipped, this + can be 0 to use the full words. + + There is no sign taken from the data, ROP will simply be a positive + integer. An application can handle any sign itself, and apply it + for instance with `mpz_neg'. + + There are no data alignment restrictions on OP, any address is + allowed. + + Here's an example converting an array of `unsigned long' data, most + significant element first, and host byte order within each value. + + unsigned long a[20]; + /* Initialize Z and A */ + mpz_import (z, 20, 1, sizeof(a[0]), 0, 0, a); + + This example assumes the full `sizeof' bytes are used for data in + the given type, which is usually true, and certainly true for + `unsigned long' everywhere we know of. However on Cray vector + systems it may be noted that `short' and `int' are always stored + in 8 bytes (and with `sizeof' indicating that) but use only 32 or + 46 bits. The NAILS feature can account for this, by passing for + instance `8*sizeof(int)-INT_BIT'. + + -- Function: void * mpz_export (void *ROP, size_t *COUNTP, int ORDER, + size_t SIZE, int ENDIAN, size_t NAILS, mpz_t OP) + Fill ROP with word data from OP. + + The parameters specify the format of the data produced. Each word + will be SIZE bytes and ORDER can be 1 for most significant word + first or -1 for least significant first. Within each word ENDIAN + can be 1 for most significant byte first, -1 for least significant + first, or 0 for the native endianness of the host CPU. The most + significant NAILS bits of each word are unused and set to zero, + this can be 0 to produce full words. + + The number of words produced is written to `*COUNTP', or COUNTP + can be `NULL' to discard the count. ROP must have enough space + for the data, or if ROP is `NULL' then a result array of the + necessary size is allocated using the current GMP allocation + function (*note Custom Allocation::). In either case the return + value is the destination used, either ROP or the allocated block. + + If OP is non-zero then the most significant word produced will be + non-zero. If OP is zero then the count returned will be zero and + nothing written to ROP. If ROP is `NULL' in this case, no block + is allocated, just `NULL' is returned. + + The sign of OP is ignored, just the absolute value is exported. An + application can use `mpz_sgn' to get the sign and handle it as + desired. (*note Integer Comparisons::) + + There are no data alignment restrictions on ROP, any address is + allowed. + + When an application is allocating space itself the required size + can be determined with a calculation like the following. Since + `mpz_sizeinbase' always returns at least 1, `count' here will be + at least one, which avoids any portability problems with + `malloc(0)', though if `z' is zero no space at all is actually + needed (or written). + + numb = 8*size - nail; + count = (mpz_sizeinbase (z, 2) + numb-1) / numb; + p = malloc (count * size); + + +File: gmp.info, Node: Miscellaneous Integer Functions, Next: Integer Special Functions, Prev: Integer Import and Export, Up: Integer Functions + +5.15 Miscellaneous Functions +============================ + + -- Function: int mpz_fits_ulong_p (mpz_t OP) + -- Function: int mpz_fits_slong_p (mpz_t OP) + -- Function: int mpz_fits_uint_p (mpz_t OP) + -- Function: int mpz_fits_sint_p (mpz_t OP) + -- Function: int mpz_fits_ushort_p (mpz_t OP) + -- Function: int mpz_fits_sshort_p (mpz_t OP) + Return non-zero iff the value of OP fits in an `unsigned long int', + `signed long int', `unsigned int', `signed int', `unsigned short + int', or `signed short int', respectively. Otherwise, return zero. + + -- Macro: int mpz_odd_p (mpz_t OP) + -- Macro: int mpz_even_p (mpz_t OP) + Determine whether OP is odd or even, respectively. Return + non-zero if yes, zero if no. These macros evaluate their argument + more than once. + + -- Function: size_t mpz_sizeinbase (mpz_t OP, int BASE) + Return the size of OP measured in number of digits in the given + BASE. BASE can vary from 2 to 62. The sign of OP is ignored, + just the absolute value is used. The result will be either exact + or 1 too big. If BASE is a power of 2, the result is always + exact. If OP is zero the return value is always 1. + + This function can be used to determine the space required when + converting OP to a string. The right amount of allocation is + normally two more than the value returned by `mpz_sizeinbase', one + extra for a minus sign and one for the null-terminator. + + It will be noted that `mpz_sizeinbase(OP,2)' can be used to locate + the most significant 1 bit in OP, counting from 1. (Unlike the + bitwise functions which start from 0, *Note Logical and Bit + Manipulation Functions: Integer Logic and Bit Fiddling.) + + +File: gmp.info, Node: Integer Special Functions, Prev: Miscellaneous Integer Functions, Up: Integer Functions + +5.16 Special Functions +====================== + +The functions in this section are for various special purposes. Most +applications will not need them. + + -- Function: void mpz_array_init (mpz_t INTEGER_ARRAY, mp_size_t + ARRAY_SIZE, mp_size_t FIXED_NUM_BITS) + This is a special type of initialization. *Fixed* space of + FIXED_NUM_BITS is allocated to each of the ARRAY_SIZE integers in + INTEGER_ARRAY. There is no way to free the storage allocated by + this function. Don't call `mpz_clear'! + + The INTEGER_ARRAY parameter is the first `mpz_t' in the array. For + example, + + mpz_t arr[20000]; + mpz_array_init (arr[0], 20000, 512); + + This function is only intended for programs that create a large + number of integers and need to reduce memory usage by avoiding the + overheads of allocating and reallocating lots of small blocks. In + normal programs this function is not recommended. + + The space allocated to each integer by this function will not be + automatically increased, unlike the normal `mpz_init', so an + application must ensure it is sufficient for any value stored. + The following space requirements apply to various routines, + + * `mpz_abs', `mpz_neg', `mpz_set', `mpz_set_si' and + `mpz_set_ui' need room for the value they store. + + * `mpz_add', `mpz_add_ui', `mpz_sub' and `mpz_sub_ui' need room + for the larger of the two operands, plus an extra + `mp_bits_per_limb'. + + * `mpz_mul', `mpz_mul_ui' and `mpz_mul_ui' need room for the sum + of the number of bits in their operands, but each rounded up + to a multiple of `mp_bits_per_limb'. + + * `mpz_swap' can be used between two array variables, but not + between an array and a normal variable. + + For other functions, or if in doubt, the suggestion is to + calculate in a regular `mpz_init' variable and copy the result to + an array variable with `mpz_set'. + + -- Function: void * _mpz_realloc (mpz_t INTEGER, mp_size_t NEW_ALLOC) + 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. + + `mpz_realloc2' is the preferred way to accomplish allocation + changes like this. `mpz_realloc2' and `_mpz_realloc' are the same + except that `_mpz_realloc' takes its size in limbs. + + -- Function: mp_limb_t mpz_getlimbn (mpz_t OP, mp_size_t N) + 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. + + `mpz_size' can be used to find how many limbs make up OP. + `mpz_getlimbn' returns zero if N is outside the range 0 to + `mpz_size(OP)-1'. + + -- Function: size_t mpz_size (mpz_t OP) + Return the size of OP measured in number of limbs. If OP is zero, + the returned value will be zero. + + +File: gmp.info, Node: Rational Number Functions, Next: Floating-point Functions, Prev: Integer Functions, Up: Top + +6 Rational Number Functions +*************************** + +This chapter describes the GMP functions for performing arithmetic on +rational numbers. These functions start with the prefix `mpq_'. + + Rational numbers are stored in objects of type `mpq_t'. + + All rational arithmetic functions assume operands have a canonical +form, and canonicalize their result. The canonical from means that the +denominator and the numerator have no common factors, and that the +denominator is positive. Zero has the unique representation 0/1. + + Pure assignment functions do not canonicalize the assigned variable. +It is the responsibility of the user to canonicalize the assigned +variable before any arithmetic operations are performed on that +variable. + + -- Function: void mpq_canonicalize (mpq_t OP) + Remove any factors that are common to the numerator and + denominator of OP, and make the denominator positive. + +* Menu: + +* Initializing Rationals:: +* Rational Conversions:: +* Rational Arithmetic:: +* Comparing Rationals:: +* Applying Integer Functions:: +* I/O of Rationals:: + + +File: gmp.info, Node: Initializing Rationals, Next: Rational Conversions, Prev: Rational Number Functions, Up: Rational Number Functions + +6.1 Initialization and Assignment Functions +=========================================== + + -- Function: void mpq_init (mpq_t X) + Initialize X and set it to 0/1. Each variable should normally + only be initialized once, or at least cleared out (using the + function `mpq_clear') between each initialization. + + -- Function: void mpq_inits (mpq_t X, ...) + Initialize a NULL-terminated list of `mpq_t' variables, and set + their values to 0/1. + + -- Function: void mpq_clear (mpq_t X) + Free the space occupied by X. Make sure to call this function for + all `mpq_t' variables when you are done with them. + + -- Function: void mpq_clears (mpq_t X, ...) + Free the space occupied by a NULL-terminated list of `mpq_t' + variables. + + -- Function: void mpq_set (mpq_t ROP, mpq_t OP) + -- Function: void mpq_set_z (mpq_t ROP, mpz_t OP) + Assign ROP from OP. + + -- Function: void mpq_set_ui (mpq_t ROP, unsigned long int OP1, + unsigned long int OP2) + -- Function: void mpq_set_si (mpq_t ROP, signed long int OP1, unsigned + long int OP2) + Set the value of ROP to OP1/OP2. Note that if OP1 and OP2 have + common factors, ROP has to be passed to `mpq_canonicalize' before + any operations are performed on ROP. + + -- Function: int mpq_set_str (mpq_t ROP, char *STR, int BASE) + Set ROP from a null-terminated string STR in the given BASE. + + The string can be an integer like "41" or a fraction like + "41/152". The fraction must be in canonical form (*note Rational + Number Functions::), or if not then `mpq_canonicalize' must be + called. + + The numerator and optional denominator are parsed the same as in + `mpz_set_str' (*note Assigning Integers::). White space is + allowed in the string, and is simply ignored. The BASE can vary + from 2 to 62, or if BASE is 0 then the leading characters are + used: `0x' or `0X' for hex, `0b' or `0B' for binary, `0' for + octal, or decimal otherwise. Note that this is done separately + for the numerator and denominator, so for instance `0xEF/100' is + 239/100, whereas `0xEF/0x100' is 239/256. + + The return value is 0 if the entire string is a valid number, or + -1 if not. + + -- Function: void mpq_swap (mpq_t ROP1, mpq_t ROP2) + Swap the values ROP1 and ROP2 efficiently. + + +File: gmp.info, Node: Rational Conversions, Next: Rational Arithmetic, Prev: Initializing Rationals, Up: Rational Number Functions + +6.2 Conversion Functions +======================== + + -- Function: double mpq_get_d (mpq_t OP) + Convert OP to a `double', truncating if necessary (ie. rounding + towards zero). + + If the exponent from the conversion is too big or too small to fit + a `double' then the result is system dependent. For too big an + infinity is returned when available. For too small 0.0 is + normally returned. Hardware overflow, underflow and denorm traps + may or may not occur. + + -- Function: void mpq_set_d (mpq_t ROP, double OP) + -- Function: void mpq_set_f (mpq_t ROP, mpf_t OP) + Set ROP to the value of OP. There is no rounding, this conversion + is exact. + + -- Function: char * mpq_get_str (char *STR, int BASE, mpq_t OP) + Convert OP to a string of digits in base BASE. The base may vary + from 2 to 36. The string will be of the form `num/den', or if the + denominator is 1 then just `num'. + + If STR is `NULL', the result string is allocated using the current + allocation function (*note Custom Allocation::). The block will be + `strlen(str)+1' bytes, that being exactly enough for the string and + null-terminator. + + If STR is not `NULL', it should point to a block of storage large + enough for the result, that being + + mpz_sizeinbase (mpq_numref(OP), BASE) + + mpz_sizeinbase (mpq_denref(OP), BASE) + 3 + + The three extra bytes are for a possible minus sign, possible + slash, and the null-terminator. + + A pointer to the result string is returned, being either the + allocated block, or the given STR. + + +File: gmp.info, Node: Rational Arithmetic, Next: Comparing Rationals, Prev: Rational Conversions, Up: Rational Number Functions + +6.3 Arithmetic Functions +======================== + + -- Function: void mpq_add (mpq_t SUM, mpq_t ADDEND1, mpq_t ADDEND2) + Set SUM to ADDEND1 + ADDEND2. + + -- Function: void mpq_sub (mpq_t DIFFERENCE, mpq_t MINUEND, mpq_t + SUBTRAHEND) + Set DIFFERENCE to MINUEND - SUBTRAHEND. + + -- Function: void mpq_mul (mpq_t PRODUCT, mpq_t MULTIPLIER, mpq_t + MULTIPLICAND) + Set PRODUCT to MULTIPLIER times MULTIPLICAND. + + -- Function: void mpq_mul_2exp (mpq_t ROP, mpq_t OP1, mp_bitcnt_t OP2) + Set ROP to OP1 times 2 raised to OP2. + + -- Function: void mpq_div (mpq_t QUOTIENT, mpq_t DIVIDEND, mpq_t + DIVISOR) + Set QUOTIENT to DIVIDEND/DIVISOR. + + -- Function: void mpq_div_2exp (mpq_t ROP, mpq_t OP1, mp_bitcnt_t OP2) + Set ROP to OP1 divided by 2 raised to OP2. + + -- Function: void mpq_neg (mpq_t NEGATED_OPERAND, mpq_t OPERAND) + Set NEGATED_OPERAND to -OPERAND. + + -- Function: void mpq_abs (mpq_t ROP, mpq_t OP) + Set ROP to the absolute value of OP. + + -- Function: void mpq_inv (mpq_t INVERTED_NUMBER, mpq_t NUMBER) + Set INVERTED_NUMBER to 1/NUMBER. If the new denominator is zero, + this routine will divide by zero. + + +File: gmp.info, Node: Comparing Rationals, Next: Applying Integer Functions, Prev: Rational Arithmetic, Up: Rational Number Functions + +6.4 Comparison Functions +======================== + + -- Function: int mpq_cmp (mpq_t OP1, mpq_t OP2) + Compare OP1 and OP2. Return a positive value if OP1 > OP2, zero + if OP1 = OP2, and a negative value if OP1 < OP2. + + To determine if two rationals are equal, `mpq_equal' is faster than + `mpq_cmp'. + + -- Macro: int mpq_cmp_ui (mpq_t OP1, unsigned long int NUM2, unsigned + long int DEN2) + -- Macro: int mpq_cmp_si (mpq_t OP1, long int NUM2, unsigned long int + DEN2) + Compare OP1 and NUM2/DEN2. Return a positive value if OP1 > + NUM2/DEN2, zero if OP1 = NUM2/DEN2, and a negative value if OP1 < + NUM2/DEN2. + + NUM2 and DEN2 are allowed to have common factors. + + These functions are implemented as a macros and evaluate their + arguments multiple times. + + -- Macro: int mpq_sgn (mpq_t OP) + Return +1 if OP > 0, 0 if OP = 0, and -1 if OP < 0. + + This function is actually implemented as a macro. It evaluates its + arguments multiple times. + + -- Function: int mpq_equal (mpq_t OP1, mpq_t OP2) + Return non-zero if OP1 and OP2 are equal, zero if they are + non-equal. Although `mpq_cmp' can be used for the same purpose, + this function is much faster. + + +File: gmp.info, Node: Applying Integer Functions, Next: I/O of Rationals, Prev: Comparing Rationals, Up: Rational Number Functions + +6.5 Applying Integer Functions to Rationals +=========================================== + +The set of `mpq' functions is quite small. In particular, there are few +functions for either input or output. The following functions give +direct access to the numerator and denominator of an `mpq_t'. + + Note that if an assignment to the numerator and/or denominator could +take an `mpq_t' out of the canonical form described at the start of +this chapter (*note Rational Number Functions::) then +`mpq_canonicalize' must be called before any other `mpq' functions are +applied to that `mpq_t'. + + -- Macro: mpz_t mpq_numref (mpq_t OP) + -- Macro: mpz_t mpq_denref (mpq_t OP) + Return a reference to the numerator and denominator of OP, + respectively. The `mpz' functions can be used on the result of + these macros. + + -- Function: void mpq_get_num (mpz_t NUMERATOR, mpq_t RATIONAL) + -- Function: void mpq_get_den (mpz_t DENOMINATOR, mpq_t RATIONAL) + -- Function: void mpq_set_num (mpq_t RATIONAL, mpz_t NUMERATOR) + -- Function: void mpq_set_den (mpq_t RATIONAL, mpz_t DENOMINATOR) + Get or set the numerator or denominator of a rational. These + functions are equivalent to calling `mpz_set' with an appropriate + `mpq_numref' or `mpq_denref'. Direct use of `mpq_numref' or + `mpq_denref' is recommended instead of these functions. + + +File: gmp.info, Node: I/O of Rationals, Prev: Applying Integer Functions, Up: Rational Number Functions + +6.6 Input and Output Functions +============================== + +When using any of these functions, it's a good idea to include `stdio.h' +before `gmp.h', since that will allow `gmp.h' to define prototypes for +these functions. + + Passing a `NULL' pointer for a STREAM argument to any of these +functions will make them read from `stdin' and write to `stdout', +respectively. + + -- Function: size_t mpq_out_str (FILE *STREAM, int BASE, mpq_t OP) + Output OP on stdio stream STREAM, as a string of digits in base + BASE. The base may vary from 2 to 36. Output is in the form + `num/den' or if the denominator is 1 then just `num'. + + Return the number of bytes written, or if an error occurred, + return 0. + + -- Function: size_t mpq_inp_str (mpq_t ROP, FILE *STREAM, int BASE) + Read a string of digits from STREAM and convert them to a rational + in ROP. Any initial white-space characters are read and + discarded. Return the number of characters read (including white + space), or 0 if a rational could not be read. + + The input can be a fraction like `17/63' or just an integer like + `123'. Reading stops at the first character not in this form, and + white space is not permitted within the string. If the input + might not be in canonical form, then `mpq_canonicalize' must be + called (*note Rational Number Functions::). + + The BASE can be between 2 and 36, or can be 0 in which case the + leading characters of the string determine the base, `0x' or `0X' + for hexadecimal, `0' for octal, or decimal otherwise. The leading + characters are examined separately for the numerator and + denominator of a fraction, so for instance `0x10/11' is 16/11, + whereas `0x10/0x11' is 16/17. + + +File: gmp.info, Node: Floating-point Functions, Next: Low-level Functions, Prev: Rational Number Functions, Up: Top + +7 Floating-point Functions +************************** + +GMP floating point numbers are stored in objects of type `mpf_t' and +functions operating on them have an `mpf_' prefix. + + The mantissa of each float has a user-selectable precision, limited +only by available memory. Each variable has its own precision, and +that can be increased or decreased at any time. + + The exponent of each float is a fixed precision, one machine word on +most systems. In the current implementation the exponent is a count of +limbs, so for example on a 32-bit system this means a range of roughly +2^-68719476768 to 2^68719476736, or on a 64-bit system this will be +greater. Note however `mpf_get_str' can only return an exponent which +fits an `mp_exp_t' and currently `mpf_set_str' doesn't accept exponents +bigger than a `long'. + + Each variable keeps a size for the mantissa data actually in use. +This means that if a float is exactly represented in only a few bits +then only those bits will be used in a calculation, even if the +selected precision is high. + + All calculations are performed to the precision of the destination +variable. Each function is defined to calculate with "infinite +precision" followed by a truncation to the destination precision, but +of course the work done is only what's needed to determine a result +under that definition. + + The precision selected for a variable is a minimum value, GMP may +increase it a little to facilitate efficient calculation. Currently +this means rounding up to a whole limb, and then sometimes having a +further partial limb, depending on the high limb of the mantissa. But +applications shouldn't be concerned by such details. + + The mantissa in stored in binary, as might be imagined from the fact +precisions are expressed in bits. One consequence of this is that +decimal fractions like 0.1 cannot be represented exactly. The same is +true of plain IEEE `double' floats. This makes both highly unsuitable +for calculations involving money or other values that should be exact +decimal fractions. (Suitably scaled integers, or perhaps rationals, +are better choices.) + + `mpf' functions and variables have no special notion of infinity or +not-a-number, and applications must take care not to overflow the +exponent or results will be unpredictable. This might change in a +future release. + + Note that the `mpf' functions are _not_ intended as a smooth +extension to IEEE P754 arithmetic. In particular results obtained on +one computer often differ from the results on a computer with a +different word size. + +* Menu: + +* Initializing Floats:: +* Assigning Floats:: +* Simultaneous Float Init & Assign:: +* Converting Floats:: +* Float Arithmetic:: +* Float Comparison:: +* I/O of Floats:: +* Miscellaneous Float Functions:: + + +File: gmp.info, Node: Initializing Floats, Next: Assigning Floats, Prev: Floating-point Functions, Up: Floating-point Functions + +7.1 Initialization Functions +============================ + + -- Function: void mpf_set_default_prec (mp_bitcnt_t PREC) + Set the default precision to be *at least* PREC bits. All + subsequent calls to `mpf_init' will use this precision, but + previously initialized variables are unaffected. + + -- Function: mp_bitcnt_t mpf_get_default_prec (void) + Return the default precision actually used. + + An `mpf_t' object must be initialized before storing the first value +in it. The functions `mpf_init' and `mpf_init2' are used for that +purpose. + + -- Function: void mpf_init (mpf_t X) + Initialize X to 0. Normally, a variable should be initialized + once only or at least be cleared, using `mpf_clear', between + initializations. The precision of X is undefined unless a default + precision has already been established by a call to + `mpf_set_default_prec'. + + -- Function: void mpf_init2 (mpf_t X, mp_bitcnt_t PREC) + Initialize X to 0 and set its precision to be *at least* PREC + bits. Normally, a variable should be initialized once only or at + least be cleared, using `mpf_clear', between initializations. + + -- Function: void mpf_inits (mpf_t X, ...) + Initialize a NULL-terminated list of `mpf_t' variables, and set + their values to 0. The precision of the initialized variables is + undefined unless a default precision has already been established + by a call to `mpf_set_default_prec'. + + -- Function: void mpf_clear (mpf_t X) + Free the space occupied by X. Make sure to call this function for + all `mpf_t' variables when you are done with them. + + -- Function: void mpf_clears (mpf_t X, ...) + Free the space occupied by a NULL-terminated list of `mpf_t' + variables. + + Here is an example on how to initialize floating-point variables: + { + mpf_t x, y; + mpf_init (x); /* use default precision */ + mpf_init2 (y, 256); /* precision _at least_ 256 bits */ + ... + /* Unless the program is about to exit, do ... */ + mpf_clear (x); + mpf_clear (y); + } + + The following three functions are useful for changing the precision +during a calculation. A typical use would be for adjusting the +precision gradually in iterative algorithms like Newton-Raphson, making +the computation precision closely match the actual accurate part of the +numbers. + + -- Function: mp_bitcnt_t mpf_get_prec (mpf_t OP) + Return the current precision of OP, in bits. + + -- Function: void mpf_set_prec (mpf_t ROP, mp_bitcnt_t PREC) + Set the precision of ROP to be *at least* PREC bits. The value in + ROP will be truncated to the new precision. + + This function requires a call to `realloc', and so should not be + used in a tight loop. + + -- Function: void mpf_set_prec_raw (mpf_t ROP, mp_bitcnt_t PREC) + Set the precision of ROP to be *at least* PREC bits, without + changing the memory allocated. + + PREC must be no more than the allocated precision for ROP, that + being the precision when ROP was initialized, or in the most recent + `mpf_set_prec'. + + The value in ROP is unchanged, and in particular if it had a higher + precision than PREC it will retain that higher precision. New + values written to ROP will use the new PREC. + + Before calling `mpf_clear' or the full `mpf_set_prec', another + `mpf_set_prec_raw' call must be made to restore ROP to its original + allocated precision. Failing to do so will have unpredictable + results. + + `mpf_get_prec' can be used before `mpf_set_prec_raw' to get the + original allocated precision. After `mpf_set_prec_raw' it + reflects the PREC value set. + + `mpf_set_prec_raw' is an efficient way to use an `mpf_t' variable + at different precisions during a calculation, perhaps to gradually + increase precision in an iteration, or just to use various + different precisions for different purposes during a calculation. + + +File: gmp.info, Node: Assigning Floats, Next: Simultaneous Float Init & Assign, Prev: Initializing Floats, Up: Floating-point Functions + +7.2 Assignment Functions +======================== + +These functions assign new values to already initialized floats (*note +Initializing Floats::). + + -- Function: void mpf_set (mpf_t ROP, mpf_t OP) + -- Function: void mpf_set_ui (mpf_t ROP, unsigned long int OP) + -- Function: void mpf_set_si (mpf_t ROP, signed long int OP) + -- Function: void mpf_set_d (mpf_t ROP, double OP) + -- Function: void mpf_set_z (mpf_t ROP, mpz_t OP) + -- Function: void mpf_set_q (mpf_t ROP, mpq_t OP) + Set the value of ROP from OP. + + -- Function: int mpf_set_str (mpf_t ROP, char *STR, int BASE) + Set the value of ROP from the string in STR. The string is of the + form `M@N' or, if the base is 10 or less, alternatively `MeN'. + `M' is the mantissa and `N' is the exponent. The mantissa is + always in the specified base. The exponent is either in the + specified base or, if BASE is negative, in decimal. The decimal + point expected is taken from the current locale, on systems + providing `localeconv'. + + The argument BASE may be in the ranges 2 to 62, or -62 to -2. + Negative values are used to specify that the exponent is in + decimal. + + For bases up to 36, case is ignored; upper-case and lower-case + letters have the same value; for bases 37 to 62, upper-case letter + represent the usual 10..35 while lower-case letter represent + 36..61. + + Unlike the corresponding `mpz' function, the base will not be + determined from the leading characters of the string if BASE is 0. + This is so that numbers like `0.23' are not interpreted as octal. + + White space is allowed in the string, and is simply ignored. + [This is not really true; white-space is ignored in the beginning + of the string and within the mantissa, but not in other places, + such as after a minus sign or in the exponent. 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. Please tell us your opinion about this change. Do you + really want it to accept "3 14" as meaning 314 as it does now?] + + This function returns 0 if the entire string is a valid number in + base BASE. Otherwise it returns -1. + + -- Function: void mpf_swap (mpf_t ROP1, mpf_t ROP2) + Swap ROP1 and ROP2 efficiently. Both the values and the + precisions of the two variables are swapped. + + +File: gmp.info, Node: Simultaneous Float Init & Assign, Next: Converting Floats, Prev: Assigning Floats, Up: Floating-point Functions + +7.3 Combined Initialization and Assignment Functions +==================================================== + +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 `mpf_init_set...' + + Once the float has been initialized by any of the `mpf_init_set...' +functions, it can be used as the source or destination operand for the +ordinary float functions. Don't use an initialize-and-set function on +a variable already initialized! + + -- Function: void mpf_init_set (mpf_t ROP, mpf_t OP) + -- Function: void mpf_init_set_ui (mpf_t ROP, unsigned long int OP) + -- Function: void mpf_init_set_si (mpf_t ROP, signed long int OP) + -- Function: void mpf_init_set_d (mpf_t ROP, double OP) + Initialize ROP and set its value from OP. + + The precision of ROP will be taken from the active default + precision, as set by `mpf_set_default_prec'. + + -- Function: int mpf_init_set_str (mpf_t ROP, char *STR, int BASE) + Initialize ROP and set its value from the string in STR. See + `mpf_set_str' above for details on the assignment operation. + + Note that ROP is initialized even if an error occurs. (I.e., you + have to call `mpf_clear' for it.) + + The precision of ROP will be taken from the active default + precision, as set by `mpf_set_default_prec'. + + +File: gmp.info, Node: Converting Floats, Next: Float Arithmetic, Prev: Simultaneous Float Init & Assign, Up: Floating-point Functions + +7.4 Conversion Functions +======================== + + -- Function: double mpf_get_d (mpf_t OP) + Convert OP to a `double', truncating if necessary (ie. rounding + towards zero). + + If the exponent in OP is too big or too small to fit a `double' + then the result is system dependent. For too big an infinity is + returned when available. For too small 0.0 is normally returned. + Hardware overflow, underflow and denorm traps may or may not occur. + + -- Function: double mpf_get_d_2exp (signed long int *EXP, mpf_t OP) + Convert OP to a `double', truncating if necessary (ie. rounding + towards zero), and with an exponent returned separately. + + The return value is in the range 0.5<=abs(D)<1 and the exponent is + stored to `*EXP'. D * 2^EXP is the (truncated) OP value. If OP + is zero, the return is 0.0 and 0 is stored to `*EXP'. + + This is similar to the standard C `frexp' function (*note + Normalization Functions: (libc)Normalization Functions.). + + -- Function: long mpf_get_si (mpf_t OP) + -- Function: unsigned long mpf_get_ui (mpf_t OP) + Convert OP to a `long' or `unsigned long', truncating any fraction + part. If OP is too big for the return type, the result is + undefined. + + See also `mpf_fits_slong_p' and `mpf_fits_ulong_p' (*note + Miscellaneous Float Functions::). + + -- Function: char * mpf_get_str (char *STR, mp_exp_t *EXPPTR, int + BASE, size_t N_DIGITS, mpf_t OP) + Convert OP to a string of digits in base BASE. The base argument + may vary from 2 to 62 or from -2 to -36. Up to N_DIGITS digits + will be generated. Trailing zeros are not returned. No more + digits than can be accurately represented by OP are ever + generated. If N_DIGITS is 0 then that accurate maximum number of + digits are generated. + + For BASE in the range 2..36, digits and lower-case letters are + used; for -2..-36, digits and upper-case letters are used; for + 37..62, digits, upper-case letters, and lower-case letters (in + that significance order) are used. + + If STR is `NULL', the result string is allocated using the current + allocation function (*note Custom Allocation::). The block will be + `strlen(str)+1' bytes, that being exactly enough for the string and + null-terminator. + + If STR is not `NULL', it should point to a block of N_DIGITS + 2 + bytes, that being enough for the mantissa, a possible minus sign, + and a null-terminator. When N_DIGITS is 0 to get all significant + digits, an application won't be able to know the space required, + and STR should be `NULL' in that case. + + The generated string is a fraction, with an implicit radix point + immediately to the left of the first digit. The applicable + exponent is written through the EXPPTR pointer. For example, the + number 3.1416 would be returned as string "31416" and exponent 1. + + When OP is zero, an empty string is produced and the exponent + returned is 0. + + A pointer to the result string is returned, being either the + allocated block or the given STR. + + +File: gmp.info, Node: Float Arithmetic, Next: Float Comparison, Prev: Converting Floats, Up: Floating-point Functions + +7.5 Arithmetic Functions +======================== + + -- Function: void mpf_add (mpf_t ROP, mpf_t OP1, mpf_t OP2) + -- Function: void mpf_add_ui (mpf_t ROP, mpf_t OP1, unsigned long int + OP2) + Set ROP to OP1 + OP2. + + -- Function: void mpf_sub (mpf_t ROP, mpf_t OP1, mpf_t OP2) + -- Function: void mpf_ui_sub (mpf_t ROP, unsigned long int OP1, mpf_t + OP2) + -- Function: void mpf_sub_ui (mpf_t ROP, mpf_t OP1, unsigned long int + OP2) + Set ROP to OP1 - OP2. + + -- Function: void mpf_mul (mpf_t ROP, mpf_t OP1, mpf_t OP2) + -- Function: void mpf_mul_ui (mpf_t ROP, mpf_t OP1, unsigned long int + OP2) + Set ROP to OP1 times OP2. + + Division is undefined if the divisor is zero, and passing a zero +divisor to the divide functions will make these functions intentionally +divide by zero. This lets the user handle arithmetic exceptions in +these functions in the same manner as other arithmetic exceptions. + + -- Function: void mpf_div (mpf_t ROP, mpf_t OP1, mpf_t OP2) + -- Function: void mpf_ui_div (mpf_t ROP, unsigned long int OP1, mpf_t + OP2) + -- Function: void mpf_div_ui (mpf_t ROP, mpf_t OP1, unsigned long int + OP2) + Set ROP to OP1/OP2. + + -- Function: void mpf_sqrt (mpf_t ROP, mpf_t OP) + -- Function: void mpf_sqrt_ui (mpf_t ROP, unsigned long int OP) + Set ROP to the square root of OP. + + -- Function: void mpf_pow_ui (mpf_t ROP, mpf_t OP1, unsigned long int + OP2) + Set ROP to OP1 raised to the power OP2. + + -- Function: void mpf_neg (mpf_t ROP, mpf_t OP) + Set ROP to -OP. + + -- Function: void mpf_abs (mpf_t ROP, mpf_t OP) + Set ROP to the absolute value of OP. + + -- Function: void mpf_mul_2exp (mpf_t ROP, mpf_t OP1, mp_bitcnt_t OP2) + Set ROP to OP1 times 2 raised to OP2. + + -- Function: void mpf_div_2exp (mpf_t ROP, mpf_t OP1, mp_bitcnt_t OP2) + Set ROP to OP1 divided by 2 raised to OP2. + + +File: gmp.info, Node: Float Comparison, Next: I/O of Floats, Prev: Float Arithmetic, Up: Floating-point Functions + +7.6 Comparison Functions +======================== + + -- Function: int mpf_cmp (mpf_t OP1, mpf_t OP2) + -- Function: int mpf_cmp_d (mpf_t OP1, double OP2) + -- Function: int mpf_cmp_ui (mpf_t OP1, unsigned long int OP2) + -- Function: int mpf_cmp_si (mpf_t OP1, signed long int OP2) + Compare OP1 and OP2. Return a positive value if OP1 > OP2, zero + if OP1 = OP2, and a negative value if OP1 < OP2. + + `mpf_cmp_d' can be called with an infinity, but results are + undefined for a NaN. + + -- Function: int mpf_eq (mpf_t OP1, mpf_t OP2, mp_bitcnt_t op3) + Return non-zero if the first OP3 bits of OP1 and OP2 are equal, + zero otherwise. I.e., test if OP1 and OP2 are approximately equal. + + Caution 1: All version of GMP up to version 4.2.4 compared just + whole limbs, meaning sometimes more than OP3 bits, sometimes fewer. + + Caution 2: This function will consider XXX11...111 and XX100...000 + different, even if ... is replaced by a semi-infinite number of + bits. Such numbers are really just one ulp off, and should be + considered equal. + + -- Function: void mpf_reldiff (mpf_t ROP, mpf_t OP1, mpf_t OP2) + Compute the relative difference between OP1 and OP2 and store the + result in ROP. This is abs(OP1-OP2)/OP1. + + -- Macro: int mpf_sgn (mpf_t OP) + Return +1 if OP > 0, 0 if OP = 0, and -1 if OP < 0. + + This function is actually implemented as a macro. It evaluates + its arguments multiple times. + + +File: gmp.info, Node: I/O of Floats, Next: Miscellaneous Float Functions, Prev: Float Comparison, Up: Floating-point Functions + +7.7 Input and Output Functions +============================== + +Functions that perform input from a stdio stream, and functions that +output to a stdio stream. Passing a `NULL' pointer for a STREAM +argument to any of these functions will make them read from `stdin' and +write to `stdout', respectively. + + When using any of these functions, it is a good idea to include +`stdio.h' before `gmp.h', since that will allow `gmp.h' to define +prototypes for these functions. + + -- Function: size_t mpf_out_str (FILE *STREAM, int BASE, size_t + N_DIGITS, mpf_t OP) + Print OP to STREAM, as a string of digits. Return the number of + bytes written, or if an error occurred, return 0. + + The mantissa is prefixed with an `0.' and is in the given BASE, + which may vary from 2 to 62 or from -2 to -36. An exponent is + then printed, separated by an `e', or if the base is greater than + 10 then by an `@'. The exponent is always in decimal. The + decimal point follows the current locale, on systems providing + `localeconv'. + + For BASE in the range 2..36, digits and lower-case letters are + used; for -2..-36, digits and upper-case letters are used; for + 37..62, digits, upper-case letters, and lower-case letters (in + that significance order) are used. + + Up to N_DIGITS will be printed from the mantissa, except that no + more digits than are accurately representable by OP will be + printed. N_DIGITS can be 0 to select that accurate maximum. + + -- Function: size_t mpf_inp_str (mpf_t ROP, FILE *STREAM, int BASE) + Read a string in base BASE from STREAM, and put the read float in + ROP. The string is of the form `M@N' or, if the base is 10 or + less, alternatively `MeN'. `M' is the mantissa and `N' is the + exponent. The mantissa is always in the specified base. The + exponent is either in the specified base or, if BASE is negative, + in decimal. The decimal point expected is taken from the current + locale, on systems providing `localeconv'. + + The argument BASE may be in the ranges 2 to 36, or -36 to -2. + Negative values are used to specify that the exponent is in + decimal. + + Unlike the corresponding `mpz' function, the base will not be + determined from the leading characters of the string if BASE is 0. + This is so that numbers like `0.23' are not interpreted as octal. + + Return the number of bytes read, or if an error occurred, return 0. + + +File: gmp.info, Node: Miscellaneous Float Functions, Prev: I/O of Floats, Up: Floating-point Functions + +7.8 Miscellaneous Functions +=========================== + + -- Function: void mpf_ceil (mpf_t ROP, mpf_t OP) + -- Function: void mpf_floor (mpf_t ROP, mpf_t OP) + -- Function: void mpf_trunc (mpf_t ROP, mpf_t OP) + Set ROP to OP rounded to an integer. `mpf_ceil' rounds to the + next higher integer, `mpf_floor' to the next lower, and `mpf_trunc' + to the integer towards zero. + + -- Function: int mpf_integer_p (mpf_t OP) + Return non-zero if OP is an integer. + + -- Function: int mpf_fits_ulong_p (mpf_t OP) + -- Function: int mpf_fits_slong_p (mpf_t OP) + -- Function: int mpf_fits_uint_p (mpf_t OP) + -- Function: int mpf_fits_sint_p (mpf_t OP) + -- Function: int mpf_fits_ushort_p (mpf_t OP) + -- Function: int mpf_fits_sshort_p (mpf_t OP) + Return non-zero if OP would fit in the respective C data type, when + truncated to an integer. + + -- Function: void mpf_urandomb (mpf_t ROP, gmp_randstate_t STATE, + mp_bitcnt_t NBITS) + Generate a uniformly distributed random float in ROP, such that 0 + <= ROP < 1, with NBITS significant bits in the mantissa. + + The variable STATE must be initialized by calling one of the + `gmp_randinit' functions (*Note Random State Initialization::) + before invoking this function. + + -- Function: void mpf_random2 (mpf_t ROP, mp_size_t MAX_SIZE, mp_exp_t + EXP) + Generate a random float of at most MAX_SIZE limbs, with long + strings of zeros and ones in the binary representation. The + exponent of the number is in the interval -EXP to EXP (in limbs). + This function is useful for testing functions and algorithms, + since these kind of random numbers have proven to be more likely + to trigger corner-case bugs. Negative random numbers are + generated when MAX_SIZE is negative. + + +File: gmp.info, Node: Low-level Functions, Next: Random Number Functions, Prev: Floating-point Functions, Up: Top + +8 Low-level Functions +********************* + +This chapter describes low-level GMP functions, used to implement the +high-level GMP functions, but also intended for time-critical user code. + + These functions start with the prefix `mpn_'. + + The `mpn' functions are designed to be as fast as possible, *not* to +provide a coherent calling interface. The different functions have +somewhat similar interfaces, but there are variations that make them +hard to use. These functions do as little as possible apart from the +real multiple precision computation, so that no time is spent on things +that not all callers need. + + A source operand is specified by a pointer to the least significant +limb and a limb count. A destination operand is specified by just a +pointer. It is the responsibility of the caller to ensure that the +destination has enough space for storing the result. + + With this way of specifying operands, it is possible to perform +computations on subranges of an argument, and store the result into a +subrange of a destination. + + A common requirement for all functions is that each source area +needs at least one limb. No size argument may be zero. Unless +otherwise stated, in-place operations are allowed where source and +destination are the same, but not where they only partly overlap. + + The `mpn' functions are the base for the implementation of the +`mpz_', `mpf_', and `mpq_' functions. + + This example adds the number beginning at S1P and the number +beginning at S2P and writes the sum at DESTP. All areas have N limbs. + + cy = mpn_add_n (destp, s1p, s2p, n) + + It should be noted that the `mpn' functions make no attempt to +identify high or low zero limbs on their operands, or other special +forms. On random data such cases will be unlikely and it'd be wasteful +for every function to check every time. An application knowing +something about its data can take steps to trim or perhaps split its +calculations. + + +In the notation used below, a source operand is identified by the +pointer to the least significant limb, and the limb count in braces. +For example, {S1P, S1N}. + + -- Function: mp_limb_t mpn_add_n (mp_limb_t *RP, const mp_limb_t *S1P, + const mp_limb_t *S2P, mp_size_t N) + Add {S1P, N} and {S2P, N}, and write the N least significant limbs + of the result to RP. Return carry, either 0 or 1. + + This is the lowest-level function for addition. It is the + preferred function for addition, since it is written in assembly + for most CPUs. For addition of a variable to itself (i.e., S1P + equals S2P) use `mpn_lshift' with a count of 1 for optimal speed. + + -- Function: mp_limb_t mpn_add_1 (mp_limb_t *RP, const mp_limb_t *S1P, + mp_size_t N, mp_limb_t S2LIMB) + Add {S1P, N} and S2LIMB, and write the N least significant limbs + of the result to RP. Return carry, either 0 or 1. + + -- Function: mp_limb_t mpn_add (mp_limb_t *RP, const mp_limb_t *S1P, + mp_size_t S1N, const mp_limb_t *S2P, mp_size_t S2N) + Add {S1P, S1N} and {S2P, S2N}, and write the S1N least significant + limbs of the result to RP. Return carry, either 0 or 1. + + This function requires that S1N is greater than or equal to S2N. + + -- Function: mp_limb_t mpn_sub_n (mp_limb_t *RP, const mp_limb_t *S1P, + const mp_limb_t *S2P, mp_size_t N) + Subtract {S2P, N} from {S1P, N}, and write the N least significant + limbs of the result to RP. Return borrow, either 0 or 1. + + This is the lowest-level function for subtraction. It is the + preferred function for subtraction, since it is written in + assembly for most CPUs. + + -- Function: mp_limb_t mpn_sub_1 (mp_limb_t *RP, const mp_limb_t *S1P, + mp_size_t N, mp_limb_t S2LIMB) + Subtract S2LIMB from {S1P, N}, and write the N least significant + limbs of the result to RP. Return borrow, either 0 or 1. + + -- Function: mp_limb_t mpn_sub (mp_limb_t *RP, const mp_limb_t *S1P, + mp_size_t S1N, const mp_limb_t *S2P, mp_size_t S2N) + Subtract {S2P, S2N} from {S1P, S1N}, and write the S1N least + significant limbs of the result to RP. Return borrow, either 0 or + 1. + + This function requires that S1N is greater than or equal to S2N. + + -- Function: void mpn_neg (mp_limb_t *RP, const mp_limb_t *SP, + mp_size_t N) + Perform the negation of {SP, N}, and write the result to {RP, N}. + Return carry-out. + + -- Function: void mpn_mul_n (mp_limb_t *RP, const mp_limb_t *S1P, + const mp_limb_t *S2P, mp_size_t N) + Multiply {S1P, N} and {S2P, N}, and write the 2*N-limb result to + RP. + + The destination has to have space for 2*N limbs, even if the + product's most significant limb is zero. No overlap is permitted + between the destination and either source. + + If the two input operands are the same, use `mpn_sqr'. + + -- Function: mp_limb_t mpn_mul (mp_limb_t *RP, const mp_limb_t *S1P, + mp_size_t S1N, const mp_limb_t *S2P, mp_size_t S2N) + Multiply {S1P, S1N} and {S2P, S2N}, and write the (S1N+S2N)-limb + result to RP. Return the most significant limb of the result. + + The destination has to have space for S1N + S2N limbs, even if the + product's most significant limb is zero. No overlap is permitted + between the destination and either source. + + This function requires that S1N is greater than or equal to S2N. + + -- Function: void mpn_sqr (mp_limb_t *RP, const mp_limb_t *S1P, + mp_size_t N) + Compute the square of {S1P, N} and write the 2*N-limb result to RP. + + The destination has to have space for 2*N limbs, even if the + result's most significant limb is zero. No overlap is permitted + between the destination and the source. + + -- Function: mp_limb_t mpn_mul_1 (mp_limb_t *RP, const mp_limb_t *S1P, + mp_size_t N, mp_limb_t S2LIMB) + Multiply {S1P, N} by S2LIMB, and write the N least significant + limbs of the product to RP. Return the most significant limb of + the product. {S1P, N} and {RP, N} are allowed to overlap provided + RP <= S1P. + + This is a low-level function that is a building block for general + multiplication as well as other operations in GMP. It is written + in assembly for most CPUs. + + Don't call this function if S2LIMB is a power of 2; use + `mpn_lshift' with a count equal to the logarithm of S2LIMB + instead, for optimal speed. + + -- Function: mp_limb_t mpn_addmul_1 (mp_limb_t *RP, const mp_limb_t + *S1P, mp_size_t N, mp_limb_t S2LIMB) + Multiply {S1P, N} and S2LIMB, and add the N least significant + limbs of the product to {RP, N} and write the result to RP. + Return the most significant limb of the product, plus carry-out + from the addition. + + This is a low-level function that is a building block for general + multiplication as well as other operations in GMP. It is written + in assembly for most CPUs. + + -- Function: mp_limb_t mpn_submul_1 (mp_limb_t *RP, const mp_limb_t + *S1P, mp_size_t N, mp_limb_t S2LIMB) + Multiply {S1P, N} and S2LIMB, and subtract the N least significant + limbs of the product from {RP, N} and write the result to RP. + Return the most significant limb of the product, plus borrow-out + from the subtraction. + + This is a low-level function that is a building block for general + multiplication and division as well as other operations in GMP. + It is written in assembly for most CPUs. + + -- Function: void mpn_tdiv_qr (mp_limb_t *QP, mp_limb_t *RP, mp_size_t + QXN, const mp_limb_t *NP, mp_size_t NN, const mp_limb_t *DP, + mp_size_t DN) + Divide {NP, NN} by {DP, DN} and put the quotient at {QP, NN-DN+1} + and the remainder at {RP, DN}. The quotient is rounded towards 0. + + No overlap is permitted between arguments, except that NP might + equal RP. The dividend size NN must be greater than or equal to + divisor size DN. The most significant limb of the divisor must be + non-zero. The QXN operand must be zero. + + -- Function: mp_limb_t mpn_divrem (mp_limb_t *R1P, mp_size_t QXN, + mp_limb_t *RS2P, mp_size_t RS2N, const mp_limb_t *S3P, + mp_size_t S3N) + [This function is obsolete. Please call `mpn_tdiv_qr' instead for + best performance.] + + Divide {RS2P, RS2N} by {S3P, S3N}, and write the quotient at R1P, + with the exception of the most significant limb, which is + returned. The remainder replaces the dividend at RS2P; it will be + S3N limbs long (i.e., as many limbs as the divisor). + + In addition to an integer quotient, QXN fraction limbs are + developed, and stored after the integral limbs. For most usages, + QXN will be zero. + + It is required that RS2N is greater than or equal to S3N. It is + required that the most significant bit of the divisor is set. + + If the quotient is not needed, pass RS2P + S3N as R1P. Aside from + that special case, no overlap between arguments is permitted. + + Return the most significant limb of the quotient, either 0 or 1. + + The area at R1P needs to be RS2N - S3N + QXN limbs large. + + -- Function: mp_limb_t mpn_divrem_1 (mp_limb_t *R1P, mp_size_t QXN, + mp_limb_t *S2P, mp_size_t S2N, mp_limb_t S3LIMB) + -- Macro: mp_limb_t mpn_divmod_1 (mp_limb_t *R1P, mp_limb_t *S2P, + mp_size_t S2N, mp_limb_t S3LIMB) + Divide {S2P, S2N} by S3LIMB, and write the quotient at R1P. + Return the remainder. + + The integer quotient is written to {R1P+QXN, S2N} and in addition + QXN fraction limbs are developed and written to {R1P, QXN}. + Either or both S2N and QXN can be zero. For most usages, QXN will + be zero. + + `mpn_divmod_1' exists for upward source compatibility and is + simply a macro calling `mpn_divrem_1' with a QXN of 0. + + The areas at R1P and S2P have to be identical or completely + separate, not partially overlapping. + + -- Function: mp_limb_t mpn_divmod (mp_limb_t *R1P, mp_limb_t *RS2P, + mp_size_t RS2N, const mp_limb_t *S3P, mp_size_t S3N) + [This function is obsolete. Please call `mpn_tdiv_qr' instead for + best performance.] + + -- Macro: mp_limb_t mpn_divexact_by3 (mp_limb_t *RP, mp_limb_t *SP, + mp_size_t N) + -- Function: mp_limb_t mpn_divexact_by3c (mp_limb_t *RP, mp_limb_t + *SP, mp_size_t N, mp_limb_t CARRY) + Divide {SP, N} by 3, expecting it to divide exactly, and writing + the result to {RP, N}. If 3 divides exactly, the return value is + zero and the result is the quotient. If not, the return value is + non-zero and the result won't be anything useful. + + `mpn_divexact_by3c' takes an initial carry parameter, which can be + the return value from a previous call, so a large calculation can + be done piece by piece from low to high. `mpn_divexact_by3' is + simply a macro calling `mpn_divexact_by3c' with a 0 carry + parameter. + + These routines use a multiply-by-inverse and will be faster than + `mpn_divrem_1' on CPUs with fast multiplication but slow division. + + The source a, result q, size n, initial carry i, and return value + c satisfy c*b^n + a-i = 3*q, where b=2^GMP_NUMB_BITS. The return + c is always 0, 1 or 2, and the initial carry i must also be 0, 1 + or 2 (these are both borrows really). When c=0 clearly q=(a-i)/3. + When c!=0, the remainder (a-i) mod 3 is given by 3-c, because b + == 1 mod 3 (when `mp_bits_per_limb' is even, which is always so + currently). + + -- Function: mp_limb_t mpn_mod_1 (mp_limb_t *S1P, mp_size_t S1N, + mp_limb_t S2LIMB) + Divide {S1P, S1N} by S2LIMB, and return the remainder. S1N can be + zero. + + -- Function: mp_limb_t mpn_lshift (mp_limb_t *RP, const mp_limb_t *SP, + mp_size_t N, unsigned int COUNT) + Shift {SP, N} left by COUNT bits, and write the result to {RP, N}. + The bits shifted out at the left are returned in the least + significant COUNT bits of the return value (the rest of the return + value is zero). + + COUNT must be in the range 1 to mp_bits_per_limb-1. The regions + {SP, N} and {RP, N} may overlap, provided RP >= SP. + + This function is written in assembly for most CPUs. + + -- Function: mp_limb_t mpn_rshift (mp_limb_t *RP, const mp_limb_t *SP, + mp_size_t N, unsigned int COUNT) + Shift {SP, N} right by COUNT bits, and write the result to {RP, + N}. The bits shifted out at the right are returned in the most + significant COUNT bits of the return value (the rest of the return + value is zero). + + COUNT must be in the range 1 to mp_bits_per_limb-1. The regions + {SP, N} and {RP, N} may overlap, provided RP <= SP. + + This function is written in assembly for most CPUs. + + -- Function: int mpn_cmp (const mp_limb_t *S1P, const mp_limb_t *S2P, + mp_size_t N) + Compare {S1P, N} and {S2P, N} and return a positive value if S1 > + S2, 0 if they are equal, or a negative value if S1 < S2. + + -- Function: mp_size_t mpn_gcd (mp_limb_t *RP, mp_limb_t *XP, + mp_size_t XN, mp_limb_t *YP, mp_size_t YN) + Set {RP, RETVAL} to the greatest common divisor of {XP, XN} and + {YP, YN}. The result can be up to YN limbs, the return value is + the actual number produced. Both source operands are destroyed. + + {XP, XN} must have at least as many bits as {YP, YN}. {YP, YN} + must be odd. Both operands must have non-zero most significant + limbs. No overlap is permitted between {XP, XN} and {YP, YN}. + + -- Function: mp_limb_t mpn_gcd_1 (const mp_limb_t *XP, mp_size_t XN, + mp_limb_t YLIMB) + Return the greatest common divisor of {XP, XN} and YLIMB. Both + operands must be non-zero. + + -- Function: mp_size_t mpn_gcdext (mp_limb_t *GP, mp_limb_t *SP, + mp_size_t *SN, mp_limb_t *XP, mp_size_t XN, mp_limb_t *YP, + mp_size_t YN) + Let U be defined by {XP, XN} and let V be defined by {YP, YN}. + + Compute the greatest common divisor G of U and V. Compute a + cofactor S such that G = US + VT. The second cofactor T is not + computed but can easily be obtained from (G - U*S) / V (the + division will be exact). It is required that U >= V > 0. + + S satisfies S = 1 or abs(S) < V / (2 G). S = 0 if and only if V + divides U (i.e., G = V). + + Store G at GP and let the return value define its limb count. + Store S at SP and let |*SN| define its limb count. S can be + negative; when this happens *SN will be negative. The areas at GP + and SP should each have room for XN+1 limbs. + + The areas {XP, XN+1} and {YP, YN+1} are destroyed (i.e. the input + operands plus an extra limb past the end of each). + + Compatibility note: GMP 4.3.0 and 4.3.1 defined S less strictly. + Earlier as well as later GMP releases define S as described here. + + -- Function: mp_size_t mpn_sqrtrem (mp_limb_t *R1P, mp_limb_t *R2P, + const mp_limb_t *SP, mp_size_t N) + Compute the square root of {SP, N} and put the result at {R1P, + ceil(N/2)} and the remainder at {R2P, RETVAL}. R2P needs space + for N limbs, but the return value indicates how many are produced. + + The most significant limb of {SP, N} must be non-zero. The areas + {R1P, ceil(N/2)} and {SP, N} must be completely separate. The + areas {R2P, N} and {SP, N} must be either identical or completely + separate. + + If the remainder is not wanted then R2P can be `NULL', and in this + case the return value is zero or non-zero according to whether the + remainder would have been zero or non-zero. + + A return value of zero indicates a perfect square. See also + `mpz_perfect_square_p'. + + -- Function: mp_size_t mpn_get_str (unsigned char *STR, int BASE, + mp_limb_t *S1P, mp_size_t S1N) + Convert {S1P, S1N} to a raw unsigned char array at STR in base + BASE, and return the number of characters produced. There may be + leading zeros in the string. The string is not in ASCII; to + convert it to printable format, add the ASCII codes for `0' or + `A', depending on the base and range. BASE can vary from 2 to 256. + + The most significant limb of the input {S1P, S1N} must be + non-zero. The input {S1P, S1N} is clobbered, except when BASE is + a power of 2, in which case it's unchanged. + + The area at STR has to have space for the largest possible number + represented by a S1N long limb array, plus one extra character. + + -- Function: mp_size_t mpn_set_str (mp_limb_t *RP, const unsigned char + *STR, size_t STRSIZE, int BASE) + Convert bytes {STR,STRSIZE} in the given BASE to limbs at RP. + + STR[0] is the most significant byte and STR[STRSIZE-1] is the + least significant. Each byte should be a value in the range 0 to + BASE-1, not an ASCII character. BASE can vary from 2 to 256. + + The return value is the number of limbs written to RP. If the most + significant input byte is non-zero then the high limb at RP will be + non-zero, and only that exact number of limbs will be required + there. + + If the most significant input byte is zero then there may be high + zero limbs written to RP and included in the return value. + + STRSIZE must be at least 1, and no overlap is permitted between + {STR,STRSIZE} and the result at RP. + + -- Function: mp_bitcnt_t mpn_scan0 (const mp_limb_t *S1P, mp_bitcnt_t + BIT) + Scan S1P from bit position BIT for the next clear bit. + + It is required that there be a clear bit within the area at S1P at + or beyond bit position BIT, so that the function has something to + return. + + -- Function: mp_bitcnt_t mpn_scan1 (const mp_limb_t *S1P, mp_bitcnt_t + BIT) + Scan S1P from bit position BIT for the next set bit. + + It is required that there be a set bit within the area at S1P at or + beyond bit position BIT, so that the function has something to + return. + + -- Function: void mpn_random (mp_limb_t *R1P, mp_size_t R1N) + -- Function: void mpn_random2 (mp_limb_t *R1P, mp_size_t R1N) + Generate a random number of length R1N and store it at R1P. The + most significant limb is always non-zero. `mpn_random' generates + uniformly distributed limb data, `mpn_random2' generates long + strings of zeros and ones in the binary representation. + + `mpn_random2' is intended for testing the correctness of the `mpn' + routines. + + -- Function: mp_bitcnt_t mpn_popcount (const mp_limb_t *S1P, mp_size_t + N) + Count the number of set bits in {S1P, N}. + + -- Function: mp_bitcnt_t mpn_hamdist (const mp_limb_t *S1P, const + mp_limb_t *S2P, mp_size_t N) + Compute the hamming distance between {S1P, N} and {S2P, N}, which + is the number of bit positions where the two operands have + different bit values. + + -- Function: int mpn_perfect_square_p (const mp_limb_t *S1P, mp_size_t + N) + Return non-zero iff {S1P, N} is a perfect square. + + -- Function: void mpn_and_n (mp_limb_t *RP, const mp_limb_t *S1P, + const mp_limb_t *S2P, mp_size_t N) + Perform the bitwise logical and of {S1P, N} and {S2P, N}, and + write the result to {RP, N}. + + -- Function: void mpn_ior_n (mp_limb_t *RP, const mp_limb_t *S1P, + const mp_limb_t *S2P, mp_size_t N) + Perform the bitwise logical inclusive or of {S1P, N} and {S2P, N}, + and write the result to {RP, N}. + + -- Function: void mpn_xor_n (mp_limb_t *RP, const mp_limb_t *S1P, + const mp_limb_t *S2P, mp_size_t N) + Perform the bitwise logical exclusive or of {S1P, N} and {S2P, N}, + and write the result to {RP, N}. + + -- Function: void mpn_andn_n (mp_limb_t *RP, const mp_limb_t *S1P, + const mp_limb_t *S2P, mp_size_t N) + Perform the bitwise logical and of {S1P, N} and the bitwise + complement of {S2P, N}, and write the result to {RP, N}. + + -- Function: void mpn_iorn_n (mp_limb_t *RP, const mp_limb_t *S1P, + const mp_limb_t *S2P, mp_size_t N) + Perform the bitwise logical inclusive or of {S1P, N} and the + bitwise complement of {S2P, N}, and write the result to {RP, N}. + + -- Function: void mpn_nand_n (mp_limb_t *RP, const mp_limb_t *S1P, + const mp_limb_t *S2P, mp_size_t N) + Perform the bitwise logical and of {S1P, N} and {S2P, N}, and + write the bitwise complement of the result to {RP, N}. + + -- Function: void mpn_nior_n (mp_limb_t *RP, const mp_limb_t *S1P, + const mp_limb_t *S2P, mp_size_t N) + Perform the bitwise logical inclusive or of {S1P, N} and {S2P, N}, + and write the bitwise complement of the result to {RP, N}. + + -- Function: void mpn_xnor_n (mp_limb_t *RP, const mp_limb_t *S1P, + const mp_limb_t *S2P, mp_size_t N) + Perform the bitwise logical exclusive or of {S1P, N} and {S2P, N}, + and write the bitwise complement of the result to {RP, N}. + + -- Function: void mpn_com (mp_limb_t *RP, const mp_limb_t *SP, + mp_size_t N) + Perform the bitwise complement of {SP, N}, and write the result to + {RP, N}. + + -- Function: void mpn_copyi (mp_limb_t *RP, const mp_limb_t *S1P, + mp_size_t N) + Copy from {S1P, N} to {RP, N}, increasingly. + + -- Function: void mpn_copyd (mp_limb_t *RP, const mp_limb_t *S1P, + mp_size_t N) + Copy from {S1P, N} to {RP, N}, decreasingly. + + -- Function: void mpn_zero (mp_limb_t *RP, mp_size_t N) + Zero {RP, N}. + + +8.1 Nails +========= + +*Everything in this section is highly experimental and may disappear or +be subject to incompatible changes in a future version of GMP.* + + Nails are an experimental feature whereby a few bits are left unused +at the top of each `mp_limb_t'. This can significantly improve carry +handling on some processors. + + All the `mpn' functions accepting limb data will expect the nail +bits to be zero on entry, and will return data with the nails similarly +all zero. This applies both to limb vectors and to single limb +arguments. + + Nails can be enabled by configuring with `--enable-nails'. By +default the number of bits will be chosen according to what suits the +host processor, but a particular number can be selected with +`--enable-nails=N'. + + At the mpn level, a nail build is neither source nor binary +compatible with a non-nail build, strictly speaking. But programs +acting on limbs only through the mpn functions are likely to work +equally well with either build, and judicious use of the definitions +below should make any program compatible with either build, at the +source level. + + For the higher level routines, meaning `mpz' etc, a nail build +should be fully source and binary compatible with a non-nail build. + + -- Macro: GMP_NAIL_BITS + -- Macro: GMP_NUMB_BITS + -- Macro: GMP_LIMB_BITS + `GMP_NAIL_BITS' is the number of nail bits, or 0 when nails are + not in use. `GMP_NUMB_BITS' is the number of data bits in a limb. + `GMP_LIMB_BITS' is the total number of bits in an `mp_limb_t'. In + all cases + + GMP_LIMB_BITS == GMP_NAIL_BITS + GMP_NUMB_BITS + + -- Macro: GMP_NAIL_MASK + -- Macro: GMP_NUMB_MASK + Bit masks for the nail and number parts of a limb. + `GMP_NAIL_MASK' is 0 when nails are not in use. + + `GMP_NAIL_MASK' is not often needed, since the nail part can be + obtained with `x >> GMP_NUMB_BITS', and that means one less large + constant, which can help various RISC chips. + + -- Macro: GMP_NUMB_MAX + The maximum value that can be stored in the number part of a limb. + This is the same as `GMP_NUMB_MASK', but can be used for clarity + when doing comparisons rather than bit-wise operations. + + The term "nails" comes from finger or toe nails, which are at the +ends of a limb (arm or leg). "numb" is short for number, but is also +how the developers felt after trying for a long time to come up with +sensible names for these things. + + In the future (the distant future most likely) a non-zero nail might +be permitted, giving non-unique representations for numbers in a limb +vector. This would help vector processors since carries would only +ever need to propagate one or two limbs. + + +File: gmp.info, Node: Random Number Functions, Next: Formatted Output, Prev: Low-level Functions, Up: Top + +9 Random Number Functions +************************* + +Sequences of pseudo-random numbers in GMP are generated using a +variable of type `gmp_randstate_t', which holds an algorithm selection +and a current state. Such a variable must be initialized by a call to +one of the `gmp_randinit' functions, and can be seeded with one of the +`gmp_randseed' functions. + + The functions actually generating random numbers are described in +*Note Integer Random Numbers::, and *Note Miscellaneous Float +Functions::. + + The older style random number functions don't accept a +`gmp_randstate_t' parameter but instead share a global variable of that +type. They use a default algorithm and are currently not seeded +(though perhaps that will change in the future). The new functions +accepting a `gmp_randstate_t' are recommended for applications that +care about randomness. + +* Menu: + +* Random State Initialization:: +* Random State Seeding:: +* Random State Miscellaneous:: + + +File: gmp.info, Node: Random State Initialization, Next: Random State Seeding, Prev: Random Number Functions, Up: Random Number Functions + +9.1 Random State Initialization +=============================== + + -- Function: void gmp_randinit_default (gmp_randstate_t STATE) + Initialize STATE with a default algorithm. This will be a + compromise between speed and randomness, and is recommended for + applications with no special requirements. Currently this is + `gmp_randinit_mt'. + + -- Function: void gmp_randinit_mt (gmp_randstate_t STATE) + Initialize STATE for a Mersenne Twister algorithm. This algorithm + is fast and has good randomness properties. + + -- Function: void gmp_randinit_lc_2exp (gmp_randstate_t STATE, mpz_t + A, unsigned long C, mp_bitcnt_t M2EXP) + Initialize STATE with a linear congruential algorithm X = (A*X + + C) mod 2^M2EXP. + + The low bits of X in this algorithm are not very random. The least + significant bit will have a period no more than 2, and the second + bit no more than 4, etc. For this reason only the high half of + each X is actually used. + + When a random number of more than M2EXP/2 bits is to be generated, + multiple iterations of the recurrence are used and the results + concatenated. + + -- Function: int gmp_randinit_lc_2exp_size (gmp_randstate_t STATE, + mp_bitcnt_t SIZE) + Initialize STATE for a linear congruential algorithm as per + `gmp_randinit_lc_2exp'. A, C and M2EXP are selected from a table, + chosen so that SIZE bits (or more) of each X will be used, ie. + M2EXP/2 >= SIZE. + + If successful the return value is non-zero. If SIZE is bigger + than the table data provides then the return value is zero. The + maximum SIZE currently supported is 128. + + -- Function: void gmp_randinit_set (gmp_randstate_t ROP, + gmp_randstate_t OP) + Initialize ROP with a copy of the algorithm and state from OP. + + -- Function: void gmp_randinit (gmp_randstate_t STATE, + gmp_randalg_t ALG, ...) + *This function is obsolete.* + + Initialize STATE with an algorithm selected by ALG. The only + choice is `GMP_RAND_ALG_LC', which is `gmp_randinit_lc_2exp_size' + described above. A third parameter of type `unsigned long' is + required, this is the SIZE for that function. + `GMP_RAND_ALG_DEFAULT' or 0 are the same as `GMP_RAND_ALG_LC'. + + `gmp_randinit' sets bits in the global variable `gmp_errno' to + indicate an error. `GMP_ERROR_UNSUPPORTED_ARGUMENT' if ALG is + unsupported, or `GMP_ERROR_INVALID_ARGUMENT' if the SIZE parameter + is too big. It may be noted this error reporting is not thread + safe (a good reason to use `gmp_randinit_lc_2exp_size' instead). + + -- Function: void gmp_randclear (gmp_randstate_t STATE) + Free all memory occupied by STATE. + + +File: gmp.info, Node: Random State Seeding, Next: Random State Miscellaneous, Prev: Random State Initialization, Up: Random Number Functions + +9.2 Random State Seeding +======================== + + -- Function: void gmp_randseed (gmp_randstate_t STATE, mpz_t SEED) + -- Function: void gmp_randseed_ui (gmp_randstate_t STATE, + unsigned long int SEED) + Set an initial seed value into STATE. + + The size of a seed determines how many different sequences of + random numbers that it's possible to generate. The "quality" of + the seed is the randomness of a given seed compared to the + previous seed used, and this affects the randomness of separate + number sequences. The method for choosing a seed is critical if + the generated numbers are to be used for important applications, + such as generating cryptographic keys. + + Traditionally the system time has been used to seed, but care + needs to be taken with this. If an application seeds often and + the resolution of the system clock is low, then the same sequence + of numbers might be repeated. Also, the system time is quite easy + to guess, so if unpredictability is required then it should + definitely not be the only source for the seed value. On some + systems there's a special device `/dev/random' which provides + random data better suited for use as a seed. + + +File: gmp.info, Node: Random State Miscellaneous, Prev: Random State Seeding, Up: Random Number Functions + +9.3 Random State Miscellaneous +============================== + + -- Function: unsigned long gmp_urandomb_ui (gmp_randstate_t STATE, + unsigned long N) + Return a uniformly distributed random number of N bits, ie. in the + range 0 to 2^N-1 inclusive. N must be less than or equal to the + number of bits in an `unsigned long'. + + -- Function: unsigned long gmp_urandomm_ui (gmp_randstate_t STATE, + unsigned long N) + Return a uniformly distributed random number in the range 0 to + N-1, inclusive. + + +File: gmp.info, Node: Formatted Output, Next: Formatted Input, Prev: Random Number Functions, Up: Top + +10 Formatted Output +******************* + +* Menu: + +* Formatted Output Strings:: +* Formatted Output Functions:: +* C++ Formatted Output:: + + +File: gmp.info, Node: Formatted Output Strings, Next: Formatted Output Functions, Prev: Formatted Output, Up: Formatted Output + +10.1 Format Strings +=================== + +`gmp_printf' and friends accept format strings similar to the standard C +`printf' (*note Formatted Output: (libc)Formatted Output.). A format +specification is of the form + + % [flags] [width] [.[precision]] [type] conv + + GMP adds types `Z', `Q' and `F' for `mpz_t', `mpq_t' and `mpf_t' +respectively, `M' for `mp_limb_t', and `N' for an `mp_limb_t' array. +`Z', `Q', `M' and `N' behave like integers. `Q' will print a `/' and a +denominator, if needed. `F' behaves like a float. For example, + + mpz_t z; + gmp_printf ("%s is an mpz %Zd\n", "here", z); + + mpq_t q; + gmp_printf ("a hex rational: %#40Qx\n", q); + + mpf_t f; + int n; + gmp_printf ("fixed point mpf %.*Ff with %d digits\n", n, f, n); + + mp_limb_t l; + gmp_printf ("limb %Mu\n", l); + + const mp_limb_t *ptr; + mp_size_t size; + gmp_printf ("limb array %Nx\n", ptr, size); + + For `N' the limbs are expected least significant first, as per the +`mpn' functions (*note Low-level Functions::). A negative size can be +given to print the value as a negative. + + All the standard C `printf' types behave the same as the C library +`printf', and can be freely intermixed with the GMP extensions. In the +current implementation the standard parts of the format string are +simply handed to `printf' and only the GMP extensions handled directly. + + The flags accepted are as follows. GLIBC style ' is only for the +standard C types (not the GMP types), and only if the C library +supports it. + + 0 pad with zeros (rather than spaces) + # show the base with `0x', `0X' or `0' + + always show a sign + (space) show a space or a `-' sign + ' group digits, GLIBC style (not GMP types) + + The optional width and precision can be given as a number within the +format string, or as a `*' to take an extra parameter of type `int', the +same as the standard `printf'. + + The standard types accepted are as follows. `h' and `l' are +portable, the rest will depend on the compiler (or include files) for +the type and the C library for the output. + + h short + hh char + j intmax_t or uintmax_t + l long or wchar_t + ll long long + L long double + q quad_t or u_quad_t + t ptrdiff_t + z size_t + +The GMP types are + + F mpf_t, float conversions + Q mpq_t, integer conversions + M mp_limb_t, integer conversions + N mp_limb_t array, integer conversions + Z mpz_t, integer conversions + + The conversions accepted are as follows. `a' and `A' are always +supported for `mpf_t' but depend on the C library for standard C float +types. `m' and `p' depend on the C library. + + a A hex floats, C99 style + c character + d decimal integer + e E scientific format float + f fixed point float + i same as d + g G fixed or scientific float + m `strerror' string, GLIBC style + n store characters written so far + o octal integer + p pointer + s string + u unsigned integer + x X hex integer + + `o', `x' and `X' are unsigned for the standard C types, but for +types `Z', `Q' and `N' they are signed. `u' is not meaningful for `Z', +`Q' and `N'. + + `M' is a proxy for the C library `l' or `L', according to the size +of `mp_limb_t'. Unsigned conversions will be usual, but a signed +conversion can be used and will interpret the value as a twos complement +negative. + + `n' can be used with any type, even the GMP types. + + Other types or conversions that might be accepted by the C library +`printf' cannot be used through `gmp_printf', this includes for +instance extensions registered with GLIBC `register_printf_function'. +Also currently there's no support for POSIX `$' style numbered arguments +(perhaps this will be added in the future). + + The precision field has it's usual meaning for integer `Z' and float +`F' types, but is currently undefined for `Q' and should not be used +with that. + + `mpf_t' conversions only ever generate as many digits as can be +accurately represented by the operand, the same as `mpf_get_str' does. +Zeros will be used if necessary to pad to the requested precision. This +happens even for an `f' conversion of an `mpf_t' which is an integer, +for instance 2^1024 in an `mpf_t' of 128 bits precision will only +produce about 40 digits, then pad with zeros to the decimal point. An +empty precision field like `%.Fe' or `%.Ff' can be used to specifically +request just the significant digits. + + The decimal point character (or string) is taken from the current +locale settings on systems which provide `localeconv' (*note Locales +and Internationalization: (libc)Locales.). The C library will normally +do the same for standard float output. + + The format string is only interpreted as plain `char's, multibyte +characters are not recognised. Perhaps this will change in the future. + + +File: gmp.info, Node: Formatted Output Functions, Next: C++ Formatted Output, Prev: Formatted Output Strings, Up: Formatted Output + +10.2 Functions +============== + +Each of the following functions is similar to the corresponding C +library function. The basic `printf' forms take a variable argument +list. The `vprintf' forms take an argument pointer, see *Note Variadic +Functions: (libc)Variadic Functions, or `man 3 va_start'. + + It should be emphasised that if a format string is invalid, or the +arguments don't match what the format specifies, then the behaviour of +any of these functions will be unpredictable. GCC format string +checking is not available, since it doesn't recognise the GMP +extensions. + + The file based functions `gmp_printf' and `gmp_fprintf' will return +-1 to indicate a write error. Output is not "atomic", so partial +output may be produced if a write error occurs. All the functions can +return -1 if the C library `printf' variant in use returns -1, but this +shouldn't normally occur. + + -- Function: int gmp_printf (const char *FMT, ...) + -- Function: int gmp_vprintf (const char *FMT, va_list AP) + Print to the standard output `stdout'. Return the number of + characters written, or -1 if an error occurred. + + -- Function: int gmp_fprintf (FILE *FP, const char *FMT, ...) + -- Function: int gmp_vfprintf (FILE *FP, const char *FMT, va_list AP) + Print to the stream FP. Return the number of characters written, + or -1 if an error occurred. + + -- Function: int gmp_sprintf (char *BUF, const char *FMT, ...) + -- Function: int gmp_vsprintf (char *BUF, const char *FMT, va_list AP) + Form a null-terminated string in BUF. Return the number of + characters written, excluding the terminating null. + + No overlap is permitted between the space at BUF and the string + FMT. + + These functions are not recommended, since there's no protection + against exceeding the space available at BUF. + + -- Function: int gmp_snprintf (char *BUF, size_t SIZE, const char + *FMT, ...) + -- Function: int gmp_vsnprintf (char *BUF, size_t SIZE, const char + *FMT, va_list AP) + Form a null-terminated string in BUF. No more than SIZE bytes + will be written. To get the full output, SIZE must be enough for + the string and null-terminator. + + The return value is the total number of characters which ought to + have been produced, excluding the terminating null. If RETVAL >= + SIZE then the actual output has been truncated to the first SIZE-1 + characters, and a null appended. + + No overlap is permitted between the region {BUF,SIZE} and the FMT + string. + + Notice the return value is in ISO C99 `snprintf' style. This is + so even if the C library `vsnprintf' is the older GLIBC 2.0.x + style. + + -- Function: int gmp_asprintf (char **PP, const char *FMT, ...) + -- Function: int gmp_vasprintf (char **PP, const char *FMT, va_list AP) + Form a null-terminated string in a block of memory obtained from + the current memory allocation function (*note Custom + Allocation::). The block will be the size of the string and + null-terminator. The address of the block in stored to *PP. The + return value is the number of characters produced, excluding the + null-terminator. + + Unlike the C library `asprintf', `gmp_asprintf' doesn't return -1 + if there's no more memory available, it lets the current allocation + function handle that. + + -- Function: int gmp_obstack_printf (struct obstack *OB, const char + *FMT, ...) + -- Function: int gmp_obstack_vprintf (struct obstack *OB, const char + *FMT, va_list AP) + Append to the current object in OB. The return value is the + number of characters written. A null-terminator is not written. + + FMT cannot be within the current object in OB, since that object + might move as it grows. + + These functions are available only when the C library provides the + obstack feature, which probably means only on GNU systems, see + *Note Obstacks: (libc)Obstacks. + + +File: gmp.info, Node: C++ Formatted Output, Prev: Formatted Output Functions, Up: Formatted Output + +10.3 C++ Formatted Output +========================= + +The following functions are provided in `libgmpxx' (*note Headers and +Libraries::), which is built if C++ support is enabled (*note Build +Options::). Prototypes are available from `'. + + -- Function: ostream& operator<< (ostream& STREAM, mpz_t OP) + Print OP to STREAM, using its `ios' formatting settings. + `ios::width' is reset to 0 after output, the same as the standard + `ostream operator<<' routines do. + + In hex or octal, OP is printed as a signed number, the same as for + decimal. This is unlike the standard `operator<<' routines on + `int' etc, which instead give twos complement. + + -- Function: ostream& operator<< (ostream& STREAM, mpq_t OP) + Print OP to STREAM, using its `ios' formatting settings. + `ios::width' is reset to 0 after output, the same as the standard + `ostream operator<<' routines do. + + Output will be a fraction like `5/9', or if the denominator is 1 + then just a plain integer like `123'. + + In hex or octal, OP is printed as a signed value, the same as for + decimal. If `ios::showbase' is set then a base indicator is shown + on both the numerator and denominator (if the denominator is + required). + + -- Function: ostream& operator<< (ostream& STREAM, mpf_t OP) + Print OP to STREAM, using its `ios' formatting settings. + `ios::width' is reset to 0 after output, the same as the standard + `ostream operator<<' routines do. + + The decimal point follows the standard library float `operator<<', + which on recent systems means the `std::locale' imbued on STREAM. + + Hex and octal are supported, unlike the standard `operator<<' on + `double'. The mantissa will be in hex or octal, the exponent will + be in decimal. For hex the exponent delimiter is an `@'. This is + as per `mpf_out_str'. + + `ios::showbase' is supported, and will put a base on the mantissa, + for example hex `0x1.8' or `0x0.8', or octal `01.4' or `00.4'. + This last form is slightly strange, but at least differentiates + itself from decimal. + + These operators mean that GMP types can be printed in the usual C++ +way, for example, + + mpz_t z; + int n; + ... + cout << "iteration " << n << " value " << z << "\n"; + + But note that `ostream' output (and `istream' input, *note C++ +Formatted Input::) is the only overloading available for the GMP types +and that for instance using `+' with an `mpz_t' will have unpredictable +results. For classes with overloading, see *Note C++ Class Interface::. + + +File: gmp.info, Node: Formatted Input, Next: C++ Class Interface, Prev: Formatted Output, Up: Top + +11 Formatted Input +****************** + +* Menu: + +* Formatted Input Strings:: +* Formatted Input Functions:: +* C++ Formatted Input:: + + +File: gmp.info, Node: Formatted Input Strings, Next: Formatted Input Functions, Prev: Formatted Input, Up: Formatted Input + +11.1 Formatted Input Strings +============================ + +`gmp_scanf' and friends accept format strings similar to the standard C +`scanf' (*note Formatted Input: (libc)Formatted Input.). A format +specification is of the form + + % [flags] [width] [type] conv + + GMP adds types `Z', `Q' and `F' for `mpz_t', `mpq_t' and `mpf_t' +respectively. `Z' and `Q' behave like integers. `Q' will read a `/' +and a denominator, if present. `F' behaves like a float. + + GMP variables don't require an `&' when passed to `gmp_scanf', since +they're already "call-by-reference". For example, + + /* to read say "a(5) = 1234" */ + int n; + mpz_t z; + gmp_scanf ("a(%d) = %Zd\n", &n, z); + + mpq_t q1, q2; + gmp_sscanf ("0377 + 0x10/0x11", "%Qi + %Qi", q1, q2); + + /* to read say "topleft (1.55,-2.66)" */ + mpf_t x, y; + char buf[32]; + gmp_scanf ("%31s (%Ff,%Ff)", buf, x, y); + + All the standard C `scanf' types behave the same as in the C library +`scanf', and can be freely intermixed with the GMP extensions. In the +current implementation the standard parts of the format string are +simply handed to `scanf' and only the GMP extensions handled directly. + + The flags accepted are as follows. `a' and `'' will depend on +support from the C library, and `'' cannot be used with GMP types. + + * read but don't store + a allocate a buffer (string conversions) + ' grouped digits, GLIBC style (not GMP + types) + + The standard types accepted are as follows. `h' and `l' are +portable, the rest will depend on the compiler (or include files) for +the type and the C library for the input. + + h short + hh char + j intmax_t or uintmax_t + l long int, double or wchar_t + ll long long + L long double + q quad_t or u_quad_t + t ptrdiff_t + z size_t + +The GMP types are + + F mpf_t, float conversions + Q mpq_t, integer conversions + Z mpz_t, integer conversions + + The conversions accepted are as follows. `p' and `[' will depend on +support from the C library, the rest are standard. + + c character or characters + d decimal integer + e E f g G float + i integer with base indicator + n characters read so far + o octal integer + p pointer + s string of non-whitespace characters + u decimal integer + x X hex integer + [ string of characters in a set + + `e', `E', `f', `g' and `G' are identical, they all read either fixed +point or scientific format, and either upper or lower case `e' for the +exponent in scientific format. + + C99 style hex float format (`printf %a', *note Formatted Output +Strings::) is always accepted for `mpf_t', but for the standard float +types it will depend on the C library. + + `x' and `X' are identical, both accept both upper and lower case +hexadecimal. + + `o', `u', `x' and `X' all read positive or negative values. For the +standard C types these are described as "unsigned" conversions, but +that merely affects certain overflow handling, negatives are still +allowed (per `strtoul', *note Parsing of Integers: (libc)Parsing of +Integers.). For GMP types there are no overflows, so `d' and `u' are +identical. + + `Q' type reads the numerator and (optional) denominator as given. +If the value might not be in canonical form then `mpq_canonicalize' +must be called before using it in any calculations (*note Rational +Number Functions::). + + `Qi' will read a base specification separately for the numerator and +denominator. For example `0x10/11' would be 16/11, whereas `0x10/0x11' +would be 16/17. + + `n' can be used with any of the types above, even the GMP types. +`*' to suppress assignment is allowed, though in that case it would do +nothing at all. + + Other conversions or types that might be accepted by the C library +`scanf' cannot be used through `gmp_scanf'. + + Whitespace is read and discarded before a field, except for `c' and +`[' conversions. + + For float conversions, the decimal point character (or string) +expected is taken from the current locale settings on systems which +provide `localeconv' (*note Locales and Internationalization: +(libc)Locales.). The C library will normally do the same for standard +float input. + + The format string is only interpreted as plain `char's, multibyte +characters are not recognised. Perhaps this will change in the future. + + +File: gmp.info, Node: Formatted Input Functions, Next: C++ Formatted Input, Prev: Formatted Input Strings, Up: Formatted Input + +11.2 Formatted Input Functions +============================== + +Each of the following functions is similar to the corresponding C +library function. The plain `scanf' forms take a variable argument +list. The `vscanf' forms take an argument pointer, see *Note Variadic +Functions: (libc)Variadic Functions, or `man 3 va_start'. + + It should be emphasised that if a format string is invalid, or the +arguments don't match what the format specifies, then the behaviour of +any of these functions will be unpredictable. GCC format string +checking is not available, since it doesn't recognise the GMP +extensions. + + No overlap is permitted between the FMT string and any of the results +produced. + + -- Function: int gmp_scanf (const char *FMT, ...) + -- Function: int gmp_vscanf (const char *FMT, va_list AP) + Read from the standard input `stdin'. + + -- Function: int gmp_fscanf (FILE *FP, const char *FMT, ...) + -- Function: int gmp_vfscanf (FILE *FP, const char *FMT, va_list AP) + Read from the stream FP. + + -- Function: int gmp_sscanf (const char *S, const char *FMT, ...) + -- Function: int gmp_vsscanf (const char *S, const char *FMT, va_list + AP) + Read from a null-terminated string S. + + The return value from each of these functions is the same as the +standard C99 `scanf', namely the number of fields successfully parsed +and stored. `%n' fields and fields read but suppressed by `*' don't +count towards the return value. + + If end of input (or a file error) is reached before a character for +a field or a literal, and if no previous non-suppressed fields have +matched, then the return value is `EOF' instead of 0. A whitespace +character in the format string is only an optional match and doesn't +induce an `EOF' in this fashion. Leading whitespace read and discarded +for a field don't count as characters for that field. + + For the GMP types, input parsing follows C99 rules, namely one +character of lookahead is used and characters are read while they +continue to meet the format requirements. If this doesn't provide a +complete number then the function terminates, with that field not +stored nor counted towards the return value. For instance with `mpf_t' +an input `1.23e-XYZ' would be read up to the `X' and that character +pushed back since it's not a digit. The string `1.23e-' would then be +considered invalid since an `e' must be followed by at least one digit. + + For the standard C types, in the current implementation GMP calls +the C library `scanf' functions, which might have looser rules about +what constitutes a valid input. + + Note that `gmp_sscanf' is the same as `gmp_fscanf' and only does one +character of lookahead when parsing. Although clearly it could look at +its entire input, it is deliberately made identical to `gmp_fscanf', +the same way C99 `sscanf' is the same as `fscanf'. + + +File: gmp.info, Node: C++ Formatted Input, Prev: Formatted Input Functions, Up: Formatted Input + +11.3 C++ Formatted Input +======================== + +The following functions are provided in `libgmpxx' (*note Headers and +Libraries::), which is built only if C++ support is enabled (*note +Build Options::). Prototypes are available from `'. + + -- Function: istream& operator>> (istream& STREAM, mpz_t ROP) + Read ROP from STREAM, using its `ios' formatting settings. + + -- Function: istream& operator>> (istream& STREAM, mpq_t ROP) + An integer like `123' will be read, or a fraction like `5/9'. No + whitespace is allowed around the `/'. If the fraction is not in + canonical form then `mpq_canonicalize' must be called (*note + Rational Number Functions::) before operating on it. + + As per integer input, an `0' or `0x' base indicator is read when + none of `ios::dec', `ios::oct' or `ios::hex' are set. This is + done separately for numerator and denominator, so that for instance + `0x10/11' is 16/11 and `0x10/0x11' is 16/17. + + -- Function: istream& operator>> (istream& STREAM, mpf_t ROP) + Read ROP from STREAM, using its `ios' formatting settings. + + Hex or octal floats are not supported, but might be in the future, + or perhaps it's best to accept only what the standard float + `operator>>' does. + + Note that digit grouping specified by the `istream' locale is +currently not accepted. Perhaps this will change in the future. + + + These operators mean that GMP types can be read in the usual C++ +way, for example, + + mpz_t z; + ... + cin >> z; + + But note that `istream' input (and `ostream' output, *note C++ +Formatted Output::) is the only overloading available for the GMP types +and that for instance using `+' with an `mpz_t' will have unpredictable +results. For classes with overloading, see *Note C++ Class Interface::. + + +File: gmp.info, Node: C++ Class Interface, Next: BSD Compatible Functions, Prev: Formatted Input, Up: Top + +12 C++ Class Interface +********************** + +This chapter describes the C++ class based interface to GMP. + + All GMP C language types and functions can be used in C++ programs, +since `gmp.h' has `extern "C"' qualifiers, but the class interface +offers overloaded functions and operators which may be more convenient. + + Due to the implementation of this interface, a reasonably recent C++ +compiler is required, one supporting namespaces, partial specialization +of templates and member templates. For GCC this means version 2.91 or +later. + + *Everything described in this chapter is to be considered preliminary +and might be subject to incompatible changes if some unforeseen +difficulty reveals itself.* + +* Menu: + +* C++ Interface General:: +* C++ Interface Integers:: +* C++ Interface Rationals:: +* C++ Interface Floats:: +* C++ Interface Random Numbers:: +* C++ Interface Limitations:: + + +File: gmp.info, Node: C++ Interface General, Next: C++ Interface Integers, Prev: C++ Class Interface, Up: C++ Class Interface + +12.1 C++ Interface General +========================== + +All the C++ classes and functions are available with + + #include + + Programs should be linked with the `libgmpxx' and `libgmp' +libraries. For example, + + g++ mycxxprog.cc -lgmpxx -lgmp + +The classes defined are + + -- Class: mpz_class + -- Class: mpq_class + -- Class: mpf_class + + The standard operators and various standard functions are overloaded +to allow arithmetic with these classes. For example, + + int + main (void) + { + mpz_class a, b, c; + + a = 1234; + b = "-5678"; + c = a+b; + cout << "sum is " << c << "\n"; + cout << "absolute value is " << abs(c) << "\n"; + + return 0; + } + + An important feature of the implementation is that an expression like +`a=b+c' results in a single call to the corresponding `mpz_add', +without using a temporary for the `b+c' part. Expressions which by +their nature imply intermediate values, like `a=b*c+d*e', still use +temporaries though. + + The classes can be freely intermixed in expressions, as can the +classes and the standard types `long', `unsigned long' and `double'. +Smaller types like `int' or `float' can also be intermixed, since C++ +will promote them. + + Note that `bool' is not accepted directly, but must be explicitly +cast to an `int' first. This is because C++ will automatically convert +any pointer to a `bool', so if GMP accepted `bool' it would make all +sorts of invalid class and pointer combinations compile but almost +certainly not do anything sensible. + + Conversions back from the classes to standard C++ types aren't done +automatically, instead member functions like `get_si' are provided (see +the following sections for details). + + Also there are no automatic conversions from the classes to the +corresponding GMP C types, instead a reference to the underlying C +object can be obtained with the following functions, + + -- Function: mpz_t mpz_class::get_mpz_t () + -- Function: mpq_t mpq_class::get_mpq_t () + -- Function: mpf_t mpf_class::get_mpf_t () + + These can be used to call a C function which doesn't have a C++ class +interface. For example to set `a' to the GCD of `b' and `c', + + mpz_class a, b, c; + ... + mpz_gcd (a.get_mpz_t(), b.get_mpz_t(), c.get_mpz_t()); + + In the other direction, a class can be initialized from the +corresponding GMP C type, or assigned to if an explicit constructor is +used. In both cases this makes a copy of the value, it doesn't create +any sort of association. For example, + + mpz_t z; + // ... init and calculate z ... + mpz_class x(z); + mpz_class y; + y = mpz_class (z); + + There are no namespace setups in `gmpxx.h', all types and functions +are simply put into the global namespace. This is what `gmp.h' has +done in the past, and continues to do for compatibility. The extras +provided by `gmpxx.h' follow GMP naming conventions and are unlikely to +clash with anything. + + +File: gmp.info, Node: C++ Interface Integers, Next: C++ Interface Rationals, Prev: C++ Interface General, Up: C++ Class Interface + +12.2 C++ Interface Integers +=========================== + + -- Function: void mpz_class::mpz_class (type N) + Construct an `mpz_class'. All the standard C++ types may be used, + except `long long' and `long double', and all the GMP C++ classes + can be used. Any necessary conversion follows the corresponding C + function, for example `double' follows `mpz_set_d' (*note + Assigning Integers::). + + -- Function: void mpz_class::mpz_class (mpz_t Z) + Construct an `mpz_class' from an `mpz_t'. The value in Z is + copied into the new `mpz_class', there won't be any permanent + association between it and Z. + + -- Function: void mpz_class::mpz_class (const char *S) + -- Function: void mpz_class::mpz_class (const char *S, int BASE = 0) + -- Function: void mpz_class::mpz_class (const string& S) + -- Function: void mpz_class::mpz_class (const string& S, int BASE = 0) + Construct an `mpz_class' converted from a string using + `mpz_set_str' (*note Assigning Integers::). + + If the string is not a valid integer, an `std::invalid_argument' + exception is thrown. The same applies to `operator='. + + -- Function: mpz_class operator/ (mpz_class A, mpz_class D) + -- Function: mpz_class operator% (mpz_class A, mpz_class D) + Divisions involving `mpz_class' round towards zero, as per the + `mpz_tdiv_q' and `mpz_tdiv_r' functions (*note Integer Division::). + This is the same as the C99 `/' and `%' operators. + + The `mpz_fdiv...' or `mpz_cdiv...' functions can always be called + directly if desired. For example, + + mpz_class q, a, d; + ... + mpz_fdiv_q (q.get_mpz_t(), a.get_mpz_t(), d.get_mpz_t()); + + -- Function: mpz_class abs (mpz_class OP1) + -- Function: int cmp (mpz_class OP1, type OP2) + -- Function: int cmp (type OP1, mpz_class OP2) + -- Function: bool mpz_class::fits_sint_p (void) + -- Function: bool mpz_class::fits_slong_p (void) + -- Function: bool mpz_class::fits_sshort_p (void) + -- Function: bool mpz_class::fits_uint_p (void) + -- Function: bool mpz_class::fits_ulong_p (void) + -- Function: bool mpz_class::fits_ushort_p (void) + -- Function: double mpz_class::get_d (void) + -- Function: long mpz_class::get_si (void) + -- Function: string mpz_class::get_str (int BASE = 10) + -- Function: unsigned long mpz_class::get_ui (void) + -- Function: int mpz_class::set_str (const char *STR, int BASE) + -- Function: int mpz_class::set_str (const string& STR, int BASE) + -- Function: int sgn (mpz_class OP) + -- Function: mpz_class sqrt (mpz_class OP) + These functions provide a C++ class interface to the corresponding + GMP C routines. + + `cmp' can be used with any of the classes or the standard C++ + types, except `long long' and `long double'. + + + Overloaded operators for combinations of `mpz_class' and `double' +are provided for completeness, but it should be noted that if the given +`double' is not an integer then the way any rounding is done is +currently unspecified. The rounding might take place at the start, in +the middle, or at the end of the operation, and it might change in the +future. + + Conversions between `mpz_class' and `double', however, are defined +to follow the corresponding C functions `mpz_get_d' and `mpz_set_d'. +And comparisons are always made exactly, as per `mpz_cmp_d'. + + +File: gmp.info, Node: C++ Interface Rationals, Next: C++ Interface Floats, Prev: C++ Interface Integers, Up: C++ Class Interface + +12.3 C++ Interface Rationals +============================ + +In all the following constructors, if a fraction is given then it +should be in canonical form, or if not then `mpq_class::canonicalize' +called. + + -- Function: void mpq_class::mpq_class (type OP) + -- Function: void mpq_class::mpq_class (integer NUM, integer DEN) + Construct an `mpq_class'. The initial value can be a single value + of any type, or a pair of integers (`mpz_class' or standard C++ + integer types) representing a fraction, except that `long long' + and `long double' are not supported. For example, + + mpq_class q (99); + mpq_class q (1.75); + mpq_class q (1, 3); + + -- Function: void mpq_class::mpq_class (mpq_t Q) + Construct an `mpq_class' from an `mpq_t'. The value in Q is + copied into the new `mpq_class', there won't be any permanent + association between it and Q. + + -- Function: void mpq_class::mpq_class (const char *S) + -- Function: void mpq_class::mpq_class (const char *S, int BASE = 0) + -- Function: void mpq_class::mpq_class (const string& S) + -- Function: void mpq_class::mpq_class (const string& S, int BASE = 0) + Construct an `mpq_class' converted from a string using + `mpq_set_str' (*note Initializing Rationals::). + + If the string is not a valid rational, an `std::invalid_argument' + exception is thrown. The same applies to `operator='. + + -- Function: void mpq_class::canonicalize () + Put an `mpq_class' into canonical form, as per *Note Rational + Number Functions::. All arithmetic operators require their + operands in canonical form, and will return results in canonical + form. + + -- Function: mpq_class abs (mpq_class OP) + -- Function: int cmp (mpq_class OP1, type OP2) + -- Function: int cmp (type OP1, mpq_class OP2) + -- Function: double mpq_class::get_d (void) + -- Function: string mpq_class::get_str (int BASE = 10) + -- Function: int mpq_class::set_str (const char *STR, int BASE) + -- Function: int mpq_class::set_str (const string& STR, int BASE) + -- Function: int sgn (mpq_class OP) + These functions provide a C++ class interface to the corresponding + GMP C routines. + + `cmp' can be used with any of the classes or the standard C++ + types, except `long long' and `long double'. + + -- Function: mpz_class& mpq_class::get_num () + -- Function: mpz_class& mpq_class::get_den () + Get a reference to an `mpz_class' which is the numerator or + denominator of an `mpq_class'. This can be used both for read and + write access. If the object returned is modified, it modifies the + original `mpq_class'. + + If direct manipulation might produce a non-canonical value, then + `mpq_class::canonicalize' must be called before further operations. + + -- Function: mpz_t mpq_class::get_num_mpz_t () + -- Function: mpz_t mpq_class::get_den_mpz_t () + Get a reference to the underlying `mpz_t' numerator or denominator + of an `mpq_class'. This can be passed to C functions expecting an + `mpz_t'. Any modifications made to the `mpz_t' will modify the + original `mpq_class'. + + If direct manipulation might produce a non-canonical value, then + `mpq_class::canonicalize' must be called before further operations. + + -- Function: istream& operator>> (istream& STREAM, mpq_class& ROP); + Read ROP from STREAM, using its `ios' formatting settings, the + same as `mpq_t operator>>' (*note C++ Formatted Input::). + + If the ROP read might not be in canonical form then + `mpq_class::canonicalize' must be called. + + +File: gmp.info, Node: C++ Interface Floats, Next: C++ Interface Random Numbers, Prev: C++ Interface Rationals, Up: C++ Class Interface + +12.4 C++ Interface Floats +========================= + +When an expression requires the use of temporary intermediate +`mpf_class' values, like `f=g*h+x*y', those temporaries will have the +same precision as the destination `f'. Explicit constructors can be +used if this doesn't suit. + + -- Function: mpf_class::mpf_class (type OP) + -- Function: mpf_class::mpf_class (type OP, unsigned long PREC) + Construct an `mpf_class'. Any standard C++ type can be used, + except `long long' and `long double', and any of the GMP C++ + classes can be used. + + If PREC is given, the initial precision is that value, in bits. If + PREC is not given, then the initial precision is determined by the + type of OP given. An `mpz_class', `mpq_class', or C++ builtin + type will give the default `mpf' precision (*note Initializing + Floats::). An `mpf_class' or expression will give the precision + of that value. The precision of a binary expression is the higher + of the two operands. + + mpf_class f(1.5); // default precision + mpf_class f(1.5, 500); // 500 bits (at least) + mpf_class f(x); // precision of x + mpf_class f(abs(x)); // precision of x + mpf_class f(-g, 1000); // 1000 bits (at least) + mpf_class f(x+y); // greater of precisions of x and y + + -- Function: void mpf_class::mpf_class (const char *S) + -- Function: void mpf_class::mpf_class (const char *S, unsigned long + PREC, int BASE = 0) + -- Function: void mpf_class::mpf_class (const string& S) + -- Function: void mpf_class::mpf_class (const string& S, unsigned long + PREC, int BASE = 0) + Construct an `mpf_class' converted from a string using + `mpf_set_str' (*note Assigning Floats::). If PREC is given, the + initial precision is that value, in bits. If not, the default + `mpf' precision (*note Initializing Floats::) is used. + + If the string is not a valid float, an `std::invalid_argument' + exception is thrown. The same applies to `operator='. + + -- Function: mpf_class& mpf_class::operator= (type OP) + Convert and store the given OP value to an `mpf_class' object. The + same types are accepted as for the constructors above. + + Note that `operator=' only stores a new value, it doesn't copy or + change the precision of the destination, instead the value is + truncated if necessary. This is the same as `mpf_set' etc. Note + in particular this means for `mpf_class' a copy constructor is not + the same as a default constructor plus assignment. + + mpf_class x (y); // x created with precision of y + + mpf_class x; // x created with default precision + x = y; // value truncated to that precision + + Applications using templated code may need to be careful about the + assumptions the code makes in this area, when working with + `mpf_class' values of various different or non-default precisions. + For instance implementations of the standard `complex' template + have been seen in both styles above, though of course `complex' is + normally only actually specified for use with the builtin float + types. + + -- Function: mpf_class abs (mpf_class OP) + -- Function: mpf_class ceil (mpf_class OP) + -- Function: int cmp (mpf_class OP1, type OP2) + -- Function: int cmp (type OP1, mpf_class OP2) + -- Function: bool mpf_class::fits_sint_p (void) + -- Function: bool mpf_class::fits_slong_p (void) + -- Function: bool mpf_class::fits_sshort_p (void) + -- Function: bool mpf_class::fits_uint_p (void) + -- Function: bool mpf_class::fits_ulong_p (void) + -- Function: bool mpf_class::fits_ushort_p (void) + -- Function: mpf_class floor (mpf_class OP) + -- Function: mpf_class hypot (mpf_class OP1, mpf_class OP2) + -- Function: double mpf_class::get_d (void) + -- Function: long mpf_class::get_si (void) + -- Function: string mpf_class::get_str (mp_exp_t& EXP, int BASE = 10, + size_t DIGITS = 0) + -- Function: unsigned long mpf_class::get_ui (void) + -- Function: int mpf_class::set_str (const char *STR, int BASE) + -- Function: int mpf_class::set_str (const string& STR, int BASE) + -- Function: int sgn (mpf_class OP) + -- Function: mpf_class sqrt (mpf_class OP) + -- Function: mpf_class trunc (mpf_class OP) + These functions provide a C++ class interface to the corresponding + GMP C routines. + + `cmp' can be used with any of the classes or the standard C++ + types, except `long long' and `long double'. + + The accuracy provided by `hypot' is not currently guaranteed. + + -- Function: mp_bitcnt_t mpf_class::get_prec () + -- Function: void mpf_class::set_prec (mp_bitcnt_t PREC) + -- Function: void mpf_class::set_prec_raw (mp_bitcnt_t PREC) + Get or set the current precision of an `mpf_class'. + + The restrictions described for `mpf_set_prec_raw' (*note + Initializing Floats::) apply to `mpf_class::set_prec_raw'. Note + in particular that the `mpf_class' must be restored to it's + allocated precision before being destroyed. This must be done by + application code, there's no automatic mechanism for it. + + +File: gmp.info, Node: C++ Interface Random Numbers, Next: C++ Interface Limitations, Prev: C++ Interface Floats, Up: C++ Class Interface + +12.5 C++ Interface Random Numbers +================================= + + -- Class: gmp_randclass + The C++ class interface to the GMP random number functions uses + `gmp_randclass' to hold an algorithm selection and current state, + as per `gmp_randstate_t'. + + -- Function: gmp_randclass::gmp_randclass (void (*RANDINIT) + (gmp_randstate_t, ...), ...) + Construct a `gmp_randclass', using a call to the given RANDINIT + function (*note Random State Initialization::). The arguments + expected are the same as RANDINIT, but with `mpz_class' instead of + `mpz_t'. For example, + + gmp_randclass r1 (gmp_randinit_default); + gmp_randclass r2 (gmp_randinit_lc_2exp_size, 32); + gmp_randclass r3 (gmp_randinit_lc_2exp, a, c, m2exp); + gmp_randclass r4 (gmp_randinit_mt); + + `gmp_randinit_lc_2exp_size' will fail if the size requested is too + big, an `std::length_error' exception is thrown in that case. + + -- Function: gmp_randclass::gmp_randclass (gmp_randalg_t ALG, ...) + Construct a `gmp_randclass' using the same parameters as + `gmp_randinit' (*note Random State Initialization::). This + function is obsolete and the above RANDINIT style should be + preferred. + + -- Function: void gmp_randclass::seed (unsigned long int S) + -- Function: void gmp_randclass::seed (mpz_class S) + Seed a random number generator. See *note Random Number + Functions::, for how to choose a good seed. + + -- Function: mpz_class gmp_randclass::get_z_bits (unsigned long BITS) + -- Function: mpz_class gmp_randclass::get_z_bits (mpz_class BITS) + Generate a random integer with a specified number of bits. + + -- Function: mpz_class gmp_randclass::get_z_range (mpz_class N) + Generate a random integer in the range 0 to N-1 inclusive. + + -- Function: mpf_class gmp_randclass::get_f () + -- Function: mpf_class gmp_randclass::get_f (unsigned long PREC) + Generate a random float F in the range 0 <= F < 1. F will be to + PREC bits precision, or if PREC is not given then to the precision + of the destination. For example, + + gmp_randclass r; + ... + mpf_class f (0, 512); // 512 bits precision + f = r.get_f(); // random number, 512 bits + + +File: gmp.info, Node: C++ Interface Limitations, Prev: C++ Interface Random Numbers, Up: C++ Class Interface + +12.6 C++ Interface Limitations +============================== + +`mpq_class' and Templated Reading + A generic piece of template code probably won't know that + `mpq_class' requires a `canonicalize' call if inputs read with + `operator>>' might be non-canonical. This can lead to incorrect + results. + + `operator>>' behaves as it does for reasons of efficiency. A + canonicalize can be quite time consuming on large operands, and is + best avoided if it's not necessary. + + But this potential difficulty reduces the usefulness of + `mpq_class'. Perhaps a mechanism to tell `operator>>' what to do + will be adopted in the future, maybe a preprocessor define, a + global flag, or an `ios' flag pressed into service. Or maybe, at + the risk of inconsistency, the `mpq_class' `operator>>' could + canonicalize and leave `mpq_t' `operator>>' not doing so, for use + on those occasions when that's acceptable. Send feedback or + alternate ideas to . + +Subclassing + Subclassing the GMP C++ classes works, but is not currently + recommended. + + Expressions involving subclasses resolve correctly (or seem to), + but in normal C++ fashion the subclass doesn't inherit + constructors and assignments. There's many of those in the GMP + classes, and a good way to reestablish them in a subclass is not + yet provided. + +Templated Expressions + A subtle difficulty exists when using expressions together with + application-defined template functions. Consider the following, + with `T' intended to be some numeric type, + + template + T fun (const T &, const T &); + + When used with, say, plain `mpz_class' variables, it works fine: + `T' is resolved as `mpz_class'. + + mpz_class f(1), g(2); + fun (f, g); // Good + + But when one of the arguments is an expression, it doesn't work. + + mpz_class f(1), g(2), h(3); + fun (f, g+h); // Bad + + This is because `g+h' ends up being a certain expression template + type internal to `gmpxx.h', which the C++ template resolution + rules are unable to automatically convert to `mpz_class'. The + workaround is simply to add an explicit cast. + + mpz_class f(1), g(2), h(3); + fun (f, mpz_class(g+h)); // Good + + Similarly, within `fun' it may be necessary to cast an expression + to type `T' when calling a templated `fun2'. + + template + void fun (T f, T g) + { + fun2 (f, f+g); // Bad + } + + template + void fun (T f, T g) + { + fun2 (f, T(f+g)); // Good + } + + +File: gmp.info, Node: BSD Compatible Functions, Next: Custom Allocation, Prev: C++ Class Interface, Up: Top + +13 Berkeley MP Compatible Functions +*********************************** + +These functions are intended to be fully compatible with the Berkeley MP +library which is available on many BSD derived U*ix systems. The +`--enable-mpbsd' option must be used when building GNU MP to make these +available (*note Installing GMP::). + + The original Berkeley MP library has a usage restriction: you cannot +use the same variable as both source and destination in a single +function call. The compatible functions in GNU MP do not share this +restriction--inputs and outputs may overlap. + + It is not recommended that new programs are written using these +functions. Apart from the incomplete set of functions, the interface +for initializing `MINT' objects is more error prone, and the `pow' +function collides with `pow' in `libm.a'. + + Include the header `mp.h' to get the definition of the necessary +types and functions. If you are on a BSD derived system, make sure to +include GNU `mp.h' if you are going to link the GNU `libmp.a' to your +program. This means that you probably need to give the `-I' +option to the compiler, where `' is the directory where you have +GNU `mp.h'. + + -- Function: MINT * itom (signed short int INITIAL_VALUE) + Allocate an integer consisting of a `MINT' object and dynamic limb + space. Initialize the integer to INITIAL_VALUE. Return a pointer + to the `MINT' object. + + -- Function: MINT * xtom (char *INITIAL_VALUE) + Allocate an integer consisting of a `MINT' object and dynamic limb + space. Initialize the integer from INITIAL_VALUE, a hexadecimal, + null-terminated C string. Return a pointer to the `MINT' object. + + -- Function: void move (MINT *SRC, MINT *DEST) + Set DEST to SRC by copying. Both variables must be previously + initialized. + + -- Function: void madd (MINT *SRC_1, MINT *SRC_2, MINT *DESTINATION) + Add SRC_1 and SRC_2 and put the sum in DESTINATION. + + -- Function: void msub (MINT *SRC_1, MINT *SRC_2, MINT *DESTINATION) + Subtract SRC_2 from SRC_1 and put the difference in DESTINATION. + + -- Function: void mult (MINT *SRC_1, MINT *SRC_2, MINT *DESTINATION) + Multiply SRC_1 and SRC_2 and put the product in DESTINATION. + + -- Function: void mdiv (MINT *DIVIDEND, MINT *DIVISOR, MINT *QUOTIENT, + MINT *REMAINDER) + -- Function: void sdiv (MINT *DIVIDEND, signed short int DIVISOR, MINT + *QUOTIENT, signed short int *REMAINDER) + Set QUOTIENT to DIVIDEND/DIVISOR, and REMAINDER to DIVIDEND mod + DIVISOR. The quotient is rounded towards zero; the remainder has + the same sign as the dividend unless it is zero. + + Some implementations of these functions work differently--or not + at all--for negative arguments. + + -- Function: void msqrt (MINT *OP, MINT *ROOT, MINT *REMAINDER) + Set ROOT to the truncated integer part of the square root of OP, + like `mpz_sqrt'. Set REMAINDER to OP-ROOT*ROOT, i.e. zero if OP + is a perfect square. + + If ROOT and REMAINDER are the same variable, the results are + undefined. + + -- Function: void pow (MINT *BASE, MINT *EXP, MINT *MOD, MINT *DEST) + Set DEST to (BASE raised to EXP) modulo MOD. + + Note that the name `pow' clashes with `pow' from the standard C + math library (*note Exponentiation and Logarithms: (libc)Exponents + and Logarithms.). An application will only be able to use one or + the other. + + -- Function: void rpow (MINT *BASE, signed short int EXP, MINT *DEST) + Set DEST to BASE raised to EXP. + + -- Function: void gcd (MINT *OP1, MINT *OP2, MINT *RES) + Set RES to the greatest common divisor of OP1 and OP2. + + -- Function: int mcmp (MINT *OP1, MINT *OP2) + Compare OP1 and OP2. Return a positive value if OP1 > OP2, zero + if OP1 = OP2, and a negative value if OP1 < OP2. + + -- Function: void min (MINT *DEST) + Input a decimal string from `stdin', and put the read integer in + DEST. SPC and TAB are allowed in the number string, and are + ignored. + + -- Function: void mout (MINT *SRC) + Output SRC to `stdout', as a decimal string. Also output a + newline. + + -- Function: char * mtox (MINT *OP) + Convert OP to a hexadecimal string, and return a pointer to the + string. The returned string is allocated using the default memory + allocation function, `malloc' by default. It will be + `strlen(str)+1' bytes, that being exactly enough for the string + and null-terminator. + + -- Function: void mfree (MINT *OP) + De-allocate, the space used by OP. *This function should only be + passed a value returned by `itom' or `xtom'.* + + +File: gmp.info, Node: Custom Allocation, Next: Language Bindings, Prev: BSD Compatible Functions, Up: Top + +14 Custom Allocation +******************** + +By default GMP uses `malloc', `realloc' and `free' for memory +allocation, and if they fail GMP prints a message to the standard error +output and terminates the program. + + Alternate functions can be specified, to allocate memory in a +different way or to have a different error action on running out of +memory. + + This feature is available in the Berkeley compatibility library +(*note BSD Compatible Functions::) as well as the main GMP library. + + -- Function: void mp_set_memory_functions ( + void *(*ALLOC_FUNC_PTR) (size_t), + void *(*REALLOC_FUNC_PTR) (void *, size_t, size_t), + void (*FREE_FUNC_PTR) (void *, size_t)) + Replace the current allocation functions from the arguments. If + an argument is `NULL', the corresponding default function is used. + + These functions will be used for all memory allocation done by + GMP, apart from temporary space from `alloca' if that function is + available and GMP is configured to use it (*note Build Options::). + + *Be sure to call `mp_set_memory_functions' only when there are no + active GMP objects allocated using the previous memory functions! + Usually that means calling it before any other GMP function.* + + The functions supplied should fit the following declarations: + + -- Function: void * allocate_function (size_t ALLOC_SIZE) + Return a pointer to newly allocated space with at least ALLOC_SIZE + bytes. + + -- Function: void * reallocate_function (void *PTR, size_t OLD_SIZE, + size_t NEW_SIZE) + Resize a previously allocated block PTR of OLD_SIZE bytes to be + NEW_SIZE bytes. + + The block may be moved if necessary or if desired, and in that + case the smaller of OLD_SIZE and NEW_SIZE bytes must be copied to + the new location. The return value is a pointer to the resized + block, that being the new location if moved or just PTR if not. + + PTR is never `NULL', it's always a previously allocated block. + NEW_SIZE may be bigger or smaller than OLD_SIZE. + + -- Function: void free_function (void *PTR, size_t SIZE) + De-allocate the space pointed to by PTR. + + PTR is never `NULL', it's always a previously allocated block of + SIZE bytes. + + A "byte" here means the unit used by the `sizeof' operator. + + The OLD_SIZE parameters to REALLOCATE_FUNCTION and FREE_FUNCTION are +passed for convenience, but of course can be ignored if not needed. +The default functions using `malloc' and friends for instance don't use +them. + + No error return is allowed from any of these functions, if they +return then they must have performed the specified operation. In +particular note that ALLOCATE_FUNCTION or REALLOCATE_FUNCTION mustn't +return `NULL'. + + Getting a different fatal error action is a good use for custom +allocation functions, for example giving a graphical dialog rather than +the default print to `stderr'. How much is possible when genuinely out +of memory is another question though. + + There's currently no defined way for the allocation functions to +recover from an error such as out of memory, they must terminate +program execution. A `longjmp' or throwing a C++ exception will have +undefined results. This may change in the future. + + GMP may use allocated blocks to hold pointers to other allocated +blocks. This will limit the assumptions a conservative garbage +collection scheme can make. + + Since the default GMP allocation uses `malloc' and friends, those +functions will be linked in even if the first thing a program does is an +`mp_set_memory_functions'. It's necessary to change the GMP sources if +this is a problem. + + + -- Function: void mp_get_memory_functions ( + void *(**ALLOC_FUNC_PTR) (size_t), + void *(**REALLOC_FUNC_PTR) (void *, size_t, size_t), + void (**FREE_FUNC_PTR) (void *, size_t)) + Get the current allocation functions, storing function pointers to + the locations given by the arguments. If an argument is `NULL', + that function pointer is not stored. + + For example, to get just the current free function, + + void (*freefunc) (void *, size_t); + + mp_get_memory_functions (NULL, NULL, &freefunc); + + +File: gmp.info, Node: Language Bindings, Next: Algorithms, Prev: Custom Allocation, Up: Top + +15 Language Bindings +******************** + +The following packages and projects offer access to GMP from languages +other than C, though perhaps with varying levels of functionality and +efficiency. + + +C++ + * GMP C++ class interface, *note C++ Class Interface:: + Straightforward interface, expression templates to eliminate + temporaries. + + * ALP `http://www-sop.inria.fr/saga/logiciels/ALP/' + Linear algebra and polynomials using templates. + + * Arithmos `http://www.win.ua.ac.be/~cant/arithmos/' + Rationals with infinities and square roots. + + * CLN `http://www.ginac.de/CLN/' + High level classes for arithmetic. + + * LiDIA `http://www.cdc.informatik.tu-darmstadt.de/TI/LiDIA/' + A C++ library for computational number theory. + + * Linbox `http://www.linalg.org/' + Sparse vectors and matrices. + + * NTL `http://www.shoup.net/ntl/' + A C++ number theory library. + +Fortran + * Omni F77 `http://phase.hpcc.jp/Omni/home.html' + Arbitrary precision floats. + +Haskell + * Glasgow Haskell Compiler `http://www.haskell.org/ghc/' + +Java + * Kaffe `http://www.kaffe.org/' + + * Kissme `http://kissme.sourceforge.net/' + +Lisp + * GNU Common Lisp `http://www.gnu.org/software/gcl/gcl.html' + + * Librep `http://librep.sourceforge.net/' + + * XEmacs (21.5.18 beta and up) `http://www.xemacs.org' + Optional big integers, rationals and floats using GMP. + +M4 + * GNU m4 betas `http://www.seindal.dk/rene/gnu/' + Optionally provides an arbitrary precision `mpeval'. + +ML + * MLton compiler `http://mlton.org/' + +Objective Caml + * MLGMP `http://www.di.ens.fr/~monniaux/programmes.html.en' + + * Numerix `http://pauillac.inria.fr/~quercia/' + Optionally using GMP. + +Oz + * Mozart `http://www.mozart-oz.org/' + +Pascal + * GNU Pascal Compiler `http://www.gnu-pascal.de/' + GMP unit. + + * Numerix `http://pauillac.inria.fr/~quercia/' + For Free Pascal, optionally using GMP. + +Perl + * GMP module, see `demos/perl' in the GMP sources (*note + Demonstration Programs::). + + * Math::GMP `http://www.cpan.org/' + Compatible with Math::BigInt, but not as many functions as + the GMP module above. + + * Math::BigInt::GMP `http://www.cpan.org/' + Plug Math::GMP into normal Math::BigInt operations. + +Pike + * mpz module in the standard distribution, + `http://pike.ida.liu.se/' + +Prolog + * SWI Prolog `http://www.swi-prolog.org/' + Arbitrary precision floats. + +Python + * mpz module in the standard distribution, + `http://www.python.org/' + + * GMPY `http://gmpy.sourceforge.net/' + +Scheme + * GNU Guile (upcoming 1.8) + `http://www.gnu.org/software/guile/guile.html' + + * RScheme `http://www.rscheme.org/' + + * STklos `http://www.stklos.org/' + +Smalltalk + * GNU Smalltalk + `http://www.smalltalk.org/versions/GNUSmalltalk.html' + +Other + * Axiom `http://savannah.nongnu.org/projects/axiom' + Computer algebra using GCL. + + * DrGenius `http://drgenius.seul.org/' + Geometry system and mathematical programming language. + + * GiNaC `http://www.ginac.de/' + C++ computer algebra using CLN. + + * GOO `http://www.googoogaga.org/' + Dynamic object oriented language. + + * Maxima `http://www.ma.utexas.edu/users/wfs/maxima.html' + Macsyma computer algebra using GCL. + + * Q `http://q-lang.sourceforge.net/' + Equational programming system. + + * Regina `http://regina.sourceforge.net/' + Topological calculator. + + * Yacas `http://www.xs4all.nl/~apinkus/yacas.html' + Yet another computer algebra system. + + + +File: gmp.info, Node: Algorithms, Next: Internals, Prev: Language Bindings, Up: Top + +16 Algorithms +************* + +This chapter is an introduction to some of the algorithms used for +various GMP operations. The code is likely to be hard to understand +without knowing something about the algorithms. + + Some GMP internals are mentioned, but applications that expect to be +compatible with future GMP releases should take care to use only the +documented functions. + +* Menu: + +* Multiplication Algorithms:: +* Division Algorithms:: +* Greatest Common Divisor Algorithms:: +* Powering Algorithms:: +* Root Extraction Algorithms:: +* Radix Conversion Algorithms:: +* Other Algorithms:: +* Assembly Coding:: + + +File: gmp.info, Node: Multiplication Algorithms, Next: Division Algorithms, Prev: Algorithms, Up: Algorithms + +16.1 Multiplication +=================== + +NxN limb multiplications and squares are done using one of five +algorithms, as the size N increases. + + Algorithm Threshold + Basecase (none) + Karatsuba `MUL_TOOM22_THRESHOLD' + Toom-3 `MUL_TOOM33_THRESHOLD' + Toom-4 `MUL_TOOM44_THRESHOLD' + FFT `MUL_FFT_THRESHOLD' + + Similarly for squaring, with the `SQR' thresholds. + + NxM multiplications of operands with different sizes above +`MUL_TOOM22_THRESHOLD' are currently done by special Toom-inspired +algorithms or directly with FFT, depending on operand size (*note +Unbalanced Multiplication::). + +* Menu: + +* Basecase Multiplication:: +* Karatsuba Multiplication:: +* Toom 3-Way Multiplication:: +* Toom 4-Way Multiplication:: +* FFT Multiplication:: +* Other Multiplication:: +* Unbalanced Multiplication:: + + +File: gmp.info, Node: Basecase Multiplication, Next: Karatsuba Multiplication, Prev: Multiplication Algorithms, Up: Multiplication Algorithms + +16.1.1 Basecase Multiplication +------------------------------ + +Basecase NxM multiplication is a straightforward rectangular set of +cross-products, the same as long multiplication done by hand and for +that reason sometimes known as the schoolbook or grammar school method. +This is an O(N*M) algorithm. See Knuth section 4.3.1 algorithm M +(*note References::), and the `mpn/generic/mul_basecase.c' code. + + Assembly implementations of `mpn_mul_basecase' are essentially the +same as the generic C code, but have all the usual assembly tricks and +obscurities introduced for speed. + + A square can be done in roughly half the time of a multiply, by +using the fact that the cross products above and below the diagonal are +the same. A triangle of products below the diagonal is formed, doubled +(left shift by one bit), and then the products on the diagonal added. +This can be seen in `mpn/generic/sqr_basecase.c'. Again the assembly +implementations take essentially the same approach. + + u0 u1 u2 u3 u4 + +---+---+---+---+---+ + u0 | d | | | | | + +---+---+---+---+---+ + u1 | | d | | | | + +---+---+---+---+---+ + u2 | | | d | | | + +---+---+---+---+---+ + u3 | | | | d | | + +---+---+---+---+---+ + u4 | | | | | d | + +---+---+---+---+---+ + + In practice squaring isn't a full 2x faster than multiplying, it's +usually around 1.5x. Less than 1.5x probably indicates +`mpn_sqr_basecase' wants improving on that CPU. + + On some CPUs `mpn_mul_basecase' can be faster than the generic C +`mpn_sqr_basecase' on some small sizes. `SQR_BASECASE_THRESHOLD' is +the size at which to use `mpn_sqr_basecase', this will be zero if that +routine should be used always. + + +File: gmp.info, Node: Karatsuba Multiplication, Next: Toom 3-Way Multiplication, Prev: Basecase Multiplication, Up: Multiplication Algorithms + +16.1.2 Karatsuba Multiplication +------------------------------- + +The Karatsuba multiplication algorithm is described in Knuth section +4.3.3 part A, and various other textbooks. A brief description is +given here. + + The inputs x and y are treated as each split into two parts of equal +length (or the most significant part one limb shorter if N is odd). + + high low + +----------+----------+ + | x1 | x0 | + +----------+----------+ + + +----------+----------+ + | y1 | y0 | + +----------+----------+ + + Let b be the power of 2 where the split occurs, ie. if x0 is k limbs +(y0 the same) then b=2^(k*mp_bits_per_limb). With that x=x1*b+x0 and +y=y1*b+y0, and the following holds, + + x*y = (b^2+b)*x1*y1 - b*(x1-x0)*(y1-y0) + (b+1)*x0*y0 + + This formula means doing only three multiplies of (N/2)x(N/2) limbs, +whereas a basecase multiply of NxN limbs is equivalent to four +multiplies of (N/2)x(N/2). The factors (b^2+b) etc represent the +positions where the three products must be added. + + high low + +--------+--------+ +--------+--------+ + | x1*y1 | | x0*y0 | + +--------+--------+ +--------+--------+ + +--------+--------+ + add | x1*y1 | + +--------+--------+ + +--------+--------+ + add | x0*y0 | + +--------+--------+ + +--------+--------+ + sub | (x1-x0)*(y1-y0) | + +--------+--------+ + + The term (x1-x0)*(y1-y0) is best calculated as an absolute value, +and the sign used to choose to add or subtract. Notice the sum +high(x0*y0)+low(x1*y1) occurs twice, so it's possible to do 5*k limb +additions, rather than 6*k, but in GMP extra function call overheads +outweigh the saving. + + Squaring is similar to multiplying, but with x=y the formula reduces +to an equivalent with three squares, + + x^2 = (b^2+b)*x1^2 - b*(x1-x0)^2 + (b+1)*x0^2 + + The final result is accumulated from those three squares the same +way as for the three multiplies above. The middle term (x1-x0)^2 is now +always positive. + + A similar formula for both multiplying and squaring can be +constructed with a middle term (x1+x0)*(y1+y0). But those sums can +exceed k limbs, leading to more carry handling and additions than the +form above. + + Karatsuba multiplication is asymptotically an O(N^1.585) algorithm, +the exponent being log(3)/log(2), representing 3 multiplies each 1/2 +the size of the inputs. This is a big improvement over the basecase +multiply at O(N^2) and the advantage soon overcomes the extra additions +Karatsuba performs. `MUL_TOOM22_THRESHOLD' can be as little as 10 +limbs. The `SQR' threshold is usually about twice the `MUL'. + + The basecase algorithm will take a time of the form M(N) = a*N^2 + +b*N + c and the Karatsuba algorithm K(N) = 3*M(N/2) + d*N + e, which +expands to K(N) = 3/4*a*N^2 + 3/2*b*N + 3*c + d*N + e. The factor 3/4 +for a means per-crossproduct speedups in the basecase code will +increase the threshold since they benefit M(N) more than K(N). And +conversely the 3/2 for b means linear style speedups of b will increase +the threshold since they benefit K(N) more than M(N). The latter can +be seen for instance when adding an optimized `mpn_sqr_diagonal' to +`mpn_sqr_basecase'. Of course all speedups reduce total time, and in +that sense the algorithm thresholds are merely of academic interest. + + +File: gmp.info, Node: Toom 3-Way Multiplication, Next: Toom 4-Way Multiplication, Prev: Karatsuba Multiplication, Up: Multiplication Algorithms + +16.1.3 Toom 3-Way Multiplication +-------------------------------- + +The Karatsuba formula is the simplest case of a general approach to +splitting inputs that leads to both Toom and FFT algorithms. A +description of Toom can be found in Knuth section 4.3.3, with an +example 3-way calculation after Theorem A. The 3-way form used in GMP +is described here. + + The operands are each considered split into 3 pieces of equal length +(or the most significant part 1 or 2 limbs shorter than the other two). + + high low + +----------+----------+----------+ + | x2 | x1 | x0 | + +----------+----------+----------+ + + +----------+----------+----------+ + | y2 | y1 | y0 | + +----------+----------+----------+ + +These parts are treated as the coefficients of two polynomials + + X(t) = x2*t^2 + x1*t + x0 + Y(t) = y2*t^2 + y1*t + y0 + + Let b equal the power of 2 which is the size of the x0, x1, y0 and +y1 pieces, ie. if they're k limbs each then b=2^(k*mp_bits_per_limb). +With this x=X(b) and y=Y(b). + + Let a polynomial W(t)=X(t)*Y(t) and suppose its coefficients are + + W(t) = w4*t^4 + w3*t^3 + w2*t^2 + w1*t + w0 + + The w[i] are going to be determined, and when they are they'll give +the final result using w=W(b), since x*y=X(b)*Y(b)=W(b). The +coefficients will be roughly b^2 each, and the final W(b) will be an +addition like, + + high low + +-------+-------+ + | w4 | + +-------+-------+ + +--------+-------+ + | w3 | + +--------+-------+ + +--------+-------+ + | w2 | + +--------+-------+ + +--------+-------+ + | w1 | + +--------+-------+ + +-------+-------+ + | w0 | + +-------+-------+ + + The w[i] coefficients could be formed by a simple set of cross +products, like w4=x2*y2, w3=x2*y1+x1*y2, w2=x2*y0+x1*y1+x0*y2 etc, but +this would need all nine x[i]*y[j] for i,j=0,1,2, and would be +equivalent merely to a basecase multiply. Instead the following +approach is used. + + X(t) and Y(t) are evaluated and multiplied at 5 points, giving +values of W(t) at those points. In GMP the following points are used, + + Point Value + t=0 x0 * y0, which gives w0 immediately + t=1 (x2+x1+x0) * (y2+y1+y0) + t=-1 (x2-x1+x0) * (y2-y1+y0) + t=2 (4*x2+2*x1+x0) * (4*y2+2*y1+y0) + t=inf x2 * y2, which gives w4 immediately + + At t=-1 the values can be negative and that's handled using the +absolute values and tracking the sign separately. At t=inf the value +is actually X(t)*Y(t)/t^4 in the limit as t approaches infinity, but +it's much easier to think of as simply x2*y2 giving w4 immediately +(much like x0*y0 at t=0 gives w0 immediately). + + Each of the points substituted into W(t)=w4*t^4+...+w0 gives a +linear combination of the w[i] coefficients, and the value of those +combinations has just been calculated. + + W(0) = w0 + W(1) = w4 + w3 + w2 + w1 + w0 + W(-1) = w4 - w3 + w2 - w1 + w0 + W(2) = 16*w4 + 8*w3 + 4*w2 + 2*w1 + w0 + W(inf) = w4 + + This is a set of five equations in five unknowns, and some +elementary linear algebra quickly isolates each w[i]. This involves +adding or subtracting one W(t) value from another, and a couple of +divisions by powers of 2 and one division by 3, the latter using the +special `mpn_divexact_by3' (*note Exact Division::). + + The conversion of W(t) values to the coefficients is interpolation. +A polynomial of degree 4 like W(t) is uniquely determined by values +known at 5 different points. The points are arbitrary and can be +chosen to make the linear equations come out with a convenient set of +steps for quickly isolating the w[i]. + + Squaring follows the same procedure as multiplication, but there's +only one X(t) and it's evaluated at the 5 points, and those values +squared to give values of W(t). The interpolation is then identical, +and in fact the same `toom3_interpolate' subroutine is used for both +squaring and multiplying. + + Toom-3 is asymptotically O(N^1.465), the exponent being +log(5)/log(3), representing 5 recursive multiplies of 1/3 the original +size each. This is an improvement over Karatsuba at O(N^1.585), though +Toom does more work in the evaluation and interpolation and so it only +realizes its advantage above a certain size. + + Near the crossover between Toom-3 and Karatsuba there's generally a +range of sizes where the difference between the two is small. +`MUL_TOOM33_THRESHOLD' is a somewhat arbitrary point in that range and +successive runs of the tune program can give different values due to +small variations in measuring. A graph of time versus size for the two +shows the effect, see `tune/README'. + + At the fairly small sizes where the Toom-3 thresholds occur it's +worth remembering that the asymptotic behaviour for Karatsuba and +Toom-3 can't be expected to make accurate predictions, due of course to +the big influence of all sorts of overheads, and the fact that only a +few recursions of each are being performed. Even at large sizes +there's a good chance machine dependent effects like cache architecture +will mean actual performance deviates from what might be predicted. + + The formula given for the Karatsuba algorithm (*note Karatsuba +Multiplication::) has an equivalent for Toom-3 involving only five +multiplies, but this would be complicated and unenlightening. + + An alternate view of Toom-3 can be found in Zuras (*note +References::), using a vector to represent the x and y splits and a +matrix multiplication for the evaluation and interpolation stages. The +matrix inverses are not meant to be actually used, and they have +elements with values much greater than in fact arise in the +interpolation steps. The diagram shown for the 3-way is attractive, +but again doesn't have to be implemented that way and for example with +a bit of rearrangement just one division by 6 can be done. + + +File: gmp.info, Node: Toom 4-Way Multiplication, Next: FFT Multiplication, Prev: Toom 3-Way Multiplication, Up: Multiplication Algorithms + +16.1.4 Toom 4-Way Multiplication +-------------------------------- + +Karatsuba and Toom-3 split the operands into 2 and 3 coefficients, +respectively. Toom-4 analogously splits the operands into 4 +coefficients. Using the notation from the section on Toom-3 +multiplication, we form two polynomials: + + X(t) = x3*t^3 + x2*t^2 + x1*t + x0 + Y(t) = y3*t^3 + y2*t^2 + y1*t + y0 + + X(t) and Y(t) are evaluated and multiplied at 7 points, giving +values of W(t) at those points. In GMP the following points are used, + + Point Value + t=0 x0 * y0, which gives w0 immediately + t=1/2 (x3+2*x2+4*x1+8*x0) * (y3+2*y2+4*y1+8*y0) + t=-1/2 (-x3+2*x2-4*x1+8*x0) * (-y3+2*y2-4*y1+8*y0) + t=1 (x3+x2+x1+x0) * (y3+y2+y1+y0) + t=-1 (-x3+x2-x1+x0) * (-y3+y2-y1+y0) + t=2 (8*x3+4*x2+2*x1+x0) * (8*y3+4*y2+2*y1+y0) + t=inf x3 * y3, which gives w6 immediately + + The number of additions and subtractions for Toom-4 is much larger +than for Toom-3. But several subexpressions occur multiple times, for +example x2+x0, occurs for both t=1 and t=-1. + + Toom-4 is asymptotically O(N^1.404), the exponent being +log(7)/log(4), representing 7 recursive multiplies of 1/4 the original +size each. + + +File: gmp.info, Node: FFT Multiplication, Next: Other Multiplication, Prev: Toom 4-Way Multiplication, Up: Multiplication Algorithms + +16.1.5 FFT Multiplication +------------------------- + +At large to very large sizes a Fermat style FFT multiplication is used, +following Scho"nhage and Strassen (*note References::). Descriptions +of FFTs in various forms can be found in many textbooks, for instance +Knuth section 4.3.3 part C or Lipson chapter IX. A brief description +of the form used in GMP is given here. + + The multiplication done is x*y mod 2^N+1, for a given N. A full +product x*y is obtained by choosing N>=bits(x)+bits(y) and padding x +and y with high zero limbs. The modular product is the native form for +the algorithm, so padding to get a full product is unavoidable. + + The algorithm follows a split, evaluate, pointwise multiply, +interpolate and combine similar to that described above for Karatsuba +and Toom-3. A k parameter controls the split, with an FFT-k splitting +into 2^k pieces of M=N/2^k bits each. N must be a multiple of +(2^k)*mp_bits_per_limb so the split falls on limb boundaries, avoiding +bit shifts in the split and combine stages. + + The evaluations, pointwise multiplications, and interpolation, are +all done modulo 2^N'+1 where N' is 2M+k+3 rounded up to a multiple of +2^k and of `mp_bits_per_limb'. The results of interpolation will be +the following negacyclic convolution of the input pieces, and the +choice of N' ensures these sums aren't truncated. + + --- + \ b + w[n] = / (-1) * x[i] * y[j] + --- + i+j==b*2^k+n + b=0,1 + + The points used for the evaluation are g^i for i=0 to 2^k-1 where +g=2^(2N'/2^k). g is a 2^k'th root of unity mod 2^N'+1, which produces +necessary cancellations at the interpolation stage, and it's also a +power of 2 so the fast Fourier transforms used for the evaluation and +interpolation do only shifts, adds and negations. + + The pointwise multiplications are done modulo 2^N'+1 and either +recurse into a further FFT or use a plain multiplication (Toom-3, +Karatsuba or basecase), whichever is optimal at the size N'. The +interpolation is an inverse fast Fourier transform. The resulting set +of sums of x[i]*y[j] are added at appropriate offsets to give the final +result. + + Squaring is the same, but x is the only input so it's one transform +at the evaluate stage and the pointwise multiplies are squares. The +interpolation is the same. + + For a mod 2^N+1 product, an FFT-k is an O(N^(k/(k-1))) algorithm, +the exponent representing 2^k recursed modular multiplies each +1/2^(k-1) the size of the original. Each successive k is an asymptotic +improvement, but overheads mean each is only faster at bigger and +bigger sizes. In the code, `MUL_FFT_TABLE' and `SQR_FFT_TABLE' are the +thresholds where each k is used. Each new k effectively swaps some +multiplying for some shifts, adds and overheads. + + A mod 2^N+1 product can be formed with a normal NxN->2N bit multiply +plus a subtraction, so an FFT and Toom-3 etc can be compared directly. +A k=4 FFT at O(N^1.333) can be expected to be the first faster than +Toom-3 at O(N^1.465). In practice this is what's found, with +`MUL_FFT_MODF_THRESHOLD' and `SQR_FFT_MODF_THRESHOLD' being between 300 +and 1000 limbs, depending on the CPU. So far it's been found that only +very large FFTs recurse into pointwise multiplies above these sizes. + + When an FFT is to give a full product, the change of N to 2N doesn't +alter the theoretical complexity for a given k, but for the purposes of +considering where an FFT might be first used it can be assumed that the +FFT is recursing into a normal multiply and that on that basis it's +doing 2^k recursed multiplies each 1/2^(k-2) the size of the inputs, +making it O(N^(k/(k-2))). This would mean k=7 at O(N^1.4) would be the +first FFT faster than Toom-3. In practice `MUL_FFT_THRESHOLD' and +`SQR_FFT_THRESHOLD' have been found to be in the k=8 range, somewhere +between 3000 and 10000 limbs. + + The way N is split into 2^k pieces and then 2M+k+3 is rounded up to +a multiple of 2^k and `mp_bits_per_limb' means that when +2^k>=mp_bits_per_limb the effective N is a multiple of 2^(2k-1) bits. +The +k+3 means some values of N just under such a multiple will be +rounded to the next. The complexity calculations above assume that a +favourable size is used, meaning one which isn't padded through +rounding, and it's also assumed that the extra +k+3 bits are negligible +at typical FFT sizes. + + The practical effect of the 2^(2k-1) constraint is to introduce a +step-effect into measured speeds. For example k=8 will round N up to a +multiple of 32768 bits, so for a 32-bit limb there'll be 512 limb +groups of sizes for which `mpn_mul_n' runs at the same speed. Or for +k=9 groups of 2048 limbs, k=10 groups of 8192 limbs, etc. In practice +it's been found each k is used at quite small multiples of its size +constraint and so the step effect is quite noticeable in a time versus +size graph. + + The threshold determinations currently measure at the mid-points of +size steps, but this is sub-optimal since at the start of a new step it +can happen that it's better to go back to the previous k for a while. +Something more sophisticated for `MUL_FFT_TABLE' and `SQR_FFT_TABLE' +will be needed. + + +File: gmp.info, Node: Other Multiplication, Next: Unbalanced Multiplication, Prev: FFT Multiplication, Up: Multiplication Algorithms + +16.1.6 Other Multiplication +--------------------------- + +The Toom algorithms described above (*note Toom 3-Way Multiplication::, +*note Toom 4-Way Multiplication::) generalizes to split into an +arbitrary number of pieces, as per Knuth section 4.3.3 algorithm C. +This is not currently used. The notes here are merely for interest. + + In general a split into r+1 pieces is made, and evaluations and +pointwise multiplications done at 2*r+1 points. A 4-way split does 7 +pointwise multiplies, 5-way does 9, etc. Asymptotically an (r+1)-way +algorithm is O(N^(log(2*r+1)/log(r+1))). Only the pointwise +multiplications count towards big-O complexity, but the time spent in +the evaluate and interpolate stages grows with r and has a significant +practical impact, with the asymptotic advantage of each r realized only +at bigger and bigger sizes. The overheads grow as O(N*r), whereas in +an r=2^k FFT they grow only as O(N*log(r)). + + Knuth algorithm C evaluates at points 0,1,2,...,2*r, but exercise 4 +uses -r,...,0,...,r and the latter saves some small multiplies in the +evaluate stage (or rather trades them for additions), and has a further +saving of nearly half the interpolate steps. The idea is to separate +odd and even final coefficients and then perform algorithm C steps C7 +and C8 on them separately. The divisors at step C7 become j^2 and the +multipliers at C8 become 2*t*j-j^2. + + Splitting odd and even parts through positive and negative points +can be thought of as using -1 as a square root of unity. If a 4th root +of unity was available then a further split and speedup would be +possible, but no such root exists for plain integers. Going to complex +integers with i=sqrt(-1) doesn't help, essentially because in Cartesian +form it takes three real multiplies to do a complex multiply. The +existence of 2^k'th roots of unity in a suitable ring or field lets the +fast Fourier transform keep splitting and get to O(N*log(r)). + + Floating point FFTs use complex numbers approximating Nth roots of +unity. Some processors have special support for such FFTs. But these +are not used in GMP since it's very difficult to guarantee an exact +result (to some number of bits). An occasional difference of 1 in the +last bit might not matter to a typical signal processing algorithm, but +is of course of vital importance to GMP. + + +File: gmp.info, Node: Unbalanced Multiplication, Prev: Other Multiplication, Up: Multiplication Algorithms + +16.1.7 Unbalanced Multiplication +-------------------------------- + +Multiplication of operands with different sizes, both below +`MUL_TOOM22_THRESHOLD' are done with plain schoolbook multiplication +(*note Basecase Multiplication::). + + For really large operands, we invoke FFT directly. + + For operands between these sizes, we use Toom inspired algorithms +suggested by Alberto Zanoni and Marco Bodrato. The idea is to split +the operands into polynomials of different degree. GMP currently +splits the smaller operand onto 2 coefficients, i.e., a polynomial of +degree 1, but the larger operand can be split into 2, 3, or 4 +coefficients, i.e., a polynomial of degree 1 to 3. + + +File: gmp.info, Node: Division Algorithms, Next: Greatest Common Divisor Algorithms, Prev: Multiplication Algorithms, Up: Algorithms + +16.2 Division Algorithms +======================== + +* Menu: + +* Single Limb Division:: +* Basecase Division:: +* Divide and Conquer Division:: +* Block-Wise Barrett Division:: +* Exact Division:: +* Exact Remainder:: +* Small Quotient Division:: + + +File: gmp.info, Node: Single Limb Division, Next: Basecase Division, Prev: Division Algorithms, Up: Division Algorithms + +16.2.1 Single Limb Division +--------------------------- + +Nx1 division is implemented using repeated 2x1 divisions from high to +low, either with a hardware divide instruction or a multiplication by +inverse, whichever is best on a given CPU. + + The multiply by inverse follows "Improved division by invariant +integers" by Mo"ller and Granlund (*note References::) and is +implemented as `udiv_qrnnd_preinv' in `gmp-impl.h'. The idea is to +have a fixed-point approximation to 1/d (see `invert_limb') and then +multiply by the high limb (plus one bit) of the dividend to get a +quotient q. With d normalized (high bit set), q is no more than 1 too +small. Subtracting q*d from the dividend gives a remainder, and +reveals whether q or q-1 is correct. + + The result is a division done with two multiplications and four or +five arithmetic operations. On CPUs with low latency multipliers this +can be much faster than a hardware divide, though the cost of +calculating the inverse at the start may mean it's only better on +inputs bigger than say 4 or 5 limbs. + + When a divisor must be normalized, either for the generic C +`__udiv_qrnnd_c' or the multiply by inverse, the division performed is +actually a*2^k by d*2^k where a is the dividend and k is the power +necessary to have the high bit of d*2^k set. The bit shifts for the +dividend are usually accomplished "on the fly" meaning by extracting +the appropriate bits at each step. Done this way the quotient limbs +come out aligned ready to store. When only the remainder is wanted, an +alternative is to take the dividend limbs unshifted and calculate r = a +mod d*2^k followed by an extra final step r*2^k mod d*2^k. This can +help on CPUs with poor bit shifts or few registers. + + The multiply by inverse can be done two limbs at a time. The +calculation is basically the same, but the inverse is two limbs and the +divisor treated as if padded with a low zero limb. This means more +work, since the inverse will need a 2x2 multiply, but the four 1x1s to +do that are independent and can therefore be done partly or wholly in +parallel. Likewise for a 2x1 calculating q*d. The net effect is to +process two limbs with roughly the same two multiplies worth of latency +that one limb at a time gives. This extends to 3 or 4 limbs at a time, +though the extra work to apply the inverse will almost certainly soon +reach the limits of multiplier throughput. + + A similar approach in reverse can be taken to process just half a +limb at a time if the divisor is only a half limb. In this case the +1x1 multiply for the inverse effectively becomes two (1/2)x1 for each +limb, which can be a saving on CPUs with a fast half limb multiply, or +in fact if the only multiply is a half limb, and especially if it's not +pipelined. + + +File: gmp.info, Node: Basecase Division, Next: Divide and Conquer Division, Prev: Single Limb Division, Up: Division Algorithms + +16.2.2 Basecase Division +------------------------ + +Basecase NxM division is like long division done by hand, but in base +2^mp_bits_per_limb. See Knuth section 4.3.1 algorithm D, and +`mpn/generic/sb_divrem_mn.c'. + + Briefly stated, while the dividend remains larger than the divisor, +a high quotient limb is formed and the Nx1 product q*d subtracted at +the top end of the dividend. With a normalized divisor (most +significant bit set), each quotient limb can be formed with a 2x1 +division and a 1x1 multiplication plus some subtractions. The 2x1 +division is by the high limb of the divisor and is done either with a +hardware divide or a multiply by inverse (the same as in *Note Single +Limb Division::) whichever is faster. Such a quotient is sometimes one +too big, requiring an addback of the divisor, but that happens rarely. + + With Q=N-M being the number of quotient limbs, this is an O(Q*M) +algorithm and will run at a speed similar to a basecase QxM +multiplication, differing in fact only in the extra multiply and divide +for each of the Q quotient limbs. + + +File: gmp.info, Node: Divide and Conquer Division, Next: Block-Wise Barrett Division, Prev: Basecase Division, Up: Division Algorithms + +16.2.3 Divide and Conquer Division +---------------------------------- + +For divisors larger than `DC_DIV_QR_THRESHOLD', division is done by +dividing. Or to be precise by a recursive divide and conquer algorithm +based on work by Moenck and Borodin, Jebelean, and Burnikel and Ziegler +(*note References::). + + The algorithm consists essentially of recognising that a 2NxN +division can be done with the basecase division algorithm (*note +Basecase Division::), but using N/2 limbs as a base, not just a single +limb. This way the multiplications that arise are (N/2)x(N/2) and can +take advantage of Karatsuba and higher multiplication algorithms (*note +Multiplication Algorithms::). The two "digits" of the quotient are +formed by recursive Nx(N/2) divisions. + + If the (N/2)x(N/2) multiplies are done with a basecase multiplication +then the work is about the same as a basecase division, but with more +function call overheads and with some subtractions separated from the +multiplies. These overheads mean that it's only when N/2 is above +`MUL_TOOM22_THRESHOLD' that divide and conquer is of use. + + `DC_DIV_QR_THRESHOLD' is based on the divisor size N, so it will be +somewhere above twice `MUL_TOOM22_THRESHOLD', but how much above +depends on the CPU. An optimized `mpn_mul_basecase' can lower +`DC_DIV_QR_THRESHOLD' a little by offering a ready-made advantage over +repeated `mpn_submul_1' calls. + + Divide and conquer is asymptotically O(M(N)*log(N)) where M(N) is +the time for an NxN multiplication done with FFTs. The actual time is +a sum over multiplications of the recursed sizes, as can be seen near +the end of section 2.2 of Burnikel and Ziegler. For example, within +the Toom-3 range, divide and conquer is 2.63*M(N). With higher +algorithms the M(N) term improves and the multiplier tends to log(N). +In practice, at moderate to large sizes, a 2NxN division is about 2 to +4 times slower than an NxN multiplication. + + +File: gmp.info, Node: Block-Wise Barrett Division, Next: Exact Division, Prev: Divide and Conquer Division, Up: Division Algorithms + +16.2.4 Block-Wise Barrett Division +---------------------------------- + +For the largest divisions, a block-wise Barrett division algorithm is +used. Here, the divisor is inverted to a precision determined by the +relative size of the dividend and divisor. Blocks of quotient limbs +are then generated by multiplying blocks from the dividend by the +inverse. + + Our block-wise algorithm computes a smaller inverse than in the +plain Barrett algorithm. For a 2n/n division, the inverse will be just +ceil(n/2) limbs. + + +File: gmp.info, Node: Exact Division, Next: Exact Remainder, Prev: Block-Wise Barrett Division, Up: Division Algorithms + +16.2.5 Exact Division +--------------------- + +A so-called exact division is when the dividend is known to be an exact +multiple of the divisor. Jebelean's exact division algorithm uses this +knowledge to make some significant optimizations (*note References::). + + The idea can be illustrated in decimal for example with 368154 +divided by 543. Because the low digit of the dividend is 4, the low +digit of the quotient must be 8. This is arrived at from 4*7 mod 10, +using the fact 7 is the modular inverse of 3 (the low digit of the +divisor), since 3*7 == 1 mod 10. So 8*543=4344 can be subtracted from +the dividend leaving 363810. Notice the low digit has become zero. + + The procedure is repeated at the second digit, with the next +quotient digit 7 (7 == 1*7 mod 10), subtracting 7*543=3801, leaving +325800. And finally at the third digit with quotient digit 6 (8*7 mod +10), subtracting 6*543=3258 leaving 0. So the quotient is 678. + + Notice however that the multiplies and subtractions don't need to +extend past the low three digits of the dividend, since that's enough +to determine the three quotient digits. For the last quotient digit no +subtraction is needed at all. On a 2NxN division like this one, only +about half the work of a normal basecase division is necessary. + + For an NxM exact division producing Q=N-M quotient limbs, the saving +over a normal basecase division is in two parts. Firstly, each of the +Q quotient limbs needs only one multiply, not a 2x1 divide and +multiply. Secondly, the crossproducts are reduced when Q>M to +Q*M-M*(M+1)/2, or when Q<=M to Q*(Q-1)/2. Notice the savings are +complementary. If Q is big then many divisions are saved, or if Q is +small then the crossproducts reduce to a small number. + + The modular inverse used is calculated efficiently by `binvert_limb' +in `gmp-impl.h'. This does four multiplies for a 32-bit limb, or six +for a 64-bit limb. `tune/modlinv.c' has some alternate implementations +that might suit processors better at bit twiddling than multiplying. + + The sub-quadratic exact division described by Jebelean in "Exact +Division with Karatsuba Complexity" is not currently implemented. It +uses a rearrangement similar to the divide and conquer for normal +division (*note Divide and Conquer Division::), but operating from low +to high. A further possibility not currently implemented is +"Bidirectional Exact Integer Division" by Krandick and Jebelean which +forms quotient limbs from both the high and low ends of the dividend, +and can halve once more the number of crossproducts needed in a 2NxN +division. + + A special case exact division by 3 exists in `mpn_divexact_by3', +supporting Toom-3 multiplication and `mpq' canonicalizations. It forms +quotient digits with a multiply by the modular inverse of 3 (which is +`0xAA..AAB') and uses two comparisons to determine a borrow for the next +limb. The multiplications don't need to be on the dependent chain, as +long as the effect of the borrows is applied, which can help chips with +pipelined multipliers. + + +File: gmp.info, Node: Exact Remainder, Next: Small Quotient Division, Prev: Exact Division, Up: Division Algorithms + +16.2.6 Exact Remainder +---------------------- + +If the exact division algorithm is done with a full subtraction at each +stage and the dividend isn't a multiple of the divisor, then low zero +limbs are produced but with a remainder in the high limbs. For +dividend a, divisor d, quotient q, and b = 2^mp_bits_per_limb, this +remainder r is of the form + + a = q*d + r*b^n + + n represents the number of zero limbs produced by the subtractions, +that being the number of limbs produced for q. r will be in the range +0<=rb*r+u2 condition appropriately relaxed. + + +File: gmp.info, Node: Greatest Common Divisor Algorithms, Next: Powering Algorithms, Prev: Division Algorithms, Up: Algorithms + +16.3 Greatest Common Divisor +============================ + +* Menu: + +* Binary GCD:: +* Lehmer's Algorithm:: +* Subquadratic GCD:: +* Extended GCD:: +* Jacobi Symbol:: + + +File: gmp.info, Node: Binary GCD, Next: Lehmer's Algorithm, Prev: Greatest Common Divisor Algorithms, Up: Greatest Common Divisor Algorithms + +16.3.1 Binary GCD +----------------- + +At small sizes GMP uses an O(N^2) binary style GCD. This is described +in many textbooks, for example Knuth section 4.5.2 algorithm B. It +simply consists of successively reducing odd operands a and b using + + a,b = abs(a-b),min(a,b) + strip factors of 2 from a + + The Euclidean GCD algorithm, as per Knuth algorithms E and A, +repeatedly computes the quotient q = floor(a/b) and replaces a,b by v, +u - q v. The binary algorithm has so far been found to be faster than +the Euclidean algorithm everywhere. One reason the binary method does +well is that the implied quotient at each step is usually small, so +often only one or two subtractions are needed to get the same effect as +a division. Quotients 1, 2 and 3 for example occur 67.7% of the time, +see Knuth section 4.5.3 Theorem E. + + When the implied quotient is large, meaning b is much smaller than +a, then a division is worthwhile. This is the basis for the initial a +mod b reductions in `mpn_gcd' and `mpn_gcd_1' (the latter for both Nx1 +and 1x1 cases). But after that initial reduction, big quotients occur +too rarely to make it worth checking for them. + + + The final 1x1 GCD in `mpn_gcd_1' is done in the generic C code as +described above. For two N-bit operands, the algorithm takes about +0.68 iterations per bit. For optimum performance some attention needs +to be paid to the way the factors of 2 are stripped from a. + + Firstly it may be noted that in twos complement the number of low +zero bits on a-b is the same as b-a, so counting or testing can begin on +a-b without waiting for abs(a-b) to be determined. + + A loop stripping low zero bits tends not to branch predict well, +since the condition is data dependent. But on average there's only a +few low zeros, so an option is to strip one or two bits arithmetically +then loop for more (as done for AMD K6). Or use a lookup table to get +a count for several bits then loop for more (as done for AMD K7). An +alternative approach is to keep just one of a or b odd and iterate + + a,b = abs(a-b), min(a,b) + a = a/2 if even + b = b/2 if even + + This requires about 1.25 iterations per bit, but stripping of a +single bit at each step avoids any branching. Repeating the bit strip +reduces to about 0.9 iterations per bit, which may be a worthwhile +tradeoff. + + Generally with the above approaches a speed of perhaps 6 cycles per +bit can be achieved, which is still not terribly fast with for instance +a 64-bit GCD taking nearly 400 cycles. It's this sort of time which +means it's not usually advantageous to combine a set of divisibility +tests into a GCD. + + Currently, the binary algorithm is used for GCD only when N < 3. + + +File: gmp.info, Node: Lehmer's Algorithm, Next: Subquadratic GCD, Prev: Binary GCD, Up: Greatest Common Divisor Algorithms + +16.3.2 Lehmer's algorithm +------------------------- + +Lehmer's improvement of the Euclidean algorithms is based on the +observation that the initial part of the quotient sequence depends only +on the most significant parts of the inputs. The variant of Lehmer's +algorithm used in GMP splits off the most significant two limbs, as +suggested, e.g., in "A Double-Digit Lehmer-Euclid Algorithm" by +Jebelean (*note References::). The quotients of two double-limb inputs +are collected as a 2 by 2 matrix with single-limb elements. This is +done by the function `mpn_hgcd2'. The resulting matrix is applied to +the inputs using `mpn_mul_1' and `mpn_submul_1'. Each iteration usually +reduces the inputs by almost one limb. In the rare case of a large +quotient, no progress can be made by examining just the most +significant two limbs, and the quotient is computing using plain +division. + + The resulting algorithm is asymptotically O(N^2), just as the +Euclidean algorithm and the binary algorithm. The quadratic part of the +work are the calls to `mpn_mul_1' and `mpn_submul_1'. For small sizes, +the linear work is also significant. There are roughly N calls to the +`mpn_hgcd2' function. This function uses a couple of important +optimizations: + + * It uses the same relaxed notion of correctness as `mpn_hgcd' (see + next section). This means that when called with the most + significant two limbs of two large numbers, the returned matrix + does not always correspond exactly to the initial quotient + sequence for the two large numbers; the final quotient may + sometimes be one off. + + * It takes advantage of the fact the quotients are usually small. + The division operator is not used, since the corresponding + assembler instruction is very slow on most architectures. (This + code could probably be improved further, it uses many branches + that are unfriendly to prediction). + + * It switches from double-limb calculations to single-limb + calculations half-way through, when the input numbers have been + reduced in size from two limbs to one and a half. + + + +File: gmp.info, Node: Subquadratic GCD, Next: Extended GCD, Prev: Lehmer's Algorithm, Up: Greatest Common Divisor Algorithms + +16.3.3 Subquadratic GCD +----------------------- + +For inputs larger than `GCD_DC_THRESHOLD', GCD is computed via the HGCD +(Half GCD) function, as a generalization to Lehmer's algorithm. + + Let the inputs a,b be of size N limbs each. Put S = floor(N/2) + 1. +Then HGCD(a,b) returns a transformation matrix T with non-negative +elements, and reduced numbers (c;d) = T^-1 (a;b). The reduced numbers +c,d must be larger than S limbs, while their difference abs(c-d) must +fit in S limbs. The matrix elements will also be of size roughly N/2. + + The HGCD base case uses Lehmer's algorithm, but with the above stop +condition that returns reduced numbers and the corresponding +transformation matrix half-way through. For inputs larger than +`HGCD_THRESHOLD', HGCD is computed recursively, using the divide and +conquer algorithm in "On Scho"nhage's algorithm and subquadratic +integer GCD computation" by Mo"ller (*note References::). The recursive +algorithm consists of these main steps. + + * Call HGCD recursively, on the most significant N/2 limbs. Apply the + resulting matrix T_1 to the full numbers, reducing them to a size + just above 3N/2. + + * Perform a small number of division or subtraction steps to reduce + the numbers to size below 3N/2. This is essential mainly for the + unlikely case of large quotients. + + * Call HGCD recursively, on the most significant N/2 limbs of the + reduced numbers. Apply the resulting matrix T_2 to the full + numbers, reducing them to a size just above N/2. + + * Compute T = T_1 T_2. + + * Perform a small number of division and subtraction steps to + satisfy the requirements, and return. + + GCD is then implemented as a loop around HGCD, similarly to Lehmer's +algorithm. Where Lehmer repeatedly chops off the top two limbs, calls +`mpn_hgcd2', and applies the resulting matrix to the full numbers, the +subquadratic GCD chops off the most significant third of the limbs (the +proportion is a tuning parameter, and 1/3 seems to be more efficient +than, e.g, 1/2), calls `mpn_hgcd', and applies the resulting matrix. +Once the input numbers are reduced to size below `GCD_DC_THRESHOLD', +Lehmer's algorithm is used for the rest of the work. + + The asymptotic running time of both HGCD and GCD is O(M(N)*log(N)), +where M(N) is the time for multiplying two N-limb numbers. + + +File: gmp.info, Node: Extended GCD, Next: Jacobi Symbol, Prev: Subquadratic GCD, Up: Greatest Common Divisor Algorithms + +16.3.4 Extended GCD +------------------- + +The extended GCD function, or GCDEXT, calculates gcd(a,b) and also +cofactors x and y satisfying a*x+b*y=gcd(a,b). All the algorithms used +for plain GCD are extended to handle this case. The binary algorithm is +used only for single-limb GCDEXT. Lehmer's algorithm is used for sizes +up to `GCDEXT_DC_THRESHOLD'. Above this threshold, GCDEXT is +implemented as a loop around HGCD, but with more book-keeping to keep +track of the cofactors. This gives the same asymptotic running time as +for GCD and HGCD, O(M(N)*log(N)) + + One difference to plain GCD is that while the inputs a and b are +reduced as the algorithm proceeds, the cofactors x and y grow in size. +This makes the tuning of the chopping-point more difficult. The current +code chops off the most significant half of the inputs for the call to +HGCD in the first iteration, and the most significant two thirds for +the remaining calls. This strategy could surely be improved. Also the +stop condition for the loop, where Lehmer's algorithm is invoked once +the inputs are reduced below `GCDEXT_DC_THRESHOLD', could maybe be +improved by taking into account the current size of the cofactors. + + +File: gmp.info, Node: Jacobi Symbol, Prev: Extended GCD, Up: Greatest Common Divisor Algorithms + +16.3.5 Jacobi Symbol +-------------------- + +`mpz_jacobi' and `mpz_kronecker' are currently implemented with a +simple binary algorithm similar to that described for the GCDs (*note +Binary GCD::). They're not very fast when both inputs are large. +Lehmer's multi-step improvement or a binary based multi-step algorithm +is likely to be better. + + When one operand fits a single limb, and that includes +`mpz_kronecker_ui' and friends, an initial reduction is done with +either `mpn_mod_1' or `mpn_modexact_1_odd', followed by the binary +algorithm on a single limb. The binary algorithm is well suited to a +single limb, and the whole calculation in this case is quite efficient. + + In all the routines sign changes for the result are accumulated +using some bit twiddling, avoiding table lookups or conditional jumps. +