+++ /dev/null
-This is gmp.info, produced by makeinfo version 6.7 from gmp.texi.
-
-This manual describes how to install and use the GNU multiple precision
-arithmetic library, version 6.2.1.
-
- Copyright 1991, 1993-2016, 2018-2020 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
-
-\1f
-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 6.2.1.
-
- Copyright 1991, 1993-2016, 2018-2020 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.
-* 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::
-
-\1f
-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.
-
- More precisely, the GNU MP library is dual licensed, under the
-conditions of the GNU Lesser General Public License version 3 (see
-'COPYING.LESSERv3'), or the GNU General Public License version 2 (see
-'COPYINGv2'). This is the recipient's choice, and the recipient also
-has the additional option of applying later versions of these licenses.
-(The reason for this dual licensing is to make it possible to use the
-library with programs which are licensed under GPL version 2, but which
-for historical or other reasons do not allow use under later versions of
-the GPL).
-
- Programs which are not part of the library itself, such as
-demonstration programs and the GMP testsuite, are licensed under the
-terms of the GNU General Public License version 3 (see 'COPYINGv3'), or
-any later version.
-
-\1f
-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 Cortex-A9, Cortex-A15, and
-generic ARM, DEC Alpha 21064, 21164, and 21264, AMD K8 and K10 (sold
-under many brands, e.g. Athlon64, Phenom, Opteron) Bulldozer, and
-Bobcat, Intel Pentium, Pentium Pro/II/III, Pentium 4, Core2, Nehalem,
-Sandy bridge, Haswell, generic x86, Intel IA-64, Motorola/IBM PowerPC 32
-and 64 such as POWER970, POWER5, POWER6, and POWER7, MIPS 32-bit and
-64-bit, SPARC 32-bit ad 64-bit with special support for all UltraSPARC
-models. There is also assembly code for many obsolete CPUs.
-
-For up-to-date information on GMP, please see the GMP web pages at
-
- <https://gmplib.org/>
-
-The latest version of the library is available at
-
- <https://ftp.gnu.org/gnu/gmp/>
-
- Many sites around the world mirror 'ftp.gnu.org', please use a mirror
-near you, see <https://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
-
- <https://gmplib.org/mailman/listinfo/>.
-
- The proper place for bug reports is <gmp-bugs@gmplib.org>. 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.
-
-\1f
-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
-<gmp-bugs@gmplib.org>. 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::
-
-\1f
-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-6.2.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' is
- architecture-dependent since it encodes 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.ac' 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: arm, sh, sh2, vax,
-
- 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 the configure
- '--disable-assembly'.
-
- 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.
-
-'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=<choice>'
- GMP allocates temporary workspace using one of the following three
- methods, which can be selected with for instance
- '--enable-alloca=malloc-reentrant'.
-
- * 'alloca' - C library or compiler builtin.
- * 'malloc-reentrant' - the heap, in a re-entrant fashion.
- * 'malloc-notreentrant' - the heap, with global variables.
-
- For convenience, the following choices are also available.
- '--disable-alloca' is the same as '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,
- higher degree 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.
-
-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.
-
-\1f
-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.)
-
- 'ABI=x32'
- The x32 ABI uses 64-bit limbs but 32-bit pointers. Like the
- 64-bit ABI, it makes full use of the chip's arithmetic
- capabilities. This ABI is not supported by all operating
- systems.
-
- gcc -mx32
-
-
-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=mode64'
- 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
-
- On 64-bit GNU/Linux, BSD, and Mac OS X/Darwin systems, the
- 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 for systems where the true
- 64-bit ABI is unavailable. No special compiler options are
- typically needed for applications. This ABI is not available
- under AIX.
-
- 'ABI=32'
- This is the basic 32-bit PowerPC ABI, with a 32-bit limb. No
- special compiler options are needed for applications.
-
- GMP's speed is greatest for the 'mode64' ABI, the 'mode32' ABI is
- 2nd best. In 'ABI=32' only the 32-bit ISA is used and this doesn't
- make full use of a 64-bit chip.
-
-
-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
-
-\1f
-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'.
-
-\1f
-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.
-
-FreeBSD 7.x, 8.x, 9.0, 9.1, 9.2
- 'm4' in these releases of FreeBSD has an eval function which
- ignores its 2nd and 3rd arguments, which 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 FreeBSD 9.3 and 10.0, so either upgrade or use GNU m4. Note
- that the FreeBSD package system installs GNU m4 under the name
- 'gm4', which GMP cannot guess.
-
-FreeBSD 7.x, 8.x, 9.x
- GMP releases starting with 6.0 do not support 'ABI=32' on
- FreeBSD/amd64 prior to release 10.0 of the system. The cause is a
- broken 'limits.h', which GMP no longer works around.
-
-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.
-
- <https://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'.
-
-NetBSD 5.x
- 'm4' in these releases of NetBSD has an eval function which ignores
- its 2nd and 3rd arguments, which 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
- NetBSD 6, so either upgrade or use GNU m4. Note that the NetBSD
- package system installs GNU m4 under the name 'gm4', which GMP
- cannot guess.
-
-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 ('--disable-assembly'),
- 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 '--disable-assembly'.
-
-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 '--disable-assembly' 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.
-
-\1f
-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 <https://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.
-
-\1f
-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 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.
-
-\1f
-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::
-
-\1f
-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 <gmp.h>
-
- Note however that prototypes for GMP functions with 'FILE *'
-parameters are only provided if '<stdio.h>' is included too.
-
- #include <stdio.h>
- #include <gmp.h>
-
- Likewise '<stdarg.h>' is required for prototypes with 'va_list'
-parameters, such as 'gmp_vprintf'. And '<obstack.h>' for prototypes
-with 'struct obstack' parameters, such as 'gmp_obstack_printf', when
-available.
-
- All programs using GMP must link against the 'libgmp' library. On a
-typical Unix-like system this can be done with '-lgmp', for example
-
- gcc myprogram.c -lgmp
-
- GMP C++ functions are in a separate 'libgmpxx' library. This is
-built and installed if C++ support has been enabled (*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.
-
-\1f
-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.
-
-\1f
-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 35
- 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 70
- functions is this class. (*note Floating-point Functions::)
-
- 4. 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 60 (hard-to-use) functions in this
- class. (*note Low-level Functions::)
-
- 5. Miscellaneous functions. Functions for setting up custom
- allocation and functions for generating random numbers. (*note
- Custom Allocation::, and *note Random Number Functions::)
-
-\1f
-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.
-
- 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);
- }
-
- GMP types like 'mpz_t' are implemented as one-element arrays of
-certain structures. Declaring a variable creates an object with the
-fields GMP needs, but variables are normally manipulated by using the
-pointer to the object. For both behavior and efficiency reasons, it is
-discouraged to make copies of the GMP object itself (either directly or
-via aggregate objects containing such GMP objects). If copies are done,
-all of them must be used read-only; using a copy as the output of some
-function will invalidate all the other copies. 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.
-
-\1f
-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 that when 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;
- }
-
- Our function 'foo' works even if its caller 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.
-
- Since GMP types are implemented as one-element arrays, using a GMP
-variable as a parameter passes a pointer to the object. Hence the
-call-by-reference.
-
-\1f
-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::.
-
-\1f
-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 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.
-
-\1f
-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 "6.2.1". Note that the format "i.j" was
- used, before version 4.3.0, when k was zero.
-
- -- Macro: __GMP_CC
- -- Macro: __GMP_CFLAGS
- The compiler and compiler flags, respectively, used when compiling
- GMP, as strings.
-
-\1f
-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 5.x, 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.
-
- * 'mpn_bdivmod', documented as preliminary in GMP 4, has been
- removed.
-
- 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 5.
-Please see the GMP 2 manual for details.
-
-\1f
-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.
-
-\1f
-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 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.
-
-\1f
-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://cs.ecs.baylor.edu/~donahoo/tools/ccmalloc/>
- <http://dmalloc.com/>
- <https://wiki.gnome.org/Apps/MemProf>
-
- 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-6.2.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 '--disable-assembly'
- 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 --disable-assembly CFLAGS=-g
-
- For C++, add '--enable-cxx CXXFLAGS=-g'.
-
-Checker
- The GCC checker (<https://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 --disable-assembly CC=checkergcc
-
- '--disable-assembly' 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
- Valgrind (<http://valgrind.org/>) is a memory checker for x86, ARM,
- MIPS, PowerPC, and S/390. 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.
-
- Valgrind does not always support every possible instruction, in
- particular ones recently added to an ISA. Valgrind might therefore
- be incompatible with a recent GMP or even a less recent GMP which
- is compiled using a recent GCC.
-
- GMP's assembly code sometimes promotes a read of the limbs to some
- larger size, for efficiency. GMP will do this even at the start
- and end of a multilimb operand, using naturally aligned operations
- on the larger type. This may lead to benign reads outside of
- allocated areas, triggering complaints from Valgrind. Valgrind's
- option '--partial-loads-ok=yes' should help.
-
-Other Problems
- Any suspected bug in GMP itself should be isolated to make sure
- it's not an application problem, see *note Reporting Bugs::.
-
-\1f
-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
-
- <https://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.
-
-\1f
-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 https://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 https://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 <gmp.h>])
-
-\1f
-File: gmp.info, Node: Emacs, Prev: Autoconf, Up: GMP Basics
-
-3.15 Emacs
-==========
-
-<C-h C-i> ('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)))))
-
-\1f
-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 <https://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 'configure' options you used when building GMP, if any.
-
- * The output from 'configure', as printed to stdout, with any options
- used.
-
- * 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-<file>.s'.
-
- Please make an effort to produce a self-contained report, with
-something definite that can be tested or debugged. Vague queries or
-piecemeal messages are difficult to act on and don't help the
-development effort.
-
- It is not uncommon that an observed problem is actually due to a bug
-in the compiler; the GMP code tends to explore interesting corners in
-compilers.
-
- If your bug report is good, we will do our best to help you get a
-corrected version of the library; if the bug report is poor, we won't do
-anything about it (except maybe ask you to send a better report).
-
- Send your report to: <gmp-bugs@gmplib.org>.
-
- If you think something in this manual is unclear, or downright
-incorrect, or if the language needs to be improved, please send a note
-to the same address.
-
-\1f
-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::
-
-\1f
-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.
-
- While N defines 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.
-
- In preparation for an operation, GMP often allocates one limb more
- than ultimately needed. To make sure GMP will not perform
- reallocation for X, you need to add the number of bits in
- 'mp_limb_t' to N.
-
- -- 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.
-
-\1f
-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, const 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, const mpq_t OP)
- -- Function: void mpz_set_f (mpz_t ROP, const 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, const 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.
-
-\1f
-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, const 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, const 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.)
-
-\1f
-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 (const 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 (const 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 (const mpz_t OP)
- Convert OP to a 'double', truncating if necessary (i.e. 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, const mpz_t
- OP)
- Convert OP to a 'double', truncating if necessary (i.e. 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
- (libc)Normalization Functions::).
-
- -- Function: char * mpz_get_str (char *STR, int BASE, const 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.
-
-\1f
-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, const mpz_t OP1, const mpz_t OP2)
- -- Function: void mpz_add_ui (mpz_t ROP, const mpz_t OP1, unsigned long
- int OP2)
- Set ROP to OP1 + OP2.
-
- -- Function: void mpz_sub (mpz_t ROP, const mpz_t OP1, const mpz_t OP2)
- -- Function: void mpz_sub_ui (mpz_t ROP, const mpz_t OP1, unsigned long
- int OP2)
- -- Function: void mpz_ui_sub (mpz_t ROP, unsigned long int OP1, const
- mpz_t OP2)
- Set ROP to OP1 - OP2.
-
- -- Function: void mpz_mul (mpz_t ROP, const mpz_t OP1, const mpz_t OP2)
- -- Function: void mpz_mul_si (mpz_t ROP, const mpz_t OP1, long int OP2)
- -- Function: void mpz_mul_ui (mpz_t ROP, const mpz_t OP1, unsigned long
- int OP2)
- Set ROP to OP1 times OP2.
-
- -- Function: void mpz_addmul (mpz_t ROP, const mpz_t OP1, const mpz_t
- OP2)
- -- Function: void mpz_addmul_ui (mpz_t ROP, const mpz_t OP1, unsigned
- long int OP2)
- Set ROP to ROP + OP1 times OP2.
-
- -- Function: void mpz_submul (mpz_t ROP, const mpz_t OP1, const mpz_t
- OP2)
- -- Function: void mpz_submul_ui (mpz_t ROP, const mpz_t OP1, unsigned
- long int OP2)
- Set ROP to ROP - OP1 times OP2.
-
- -- Function: void mpz_mul_2exp (mpz_t ROP, const 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, const mpz_t OP)
- Set ROP to -OP.
-
- -- Function: void mpz_abs (mpz_t ROP, const mpz_t OP)
- Set ROP to the absolute value of OP.
-
-\1f
-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, const mpz_t N, const mpz_t D)
- -- Function: void mpz_cdiv_r (mpz_t R, const mpz_t N, const mpz_t D)
- -- Function: void mpz_cdiv_qr (mpz_t Q, mpz_t R, const mpz_t N, const
- mpz_t D)
-
- -- Function: unsigned long int mpz_cdiv_q_ui (mpz_t Q, const mpz_t N,
- unsigned long int D)
- -- Function: unsigned long int mpz_cdiv_r_ui (mpz_t R, const mpz_t N,
- unsigned long int D)
- -- Function: unsigned long int mpz_cdiv_qr_ui (mpz_t Q, mpz_t R,
- const mpz_t N, unsigned long int D)
- -- Function: unsigned long int mpz_cdiv_ui (const mpz_t N,
- unsigned long int D)
-
- -- Function: void mpz_cdiv_q_2exp (mpz_t Q, const mpz_t N,
- mp_bitcnt_t B)
- -- Function: void mpz_cdiv_r_2exp (mpz_t R, const mpz_t N,
- mp_bitcnt_t B)
-
- -- Function: void mpz_fdiv_q (mpz_t Q, const mpz_t N, const mpz_t D)
- -- Function: void mpz_fdiv_r (mpz_t R, const mpz_t N, const mpz_t D)
- -- Function: void mpz_fdiv_qr (mpz_t Q, mpz_t R, const mpz_t N, const
- mpz_t D)
-
- -- Function: unsigned long int mpz_fdiv_q_ui (mpz_t Q, const mpz_t N,
- unsigned long int D)
- -- Function: unsigned long int mpz_fdiv_r_ui (mpz_t R, const mpz_t N,
- unsigned long int D)
- -- Function: unsigned long int mpz_fdiv_qr_ui (mpz_t Q, mpz_t R,
- const mpz_t N, unsigned long int D)
- -- Function: unsigned long int mpz_fdiv_ui (const mpz_t N,
- unsigned long int D)
-
- -- Function: void mpz_fdiv_q_2exp (mpz_t Q, const mpz_t N,
- mp_bitcnt_t B)
- -- Function: void mpz_fdiv_r_2exp (mpz_t R, const mpz_t N,
- mp_bitcnt_t B)
-
- -- Function: void mpz_tdiv_q (mpz_t Q, const mpz_t N, const mpz_t D)
- -- Function: void mpz_tdiv_r (mpz_t R, const mpz_t N, const mpz_t D)
- -- Function: void mpz_tdiv_qr (mpz_t Q, mpz_t R, const mpz_t N, const
- mpz_t D)
-
- -- Function: unsigned long int mpz_tdiv_q_ui (mpz_t Q, const mpz_t N,
- unsigned long int D)
- -- Function: unsigned long int mpz_tdiv_r_ui (mpz_t R, const mpz_t N,
- unsigned long int D)
- -- Function: unsigned long int mpz_tdiv_qr_ui (mpz_t Q, mpz_t R,
- const mpz_t N, unsigned long int D)
- -- Function: unsigned long int mpz_tdiv_ui (const mpz_t N,
- unsigned long int D)
-
- -- Function: void mpz_tdiv_q_2exp (mpz_t Q, const mpz_t N,
- mp_bitcnt_t B)
- -- Function: void mpz_tdiv_r_2exp (mpz_t R, const 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)<abs(D).
-
- The 'q' functions calculate only the quotient, the 'r' functions
- only the remainder, and the 'qr' functions calculate both. Note
- that for 'qr' the same variable cannot be passed for both Q and R,
- or results will be unpredictable.
-
- For the 'ui' variants the return value is the remainder, and in
- fact returning the remainder is all the 'div_ui' functions do. For
- 'tdiv' and 'cdiv' the remainder can be negative, so for those the
- return value is the absolute value of the remainder.
-
- For the '2exp' variants the divisor is 2^B. These functions are
- implemented as right shifts and bit masks, but of course they round
- the same as the other functions.
-
- For positive N both 'mpz_fdiv_q_2exp' and 'mpz_tdiv_q_2exp' are
- simple bitwise right shifts. For negative N, 'mpz_fdiv_q_2exp' is
- effectively an arithmetic right shift treating N as twos complement
- the same as the bitwise logical functions do, whereas
- 'mpz_tdiv_q_2exp' effectively treats N as sign and magnitude.
-
- -- Function: void mpz_mod (mpz_t R, const mpz_t N, const mpz_t D)
- -- Function: unsigned long int mpz_mod_ui (mpz_t R, const mpz_t N,
- unsigned long int D)
- Set R to N 'mod' D. The sign of the divisor is ignored; the result
- is always non-negative.
-
- 'mpz_mod_ui' is identical to 'mpz_fdiv_r_ui' above, returning the
- remainder as well as setting R. See 'mpz_fdiv_ui' above if only
- the return value is wanted.
-
- -- Function: void mpz_divexact (mpz_t Q, const mpz_t N, const mpz_t D)
- -- Function: void mpz_divexact_ui (mpz_t Q, const mpz_t N, unsigned
- long D)
- Set Q to N/D. These functions produce correct results only when it
- is known in advance that D divides N.
-
- These routines are much faster than the other division functions,
- and are the best choice when exact division is known to occur, for
- example reducing a rational to lowest terms.
-
- -- Function: int mpz_divisible_p (const mpz_t N, const mpz_t D)
- -- Function: int mpz_divisible_ui_p (const mpz_t N, unsigned long int
- D)
- -- Function: int mpz_divisible_2exp_p (const mpz_t N, mp_bitcnt_t B)
- Return non-zero if N is exactly divisible by D, or in the case of
- 'mpz_divisible_2exp_p' by 2^B.
-
- N is divisible by D if there exists an integer Q satisfying N =
- Q*D. Unlike the other division functions, D=0 is accepted and
- following the rule it can be seen that only 0 is considered
- divisible by 0.
-
- -- Function: int mpz_congruent_p (const mpz_t N, const mpz_t C, const
- mpz_t D)
- -- Function: int mpz_congruent_ui_p (const mpz_t N, unsigned long int
- C, unsigned long int D)
- -- Function: int mpz_congruent_2exp_p (const mpz_t N, const mpz_t C,
- mp_bitcnt_t B)
- Return non-zero if N is congruent to C modulo D, or in the case of
- 'mpz_congruent_2exp_p' modulo 2^B.
-
- N is congruent to C mod D if there exists an integer Q satisfying N
- = C + Q*D. Unlike the other division functions, D=0 is accepted
- and following the rule it can be seen that N and C are considered
- congruent mod 0 only when exactly equal.
-
-\1f
-File: gmp.info, Node: Integer Exponentiation, Next: Integer Roots, Prev: Integer Division, Up: Integer Functions
-
-5.7 Exponentiation Functions
-============================
-
- -- Function: void mpz_powm (mpz_t ROP, const mpz_t BASE, const mpz_t
- EXP, const mpz_t MOD)
- -- Function: void mpz_powm_ui (mpz_t ROP, const mpz_t BASE, unsigned
- long int EXP, const mpz_t MOD)
- Set ROP to (BASE raised to EXP) modulo MOD.
-
- Negative EXP is supported if the inverse BASE^(-1) mod MOD exists
- (see 'mpz_invert' in *note Number Theoretic Functions::). If an
- inverse doesn't exist then a divide by zero is raised.
-
- -- Function: void mpz_powm_sec (mpz_t ROP, const mpz_t BASE, const
- mpz_t EXP, const mpz_t MOD)
- Set ROP to (BASE raised to EXP) modulo MOD.
-
- It is required that EXP > 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, const 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.
-
-\1f
-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, const 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, const 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, const 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, const 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 (const 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 (const 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.
-
-\1f
-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 (const 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 non-prime.
-
- This function performs some trial divisions, a Baillie-PSW probable
- prime test, then REPS-24 Miller-Rabin probabilistic primality
- tests. A higher REPS value will reduce the chances of a non-prime
- being identified as "probably prime". A composite number will be
- identified as a prime with an asymptotic probability of less than
- 4^(-REPS). Reasonable values of REPS are between 15 and 50.
-
- GMP versions up to and including 6.1.2 did not use the Baillie-PSW
- primality test. In those older versions of GMP, this function
- performed REPS Miller-Rabin tests.
-
- -- Function: void mpz_nextprime (mpz_t ROP, const 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, const mpz_t OP1, const 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.
- Except if both inputs are zero; then this function defines gcd(0,0)
- = 0.
-
- -- Function: unsigned long int mpz_gcd_ui (mpz_t ROP, const 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, const mpz_t A,
- const 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
- (or zero if both inputs are zero). The values in S and T are
- chosen such that normally, abs(S) < abs(B) / (2 G) and abs(T) <
- abs(A) / (2 G), and these relations define S and T uniquely. There
- are a few exceptional cases:
-
- If abs(A) = abs(B), then S = 0, T = sgn(B).
-
- Otherwise, S = sgn(A) if B = 0 or abs(B) = 2 G, and T = sgn(B) if A
- = 0 or abs(A) = 2 G.
-
- In all cases, S = 0 if and only if G = abs(B), i.e., if B divides A
- or A = B = 0.
-
- If T or G is 'NULL' then that value is not computed.
-
- -- Function: void mpz_lcm (mpz_t ROP, const mpz_t OP1, const mpz_t OP2)
- -- Function: void mpz_lcm_ui (mpz_t ROP, const 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, const mpz_t OP1, const 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 < abs(OP2) (with ROP = 0 possible only when
- abs(OP2) = 1, i.e., in the somewhat degenerate zero ring). If an
- inverse doesn't exist the return value is zero and ROP is
- undefined. The behaviour of this function is undefined when OP2 is
- zero.
-
- -- Function: int mpz_jacobi (const mpz_t A, const mpz_t B)
- Calculate the Jacobi symbol (A/B). This is defined only for B odd.
-
- -- Function: int mpz_legendre (const mpz_t A, const 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 (const mpz_t A, const mpz_t B)
- -- Function: int mpz_kronecker_si (const mpz_t A, long B)
- -- Function: int mpz_kronecker_ui (const mpz_t A, unsigned long B)
- -- Function: int mpz_si_kronecker (long A, const mpz_t B)
- -- Function: int mpz_ui_kronecker (unsigned long A, const 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, const mpz_t OP, const
- 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 N)
- -- Function: void mpz_2fac_ui (mpz_t ROP, unsigned long int N)
- -- Function: void mpz_mfac_uiui (mpz_t ROP, unsigned long int N,
- unsigned long int M)
- Set ROP to the factorial of N: 'mpz_fac_ui' computes the plain
- factorial N!, 'mpz_2fac_ui' computes the double-factorial N!!, and
- 'mpz_mfac_uiui' the M-multi-factorial N!^(M).
-
- -- Function: void mpz_primorial_ui (mpz_t ROP, unsigned long int N)
- Set ROP to the primorial of N, i.e. the product of all positive
- prime numbers <=N.
-
- -- Function: void mpz_bin_ui (mpz_t ROP, const 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.
-
-\1f
-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 (const mpz_t OP1, const mpz_t OP2)
- -- Function: int mpz_cmp_d (const mpz_t OP1, double OP2)
- -- Macro: int mpz_cmp_si (const mpz_t OP1, signed long int OP2)
- -- Macro: int mpz_cmp_ui (const 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 (const mpz_t OP1, const mpz_t OP2)
- -- Function: int mpz_cmpabs_d (const mpz_t OP1, double OP2)
- -- Function: int mpz_cmpabs_ui (const 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 (const 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.
-
-\1f
-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, const mpz_t OP1, const mpz_t OP2)
- Set ROP to OP1 bitwise-and OP2.
-
- -- Function: void mpz_ior (mpz_t ROP, const mpz_t OP1, const mpz_t OP2)
- Set ROP to OP1 bitwise inclusive-or OP2.
-
- -- Function: void mpz_xor (mpz_t ROP, const mpz_t OP1, const mpz_t OP2)
- Set ROP to OP1 bitwise exclusive-or OP2.
-
- -- Function: void mpz_com (mpz_t ROP, const mpz_t OP)
- Set ROP to the one's complement of OP.
-
- -- Function: mp_bitcnt_t mpz_popcount (const 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 (const mpz_t OP1, const 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 (const mpz_t OP, mp_bitcnt_t
- STARTING_BIT)
- -- Function: mp_bitcnt_t mpz_scan1 (const 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 (const mpz_t OP, mp_bitcnt_t BIT_INDEX)
- Test bit BIT_INDEX in OP and return 0 or 1 accordingly.
-
-\1f
-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, of 'mpz' numbers. 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.
-
- See also *note Formatted Output:: and *note Formatted Input::.
-
- -- Function: size_t mpz_out_str (FILE *STREAM, int BASE, const 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, const 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.
-
-\1f
-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, const
- 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 2^(N-1) 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.
-
-\1f
-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, const 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);
-
-\1f
-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 (const mpz_t OP)
- -- Function: int mpz_fits_slong_p (const mpz_t OP)
- -- Function: int mpz_fits_uint_p (const mpz_t OP)
- -- Function: int mpz_fits_sint_p (const mpz_t OP)
- -- Function: int mpz_fits_ushort_p (const mpz_t OP)
- -- Function: int mpz_fits_sshort_p (const 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 (const mpz_t OP)
- -- Macro: int mpz_even_p (const 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 (const 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.)
-
-\1f
-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 an obsolete function. Do not use it.*
-
- -- 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 (const 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 (const mpz_t OP)
- Return the size of OP measured in number of limbs. If OP is zero,
- the returned value will be zero.
-
- -- Function: const mp_limb_t * mpz_limbs_read (const mpz_t X)
- Return a pointer to the limb array representing the absolute value
- of X. The size of the array is 'mpz_size(X)'. Intended for read
- access only.
-
- -- Function: mp_limb_t * mpz_limbs_write (mpz_t X, mp_size_t N)
- -- Function: mp_limb_t * mpz_limbs_modify (mpz_t X, mp_size_t N)
- Return a pointer to the limb array, intended for write access. The
- array is reallocated as needed, to make room for N limbs. Requires
- N > 0. The 'mpz_limbs_modify' function returns an array that holds
- the old absolute value of X, while 'mpz_limbs_write' may destroy
- the old value and return an array with unspecified contents.
-
- -- Function: void mpz_limbs_finish (mpz_t X, mp_size_t S)
- Updates the internal size field of X. Used after writing to the
- limb array pointer returned by 'mpz_limbs_write' or
- 'mpz_limbs_modify' is completed. The array should contain abs(S)
- valid limbs, representing the new absolute value for X, and the
- sign of X is taken from the sign of S. This function never
- reallocates X, so the limb pointer remains valid.
-
- void foo (mpz_t x)
- {
- mp_size_t n, i;
- mp_limb_t *xp;
-
- n = mpz_size (x);
- xp = mpz_limbs_modify (x, 2*n);
- for (i = 0; i < n; i++)
- xp[n+i] = xp[n-1-i];
- mpz_limbs_finish (x, mpz_sgn (x) < 0 ? - 2*n : 2*n);
- }
-
- -- Function: mpz_srcptr mpz_roinit_n (mpz_t X, const mp_limb_t *XP,
- mp_size_t XS)
- Special initialization of X, using the given limb array and size.
- X should be treated as read-only: it can be passed safely as input
- to any mpz function, but not as an output. The array XP must point
- to at least a readable limb, its size is abs(XS), and the sign of X
- is the sign of XS. For convenience, the function returns X, but
- cast to a const pointer type.
-
- void foo (mpz_t x)
- {
- static const mp_limb_t y[3] = { 0x1, 0x2, 0x3 };
- mpz_t tmp;
- mpz_add (x, x, mpz_roinit_n (tmp, y, 3));
- }
-
- -- Macro: mpz_t MPZ_ROINIT_N (mp_limb_t *XP, mp_size_t XS)
- This macro expands to an initializer which can be assigned to an
- mpz_t variable. The limb array XP must point to at least a
- readable limb, moreover, unlike the 'mpz_roinit_n' function, the
- array must be normalized: if XS is non-zero, then 'XP[abs(XS)-1]'
- must be non-zero. Intended primarily for constant values. Using
- it for non-constant values requires a C compiler supporting C99.
-
- void foo (mpz_t x)
- {
- static const mp_limb_t ya[3] = { 0x1, 0x2, 0x3 };
- static const mpz_t y = MPZ_ROINIT_N ((mp_limb_t *) ya, 3);
-
- mpz_add (x, x, y);
- }
-
-\1f
-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 form 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::
-
-\1f
-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, const mpq_t OP)
- -- Function: void mpq_set_z (mpq_t ROP, const 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, const 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.
-
-\1f
-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 (const mpq_t OP)
- Convert OP to a 'double', truncating if necessary (i.e. 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, const 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, const mpq_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. The string will be of the
- form 'num/den', or if the denominator is 1 then just 'num'.
-
- 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 (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.
-
-\1f
-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, const mpq_t ADDEND1, const mpq_t
- ADDEND2)
- Set SUM to ADDEND1 + ADDEND2.
-
- -- Function: void mpq_sub (mpq_t DIFFERENCE, const mpq_t MINUEND, const
- mpq_t SUBTRAHEND)
- Set DIFFERENCE to MINUEND - SUBTRAHEND.
-
- -- Function: void mpq_mul (mpq_t PRODUCT, const mpq_t MULTIPLIER, const
- mpq_t MULTIPLICAND)
- Set PRODUCT to MULTIPLIER times MULTIPLICAND.
-
- -- Function: void mpq_mul_2exp (mpq_t ROP, const mpq_t OP1, mp_bitcnt_t
- OP2)
- Set ROP to OP1 times 2 raised to OP2.
-
- -- Function: void mpq_div (mpq_t QUOTIENT, const mpq_t DIVIDEND, const
- mpq_t DIVISOR)
- Set QUOTIENT to DIVIDEND/DIVISOR.
-
- -- Function: void mpq_div_2exp (mpq_t ROP, const 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, const mpq_t OPERAND)
- Set NEGATED_OPERAND to -OPERAND.
-
- -- Function: void mpq_abs (mpq_t ROP, const mpq_t OP)
- Set ROP to the absolute value of OP.
-
- -- Function: void mpq_inv (mpq_t INVERTED_NUMBER, const mpq_t NUMBER)
- Set INVERTED_NUMBER to 1/NUMBER. If the new denominator is zero,
- this routine will divide by zero.
-
-\1f
-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 (const mpq_t OP1, const mpq_t OP2)
- -- Function: int mpq_cmp_z (const mpq_t OP1, const mpz_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 (const mpq_t OP1, unsigned long int NUM2,
- unsigned long int DEN2)
- -- Macro: int mpq_cmp_si (const 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 (const 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
- argument multiple times.
-
- -- Function: int mpq_equal (const mpq_t OP1, const 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.
-
-\1f
-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 (const mpq_t OP)
- -- Macro: mpz_t mpq_denref (const 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, const mpq_t RATIONAL)
- -- Function: void mpq_get_den (mpz_t DENOMINATOR, const mpq_t RATIONAL)
- -- Function: void mpq_set_num (mpq_t RATIONAL, const mpz_t NUMERATOR)
- -- Function: void mpq_set_den (mpq_t RATIONAL, const 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.
-
-\1f
-File: gmp.info, Node: I/O of Rationals, Prev: Applying Integer Functions, Up: Rational Number Functions
-
-6.6 Input and Output Functions
-==============================
-
-Functions that perform input from a stdio stream, and functions that
-output to a stdio stream, of 'mpq' numbers. 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.
-
- See also *note Formatted Output:: and *note Formatted Input::.
-
- -- Function: size_t mpq_out_str (FILE *STREAM, int BASE, const mpq_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.
- Output is in the form 'num/den' or if the denominator is 1 then
- just 'num'.
-
- 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 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 62, or can be 0 in which case the
- leading characters of the string determine the base, '0x' or '0X'
- for hexadecimal, '0b' and '0B' for binary, '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.
-
-\1f
-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, in
-practice only limited by available memory. Each variable has its own
-precision, and that can be increased or decreased at any time. This
-selectable precision is a minimum value, GMP rounds it up to a whole
-limb.
-
- The accuracy of a calculation is determined by the priorly set
-precision of the destination variable and the numeric values of the
-input variables. Input variables' set precisions do not affect
-calculations (except indirectly as their values might have been affected
-when they were assigned).
-
- The exponent of each float has 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 much
-greater. Note however that '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 track of 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 variable's
-selected precision is high. This is a performance optimization; it does
-not affect the numeric results.
-
- Internally, GMP sometimes calculates with higher precision than that
-of the destination variable in order to limit errors. Final results are
-always truncated to the destination variable's precision.
-
- The mantissa is stored in binary. 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.)
-
- The '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.
-
- 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.
-
- New projects should consider using the GMP extension library MPFR
-(<http://mpfr.org>) instead. MPFR provides well-defined precision and
-accurate rounding, and thereby naturally extends IEEE P754.
-
-* Menu:
-
-* Initializing Floats::
-* Assigning Floats::
-* Simultaneous Float Init & Assign::
-* Converting Floats::
-* Float Arithmetic::
-* Float Comparison::
-* I/O of Floats::
-* Miscellaneous Float Functions::
-
-\1f
-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 (const 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.
-
-\1f
-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, const 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, const mpz_t OP)
- -- Function: void mpf_set_q (mpf_t ROP, const mpq_t OP)
- Set the value of ROP from OP.
-
- -- Function: int mpf_set_str (mpf_t ROP, const 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.
-
-\1f
-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, const 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, const 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'.
-
-\1f
-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 (const mpf_t OP)
- Convert OP to a 'double', truncating if necessary (i.e. 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, const mpf_t
- OP)
- Convert OP to a 'double', truncating if necessary (i.e. 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
- (libc)Normalization Functions::).
-
- -- Function: long mpf_get_si (const mpf_t OP)
- -- Function: unsigned long mpf_get_ui (const 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, const 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.
-
-\1f
-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, const mpf_t OP1, const mpf_t OP2)
- -- Function: void mpf_add_ui (mpf_t ROP, const mpf_t OP1, unsigned long
- int OP2)
- Set ROP to OP1 + OP2.
-
- -- Function: void mpf_sub (mpf_t ROP, const mpf_t OP1, const mpf_t OP2)
- -- Function: void mpf_ui_sub (mpf_t ROP, unsigned long int OP1, const
- mpf_t OP2)
- -- Function: void mpf_sub_ui (mpf_t ROP, const mpf_t OP1, unsigned long
- int OP2)
- Set ROP to OP1 - OP2.
-
- -- Function: void mpf_mul (mpf_t ROP, const mpf_t OP1, const mpf_t OP2)
- -- Function: void mpf_mul_ui (mpf_t ROP, const 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, const mpf_t OP1, const mpf_t OP2)
- -- Function: void mpf_ui_div (mpf_t ROP, unsigned long int OP1, const
- mpf_t OP2)
- -- Function: void mpf_div_ui (mpf_t ROP, const mpf_t OP1, unsigned long
- int OP2)
- Set ROP to OP1/OP2.
-
- -- Function: void mpf_sqrt (mpf_t ROP, const 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, const mpf_t OP1, unsigned long
- int OP2)
- Set ROP to OP1 raised to the power OP2.
-
- -- Function: void mpf_neg (mpf_t ROP, const mpf_t OP)
- Set ROP to -OP.
-
- -- Function: void mpf_abs (mpf_t ROP, const mpf_t OP)
- Set ROP to the absolute value of OP.
-
- -- Function: void mpf_mul_2exp (mpf_t ROP, const mpf_t OP1, mp_bitcnt_t
- OP2)
- Set ROP to OP1 times 2 raised to OP2.
-
- -- Function: void mpf_div_2exp (mpf_t ROP, const mpf_t OP1, mp_bitcnt_t
- OP2)
- Set ROP to OP1 divided by 2 raised to OP2.
-
-\1f
-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 (const mpf_t OP1, const mpf_t OP2)
- -- Function: int mpf_cmp_z (const mpf_t OP1, const mpz_t OP2)
- -- Function: int mpf_cmp_d (const mpf_t OP1, double OP2)
- -- Function: int mpf_cmp_ui (const mpf_t OP1, unsigned long int OP2)
- -- Function: int mpf_cmp_si (const 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 (const mpf_t OP1, const mpf_t OP2, mp_bitcnt_t
- op3)
- *This function is mathematically ill-defined and should not be
- used.*
-
- Return non-zero if the first OP3 bits of OP1 and OP2 are equal,
- zero otherwise. Note that numbers like e.g., 256 (binary
- 100000000) and 255 (binary 11111111) will never be equal by this
- function's measure, and furthermore that 0 will only be equal to
- itself.
-
- -- Function: void mpf_reldiff (mpf_t ROP, const mpf_t OP1, const 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 (const 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
- argument multiple times.
-
-\1f
-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, of 'mpf' numbers. 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.
-
- See also *note Formatted Output:: and *note Formatted Input::.
-
- -- Function: size_t mpf_out_str (FILE *STREAM, int BASE, size_t
- N_DIGITS, const 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.
-
-\1f
-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, const mpf_t OP)
- -- Function: void mpf_floor (mpf_t ROP, const mpf_t OP)
- -- Function: void mpf_trunc (mpf_t ROP, const 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 (const mpf_t OP)
- Return non-zero if OP is an integer.
-
- -- Function: int mpf_fits_ulong_p (const mpf_t OP)
- -- Function: int mpf_fits_slong_p (const mpf_t OP)
- -- Function: int mpf_fits_uint_p (const mpf_t OP)
- -- Function: int mpf_fits_sint_p (const mpf_t OP)
- -- Function: int mpf_fits_ushort_p (const mpf_t OP)
- -- Function: int mpf_fits_sshort_p (const 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 or less if
- the precision of ROP is smaller.
-
- 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.
-
-\1f
-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: mp_limb_t 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}.
- This is equivalent to calling 'mpn_sub_n' with a N-limb zero
- minuend and passing {SP, N} as subtrahend. Return borrow, either 0
- or 1.
-
- -- 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 2N 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. {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.
-
- -- 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. {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 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.]
-
- -- Function: void mpn_divexact_1 (mp_limb_t * RP, const mp_limb_t * SP,
- mp_size_t N, mp_limb_t D)
- Divide {SP, N} by D, expecting it to divide exactly, and writing
- the result to {RP, N}. If D doesn't divide exactly, the value
- written to {RP, N} is undefined. The areas at RP and SP have to be
- identical or completely separate, not partially overlapping.
-
- -- 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 (const 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: int mpn_zero_p (const mp_limb_t *SP, mp_size_t N)
- Test {SP, N} and return 1 if the operand is zero, 0 otherwise.
-
- -- 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.
-
- It is required that XN >= YN > 0, the most significant limb of {YP,
- YN} must be non-zero, and at least one of the two operands must be
- odd. 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 *UP, mp_size_t UN, mp_limb_t *VP,
- mp_size_t VN)
- Let U be defined by {UP, UN} and let V be defined by {VP, VN}.
-
- 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 UN >= VN > 0, and the
- most significant limb of {VP, VN} must be non-zero.
-
- 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 area at GP
- should have room for VN limbs and the area at SP should have room
- for VN+1 limbs.
-
- Both source operands are destroyed.
-
- Compatibility notes: GMP 4.3.0 and 4.3.1 defined S less strictly.
- Earlier as well as later GMP releases define S as described here.
- GMP releases before GMP 4.3.0 required additional space for both
- input and output areas. More precisely, the areas {UP, UN+1} and
- {VP, VN+1} were destroyed (i.e. the operands plus an extra limb
- past the end of each), and the areas pointed to by GP and SP should
- each have room for UN+1 limbs.
-
- -- 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
- 'mpn_perfect_square_p'.
-
- -- Function: size_t mpn_sizeinbase (const mp_limb_t *XP, mp_size_t N,
- int BASE)
- Return the size of {XP,N} measured in number of digits in the given
- BASE. BASE can vary from 2 to 62. Requires N > 0 and XP[N-1] > 0.
- The result will be either exact or 1 too big. If BASE is a power
- of 2, the result is always exact.
-
- -- 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 input byte and STR[STRSIZE-1] is the
- least significant input byte. 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 converted value is {RP,RN} where RN is the return value. If
- the most significant input byte STR[0] is non-zero, then RP[RN-1]
- will be non-zero, else RP[RN-1] and some number of subsequent limbs
- may be zero.
-
- The area at RP has to have space for the largest possible number
- with STRSIZE digits in the chosen base, plus one extra limb.
-
- The input must have at least one byte, 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. The most
- significant limb of the input {S1P, N} must be non-zero.
-
- -- 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 Low-level functions for cryptography
-========================================
-
-The functions prefixed with 'mpn_sec_' and 'mpn_cnd_' are designed to
-perform the exact same low-level operations 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. These functions are intended for
-cryptographic purposes, where resilience to side-channel attacks is
-desired.
-
- These functions are less efficient than their "leaky" counterparts;
-their performance for operands of the sizes typically used for
-cryptographic applications is between 15% and 100% worse. For larger
-operands, these functions might be inadequate, since they rely on
-asymptotically elementary algorithms.
-
- These functions do not make any explicit allocations. Those of these
-functions that need scratch space accept a scratch space operand. This
-convention allows callers to keep sensitive data in designated memory
-areas. Note however that compilers may choose to spill scalar values
-used within these functions to their stack frame and that such scalars
-may contain sensitive data.
-
- In addition to these specially crafted functions, the following 'mpn'
-functions are naturally side-channel resistant: 'mpn_add_n',
-'mpn_sub_n', 'mpn_lshift', 'mpn_rshift', 'mpn_zero', 'mpn_copyi',
-'mpn_copyd', 'mpn_com', and the logical function ('mpn_and_n', etc).
-
- There are some exceptions from the side-channel resilience: (1) Some
-assembly implementations of 'mpn_lshift' identify shift-by-one as a
-special case. This is a problem iff the shift count is a function of
-sensitive data. (2) Alpha ev6 and Pentium4 using 64-bit limbs have
-leaky 'mpn_add_n' and 'mpn_sub_n'. (3) Alpha ev6 has a leaky
-'mpn_mul_1' which also makes 'mpn_sec_mul' on those systems unsafe.
-
- -- Function: mp_limb_t mpn_cnd_add_n (mp_limb_t CND, mp_limb_t *RP,
- const mp_limb_t *S1P, const mp_limb_t *S2P, mp_size_t N)
- -- Function: mp_limb_t mpn_cnd_sub_n (mp_limb_t CND, mp_limb_t *RP,
- const mp_limb_t *S1P, const mp_limb_t *S2P, mp_size_t N)
- These functions do conditional addition and subtraction. If CND is
- non-zero, they produce the same result as a regular 'mpn_add_n' or
- 'mpn_sub_n', and if CND is zero, they copy {S1P,N} to the result
- area and return zero. The functions are designed to have timing
- and memory access patterns depending only on size and location of
- the data areas, but independent of the condition CND. Like for
- 'mpn_add_n' and 'mpn_sub_n', on most machines, the timing will also
- be independent of the actual limb values.
-
- -- Function: mp_limb_t mpn_sec_add_1 (mp_limb_t *RP, const mp_limb_t
- *AP, mp_size_t N, mp_limb_t B, mp_limb_t *TP)
- -- Function: mp_limb_t mpn_sec_sub_1 (mp_limb_t *RP, const mp_limb_t
- *AP, mp_size_t N, mp_limb_t B, mp_limb_t *TP)
- Set R to A + B or A - B, respectively, where R = {RP,N}, A =
- {AP,N}, and B is a single limb. Returns carry.
-
- These functions take O(N) time, unlike the leaky functions
- 'mpn_add_1' which are O(1) on average. They require scratch space
- of 'mpn_sec_add_1_itch(N)' and 'mpn_sec_sub_1_itch(N)' limbs,
- respectively, to be passed in the TP parameter. The scratch space
- requirements are guaranteed to be at most N limbs, and increase
- monotonously in the operand size.
-
- -- Function: void mpn_cnd_swap (mp_limb_t CND, volatile mp_limb_t *AP,
- volatile mp_limb_t *BP, mp_size_t N)
- If CND is non-zero, swaps the contents of the areas {AP,N} and
- {BP,N}. Otherwise, the areas are left unmodified. Implemented
- using logical operations on the limbs, with the same memory
- accesses independent of the value of CND.
-
- -- Function: void mpn_sec_mul (mp_limb_t *RP, const mp_limb_t *AP,
- mp_size_t AN, const mp_limb_t *BP, mp_size_t BN, mp_limb_t
- *TP)
- -- Function: mp_size_t mpn_sec_mul_itch (mp_size_t AN, mp_size_t BN)
- Set R to A * B, where A = {AP,AN}, B = {BP,BN}, and R = {RP,AN+BN}.
-
- It is required that AN >= BN > 0.
-
- No overlapping between R and the input operands is allowed. For A
- = B, use 'mpn_sec_sqr' for optimal performance.
-
- This function requires scratch space of 'mpn_sec_mul_itch(AN, BN)'
- limbs to be passed in the TP parameter. The scratch space
- requirements are guaranteed to increase monotonously in the operand
- sizes.
-
- -- Function: void mpn_sec_sqr (mp_limb_t *RP, const mp_limb_t *AP,
- mp_size_t AN, mp_limb_t *TP)
- -- Function: mp_size_t mpn_sec_sqr_itch (mp_size_t AN)
- Set R to A^2, where A = {AP,AN}, and R = {RP,2AN}.
-
- It is required that AN > 0.
-
- No overlapping between R and the input operands is allowed.
-
- This function requires scratch space of 'mpn_sec_sqr_itch(AN)'
- limbs to be passed in the TP parameter. The scratch space
- requirements are guaranteed to increase monotonously in the operand
- size.
-
- -- Function: void mpn_sec_powm (mp_limb_t *RP, const mp_limb_t *BP,
- mp_size_t BN, const mp_limb_t *EP, mp_bitcnt_t ENB, const
- mp_limb_t *MP, mp_size_t N, mp_limb_t *TP)
- -- Function: mp_size_t mpn_sec_powm_itch (mp_size_t BN, mp_bitcnt_t
- ENB, size_t N)
- Set R to (B raised to E) modulo M, where R = {RP,N}, M = {MP,N},
- and E = {EP,ceil(ENB / 'GMP\_NUMB\_BITS')}.
-
- It is required that B > 0, that M > 0 is odd, and that E < 2^ENB,
- with ENB > 0.
-
- No overlapping between R and the input operands is allowed.
-
- This function requires scratch space of 'mpn_sec_powm_itch(BN, ENB,
- N)' limbs to be passed in the TP parameter. The scratch space
- requirements are guaranteed to increase monotonously in the operand
- sizes.
-
- -- Function: void mpn_sec_tabselect (mp_limb_t *RP, const mp_limb_t
- *TAB, mp_size_t N, mp_size_t NENTS, mp_size_t WHICH)
- Select entry WHICH from table TAB, which has NENTS entries, each N
- limbs. Store the selected entry at RP.
-
- This function reads the entire table to avoid side-channel
- information leaks.
-
- -- Function: mp_limb_t mpn_sec_div_qr (mp_limb_t *QP, mp_limb_t *NP,
- mp_size_t NN, const mp_limb_t *DP, mp_size_t DN, mp_limb_t
- *TP)
- -- Function: mp_size_t mpn_sec_div_qr_itch (mp_size_t NN, mp_size_t DN)
-
- Set Q to the truncated quotient N / D and R to N modulo D, where N
- = {NP,NN}, D = {DP,DN}, Q's most significant limb is the function
- return value and the remaining limbs are {QP,NN-DN}, and R =
- {NP,DN}.
-
- It is required that NN >= DN >= 1, and that DP[DN-1] != 0. This
- does not imply that N >= D since N might be zero-padded.
-
- Note the overlapping between N and R. No other operand overlapping
- is allowed. The entire space occupied by N is overwritten.
-
- This function requires scratch space of 'mpn_sec_div_qr_itch(NN,
- DN)' limbs to be passed in the TP parameter.
-
- -- Function: void mpn_sec_div_r (mp_limb_t *NP, mp_size_t NN, const
- mp_limb_t *DP, mp_size_t DN, mp_limb_t *TP)
- -- Function: mp_size_t mpn_sec_div_r_itch (mp_size_t NN, mp_size_t DN)
-
- Set R to N modulo D, where N = {NP,NN}, D = {DP,DN}, and R =
- {NP,DN}.
-
- It is required that NN >= DN >= 1, and that DP[DN-1] != 0. This
- does not imply that N >= D since N might be zero-padded.
-
- Note the overlapping between N and R. No other operand overlapping
- is allowed. The entire space occupied by N is overwritten.
-
- This function requires scratch space of 'mpn_sec_div_r_itch(NN,
- DN)' limbs to be passed in the TP parameter.
-
- -- Function: int mpn_sec_invert (mp_limb_t *RP, mp_limb_t *AP, const
- mp_limb_t *MP, mp_size_t N, mp_bitcnt_t NBCNT, mp_limb_t *TP)
- -- Function: mp_size_t mpn_sec_invert_itch (mp_size_t N)
- Set R to the inverse of A modulo M, where R = {RP,N}, A = {AP,N},
- and M = {MP,N}. *This function's interface is preliminary.*
-
- If an inverse exists, return 1, otherwise return 0 and leave R
- undefined. In either case, the input A is destroyed.
-
- It is required that M is odd, and that NBCNT >= ceil(\log(A+1)) +
- ceil(\log(M+1)). A safe choice is NBCNT = 2 * N * GMP_NUMB_BITS,
- but a smaller value might improve performance if M or A are known
- to have leading zero bits.
-
- This function requires scratch space of 'mpn_sec_invert_itch(N)'
- limbs to be passed in the TP parameter.
-
-
-8.2 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.
-
-\1f
-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::
-
-\1f
-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, const
- 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, i.e.
- 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.
-
-\1f
-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, const 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.
-
-\1f
-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, i.e. 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.
-
-\1f
-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::
-
-\1f
-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 its 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. Without any dot and thus no
-precision field, a precision value of 6 will be used. Note that these
-rules mean that '%Ff', '%.Ff', and '%.0Ff' will all be different.
-
- 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.
-
-\1f
-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.
-
-\1f
-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 '<gmp.h>'.
-
- -- Function: ostream& operator<< (ostream& STREAM, const 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, const 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, const 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::.
-
-\1f
-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::
-
-\1f
-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 float
- G
- 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.
-
-\1f
-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'.
-
-\1f
-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 '<gmp.h>'.
-
- -- 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::.
-
-\1f
-File: gmp.info, Node: C++ Class Interface, Next: Custom Allocation, 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.
-
- *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::
-
-\1f
-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 <gmpxx.h>
-
- 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.
-
-\1f
-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: 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, although conversions from 'mpq_class' and 'mpf_class'
- are 'explicit'. Any necessary conversion follows the corresponding
- C function, for example 'double' follows 'mpz_set_d' (*note
- Assigning Integers::).
-
- -- Function: explicit mpz_class::mpz_class (const 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: explicit mpz_class::mpz_class (const char *S, int BASE =
- 0)
- -- Function: explicit 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 (const char *STR)
- With C++11 compilers, integers can be constructed with the syntax
- '123_mpz' which is equivalent to 'mpz_class("123")'.
-
- -- 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 OP)
- -- 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)
-
- -- Function: mpz_class gcd (mpz_class OP1, mpz_class OP2)
- -- Function: mpz_class lcm (mpz_class OP1, mpz_class OP2)
- -- Function: mpz_class mpz_class::factorial (type OP)
- -- Function: mpz_class factorial (mpz_class OP)
- -- Function: mpz_class mpz_class::primorial (type OP)
- -- Function: mpz_class primorial (mpz_class OP)
- -- Function: mpz_class mpz_class::fibonacci (type OP)
- -- Function: mpz_class fibonacci (mpz_class OP)
-
- -- Function: void mpz_class::swap (mpz_class& OP)
- -- Function: void swap (mpz_class& OP1, mpz_class& OP2)
- These functions provide a C++ class interface to the corresponding
- GMP C routines. Calling 'factorial' or 'primorial' on a negative
- number is undefined.
-
- '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'.
-
-\1f
-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: mpq_class::mpq_class (type OP)
- -- Function: mpq_class::mpq_class (integer NUM, integer DEN)
- Construct an 'mpq_class'. The initial value can be a single value
- of any type (conversion from 'mpf_class' is 'explicit'), 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: explicit mpq_class::mpq_class (const 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: explicit mpq_class::mpq_class (const char *S, int BASE =
- 0)
- -- Function: explicit 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: mpq_class operator"" _mpq (const char *STR)
- With C++11 compilers, integral rationals can be constructed with
- the syntax '123_mpq' which is equivalent to 'mpq_class(123_mpz)'.
- Other rationals can be built as '-1_mpq/2' or '0xb_mpq/123456_mpz'.
-
- -- 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)
-
- -- Function: void mpq_class::swap (mpq_class& OP)
- -- Function: void swap (mpq_class& OP1, mpq_class& OP2)
- 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.
-
-\1f
-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, mp_bitcnt_t 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: explicit mpf_class::mpf_class (const mpf_t F)
- -- Function: mpf_class::mpf_class (const mpf_t F, mp_bitcnt_t PREC)
- Construct an 'mpf_class' from an 'mpf_t'. The value in F is copied
- into the new 'mpf_class', there won't be any permanent association
- between it and F.
-
- If PREC is given, the initial precision is that value, in bits. If
- PREC is not given, then the initial precision is that of F.
-
- -- Function: explicit mpf_class::mpf_class (const char *S)
- -- Function: mpf_class::mpf_class (const char *S, mp_bitcnt_t PREC, int
- BASE = 0)
- -- Function: explicit mpf_class::mpf_class (const string& S)
- -- Function: mpf_class::mpf_class (const string& S, mp_bitcnt_t 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 operator"" _mpf (const char *STR)
- With C++11 compilers, floats can be constructed with the syntax
- '1.23e-1_mpf' which is equivalent to 'mpf_class("1.23e-1")'.
-
- -- 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: void mpf_class::swap (mpf_class& OP)
- -- Function: void swap (mpf_class& OP1, mpf_class& OP2)
- -- 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.
-
-\1f
-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 (mp_bitcnt_t 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 (mp_bitcnt_t 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
-
-\1f
-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 <gmp-bugs@gmplib.org>.
-
-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 <class T>
- 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 <class T>
- void fun (T f, T g)
- {
- fun2 (f, f+g); // Bad
- }
-
- template <class T>
- void fun (T f, T g)
- {
- fun2 (f, T(f+g)); // Good
- }
-
-C++11
- C++11 provides several new ways in which types can be inferred:
- 'auto', 'decltype', etc. While they can be very convenient, they
- don't mix well with expression templates. In this example, the
- addition is performed twice, as if we had defined 'sum' as a macro.
-
- mpz_class z = 33;
- auto sum = z + z;
- mpz_class prod = sum * sum;
-
- This other example may crash, though some compilers might make it
- look like it is working, because the expression 'z+z' goes out of
- scope before it is evaluated.
-
- mpz_class z = 33;
- auto sum = z + z + z;
- mpz_class prod = sum * 2;
-
- It is thus strongly recommended to avoid 'auto' anywhere a GMP C++
- expression may appear.
-
-\1f
-File: gmp.info, Node: Custom Allocation, Next: Language Bindings, Prev: C++ Class Interface, Up: Top
-
-13 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.
-
- -- 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 REALLOCATE_FUNCTION parameter OLD_SIZE and the FREE_FUNCTION
-parameter SIZE are passed for convenience, but of course they can be
-ignored if not needed by an implementation. 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);
-
-\1f
-File: gmp.info, Node: Language Bindings, Next: Algorithms, Prev: Custom Allocation, Up: Top
-
-14 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 <https://www-sop.inria.fr/saga/logiciels/ALP/>
- Linear algebra and polynomials using templates.
- * CLN <https://www.ginac.de/CLN/>
- High level classes for arithmetic.
- * Linbox <http://www.linalg.org/>
- Sparse vectors and matrices.
- * NTL <http://www.shoup.net/ntl/>
- A C++ number theory library.
-
-Eiffel
- * Eiffelroom <http://www.eiffelroom.org/node/442>
-
-Haskell
- * Glasgow Haskell Compiler <https://www.haskell.org/ghc/>
-
-Java
- * Kaffe <https://github.com/kaffe/kaffe>
-
-Lisp
- * GNU Common Lisp <https://www.gnu.org/software/gcl/gcl.html>
- * Librep <http://librep.sourceforge.net/>
- * XEmacs (21.5.18 beta and up) <https://www.xemacs.org>
- Optional big integers, rationals and floats using GMP.
-
-ML
- * MLton compiler <http://mlton.org/>
-
-Objective Caml
- * MLGMP <https://opam.ocaml.org/packages/mlgmp/>
- * Numerix <http://pauillac.inria.fr/~quercia/>
- Optionally using GMP.
-
-Oz
- * Mozart <https://mozart.github.io/>
-
-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 <https://www.cpan.org/>
- Compatible with Math::BigInt, but not as many functions as the
- GMP module above.
- * Math::BigInt::GMP <https://www.cpan.org/>
- Plug Math::GMP into normal Math::BigInt operations.
-
-Pike
- * pikempz module in the standard distribution,
- <https://pike.lysator.liu.se/>
-
-Prolog
- * SWI Prolog <http://www.swi-prolog.org/>
- Arbitrary precision floats.
-
-Python
- * GMPY <https://code.google.com/p/gmpy/>
-
-Ruby
- * <https://rubygems.org/gems/gmp>
-
-Scheme
- * GNU Guile <https://www.gnu.org/software/guile/guile.html>
- * RScheme <https://www.rscheme.org/>
- * STklos <http://www.stklos.net/>
-
-Smalltalk
- * GNU Smalltalk <http://smalltalk.gnu.org/>
-
-Other
- * Axiom <https://savannah.nongnu.org/projects/axiom>
- Computer algebra using GCL.
- * DrGenius <http://drgenius.seul.org/>
- Geometry system and mathematical programming language.
- * GiNaC <httsp://www.ginac.de/>
- C++ computer algebra using CLN.
- * GOO <https://www.eecs.berkeley.edu/~jrb/goo/>
- Dynamic object oriented language.
- * Maxima <https://www.ma.utexas.edu/users/wfs/maxima.html>
- Macsyma computer algebra using GCL.
- * Regina <http://regina.sourceforge.net/>
- Topological calculator.
- * Yacas <http://yacas.sourceforge.net>
- Yet another computer algebra system.
-
-\1f
-File: gmp.info, Node: Algorithms, Next: Internals, Prev: Language Bindings, Up: Top
-
-15 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::
-
-\1f
-File: gmp.info, Node: Multiplication Algorithms, Next: Division Algorithms, Prev: Algorithms, Up: Algorithms
-
-15.1 Multiplication
-===================
-
-NxN limb multiplications and squares are done using one of seven
-algorithms, as the size N increases.
-
- Algorithm Threshold
- Basecase (none)
- Karatsuba 'MUL_TOOM22_THRESHOLD'
- Toom-3 'MUL_TOOM33_THRESHOLD'
- Toom-4 'MUL_TOOM44_THRESHOLD'
- Toom-6.5 'MUL_TOOM6H_THRESHOLD'
- Toom-8.5 'MUL_TOOM8H_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::
-* Higher degree Toom'n'half::
-* FFT Multiplication::
-* Other Multiplication::
-* Unbalanced Multiplication::
-
-\1f
-File: gmp.info, Node: Basecase Multiplication, Next: Karatsuba Multiplication, Prev: Multiplication Algorithms, Up: Multiplication Algorithms
-
-15.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.
-
-\1f
-File: gmp.info, Node: Karatsuba Multiplication, Next: Toom 3-Way Multiplication, Prev: Basecase Multiplication, Up: Multiplication Algorithms
-
-15.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, i.e. 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.
-
-\1f
-File: gmp.info, Node: Toom 3-Way Multiplication, Next: Toom 4-Way Multiplication, Prev: Karatsuba Multiplication, Up: Multiplication Algorithms
-
-15.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, i.e. 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 'toom_interpolate_5pts' 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.
-
-\1f
-File: gmp.info, Node: Toom 4-Way Multiplication, Next: Higher degree Toom'n'half, Prev: Toom 3-Way Multiplication, Up: Multiplication Algorithms
-
-15.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.
-
-\1f
-File: gmp.info, Node: Higher degree Toom'n'half, Next: FFT Multiplication, Prev: Toom 4-Way Multiplication, Up: Multiplication Algorithms
-
-15.1.5 Higher degree Toom'n'half
---------------------------------
-
-The Toom algorithms described above (*note Toom 3-Way Multiplication::,
-*note Toom 4-Way Multiplication::) generalizes to split into an
-arbitrary number of pieces. In general a split of two equally long
-operands into r pieces leads to evaluations and pointwise
-multiplications done at 2*r-1 points. To fully exploit symmetries it
-would be better to have a multiple of 4 points, that's why for higher
-degree Toom'n'half is used.
-
- Toom'n'half means that the existence of one more piece is considered
-for a single operand. It can be virtual, i.e. zero, or real, when the
-two operand are not exactly balanced. By choosing an even r, Toom-r+1/2
-requires 2r points, a multiple of four.
-
- The quadruplets of points include 0, inf, +1, -1 and +-2^i, +-2^-i .
-Each of them giving shortcuts for the evaluation phase and for some
-steps in the interpolation phase. Further tricks are used to reduce the
-memory footprint of the whole multiplication algorithm to a memory
-buffer equal in size to the result of the product.
-
- Current GMP uses both Toom-6'n'half and Toom-8'n'half.
-
-\1f
-File: gmp.info, Node: FFT Multiplication, Next: Other Multiplication, Prev: Higher degree Toom'n'half, Up: Multiplication Algorithms
-
-15.1.6 FFT Multiplication
--------------------------
-
-At large to very large sizes a Fermat style FFT multiplication is used,
-following Schö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.
-
-\1f
-File: gmp.info, Node: Other Multiplication, Next: Unbalanced Multiplication, Prev: FFT Multiplication, Up: Multiplication Algorithms
-
-15.1.7 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.
-
-\1f
-File: gmp.info, Node: Unbalanced Multiplication, Prev: Other Multiplication, Up: Multiplication Algorithms
-
-15.1.8 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.
-
-\1f
-File: gmp.info, Node: Division Algorithms, Next: Greatest Common Divisor Algorithms, Prev: Multiplication Algorithms, Up: Algorithms
-
-15.2 Division Algorithms
-========================
-
-* Menu:
-
-* Single Limb Division::
-* Basecase Division::
-* Divide and Conquer Division::
-* Block-Wise Barrett Division::
-* Exact Division::
-* Exact Remainder::
-* Small Quotient Division::
-
-\1f
-File: gmp.info, Node: Single Limb Division, Next: Basecase Division, Prev: Division Algorithms, Up: Division Algorithms
-
-15.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 Mö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.
-
-\1f
-File: gmp.info, Node: Basecase Division, Next: Divide and Conquer Division, Prev: Single Limb Division, Up: Division Algorithms
-
-15.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.
-
-\1f
-File: gmp.info, Node: Divide and Conquer Division, Next: Block-Wise Barrett Division, Prev: Basecase Division, Up: Division Algorithms
-
-15.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.
-
-\1f
-File: gmp.info, Node: Block-Wise Barrett Division, Next: Exact Division, Prev: Divide and Conquer Division, Up: Division Algorithms
-
-15.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.
-
-\1f
-File: gmp.info, Node: Exact Division, Next: Exact Remainder, Prev: Block-Wise Barrett Division, Up: Division Algorithms
-
-15.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.
-
projects / xonotic / xonotic.git / blobdiff