diff options
Diffstat (limited to 'gmp/doc/gmp.texi')
| -rw-r--r-- | gmp/doc/gmp.texi | 1974 |
1 files changed, 789 insertions, 1185 deletions
diff --git a/gmp/doc/gmp.texi b/gmp/doc/gmp.texi index 86d033101a..704faed27f 100644 --- a/gmp/doc/gmp.texi +++ b/gmp/doc/gmp.texi @@ -14,7 +14,8 @@ This manual describes how to install and use the GNU multiple precision arithmetic library, version @value{VERSION}. -Copyright 1991, 1993-2014 Free Software Foundation, Inc. +Copyright 1991, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, +2003, 2004, 2005, 2006, 2007, 2008, 2009 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 @@ -90,8 +91,8 @@ How to install and use the GNU multiple precision arithmetic library, version @v @subtitle Edition @value{EDITION} @subtitle @value{UPDATED} -@author by Torbj@"orn Granlund and the GMP development team -@c @email{tg@@gmplib.org} +@author by the GMP developers +@c @email{tege@@gmplib.org} @c Include the Distribution inside the titlepage so @c that headings are turned off. @@ -135,6 +136,7 @@ How to install and use the GNU multiple precision arithmetic library, version @v * Formatted Output:: @code{printf} style output. * Formatted Input:: @code{scanf} style input. * C++ Class Interface:: Class wrappers around GMP types. +* BSD Compatible Functions:: All functions found in BSD MP. * Custom Allocation:: How to customize the internal allocation. * Language Bindings:: Using GMP from other languages. * Algorithms:: What happens behind the scenes. @@ -443,19 +445,10 @@ 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.@refill -More precisely, the GNU MP library is dual licensed, under the conditions of -the GNU Lesser General Public License version 3 (see -@file{COPYING.LESSERv3}), or the GNU General Public License version 2 (see -@file{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 @file{COPYINGv3}), or any later -version. +The precise conditions of the license for the GNU MP library are found in the +Lesser General Public License version 3 that accompanies the source code, +see @file{COPYING.LIB}. Certain demonstration programs are provided under the +terms of the plain General Public License version 3, see @file{COPYING}. @node Introduction to GMP, Installing GMP, Copying, Top @@ -480,17 +473,29 @@ emphasis on speed (as opposed to simplicity or elegance). There is assembly code for these CPUs: @cindex CPU types -ARM Cortex-A9, Cortex-A15, and generic ARM, +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. - +AMD 29000, +AMD K6, K6-2, Athlon, and Athlon64, +Hitachi SuperH and SH-2, +HPPA 1.0, 1.1 and 2.0, +Intel Pentium, Pentium Pro/II/III, Pentium 4, generic x86, +Intel IA-64, i960, +Motorola MC68000, MC68020, MC88100, and MC88110, +Motorola/IBM PowerPC 32 and 64, +National NS32000, +IBM POWER, +MIPS R3000, R4000, +SPARCv7, SuperSPARC, generic SPARCv8, UltraSPARC, +DEC VAX, +and +Zilog Z8000. +Some optimizations also for +Cray vector systems, +Clipper, +IBM ROMP (RT), +and +Pyramid AP/XP. @cindex Home page @cindex Web page @@ -498,7 +503,7 @@ There is also assembly code for many obsolete CPUs. For up-to-date information on GMP, please see the GMP web pages at @display -@uref{https://gmplib.org/} +@uref{http://gmplib.org/} @end display @cindex Latest version of GMP @@ -508,11 +513,11 @@ For up-to-date information on GMP, please see the GMP web pages at The latest version of the library is available at @display -@uref{https://ftp.gnu.org/gnu/gmp/} +@uref{ftp://ftp.gnu.org/gnu/gmp/} @end display Many sites around the world mirror @samp{ftp.gnu.org}, please use a mirror -near you, see @uref{https://www.gnu.org/order/ftp.html} for a full list. +near you, see @uref{http://www.gnu.org/order/ftp.html} for a full list. @cindex Mailing lists There are three public mailing lists of interest. One for release @@ -520,7 +525,7 @@ announcements, one for general questions and discussions about usage of the GMP library and one for bug reports. For more information, see @display -@uref{https://gmplib.org/mailman/listinfo/}. +@uref{http://gmplib.org/mailman/listinfo/}. @end display The proper place for bug reports is @email{gmp-bugs@@gmplib.org}. See @@ -708,7 +713,7 @@ 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 @file{configure.ac} for details +The following CPUs have specific support. See @file{configure.in} for details of what code and compiler options they select. @itemize @bullet @@ -837,10 +842,16 @@ x86 family: @item Other: +@nisamp{a29k}, @nisamp{arm}, +@nisamp{clipper}, +@nisamp{i960}, +@nisamp{ns32k}, +@nisamp{pyramid}, @nisamp{sh}, @nisamp{sh2}, @nisamp{vax}, +@nisamp{z8k} @end itemize CPUs not listed will use generic C code. @@ -848,14 +859,18 @@ CPUs not listed will use generic C code. @item Generic C Build @cindex Generic C If some of the assembly code causes problems, or if otherwise desired, the -generic C code can be selected with the configure @option{--disable-assembly}. +generic C code can be selected with CPU @samp{none}. For example, + +@example +./configure --host=none-unknown-freebsd3.5 +@end example 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. @item Fat binary, @option{--enable-fat} @cindex Fat binary -@cindex @code{--enable-fat} +@cindex @option{--enable-fat} Using @option{--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. @@ -908,7 +923,8 @@ preprocessor should be set in @samp{CPPFLAGS} rather than @samp{CFLAGS}. Compiling is done with both @samp{CPPFLAGS} and @samp{CFLAGS}, but preprocessing uses just @samp{CPPFLAGS}. This distinction is because most preprocessors won't accept all the flags the compiler does. Preprocessing is -done separately in some configure tests. +done separately in some configure tests, and in the @samp{ansi2knr} support +for K&R compilers. @item @option{CC_FOR_BUILD} @cindex @code{CC_FOR_BUILD} @@ -1023,9 +1039,17 @@ debugging memory related problems (@pxref{Debugging}). @item FFT Multiplication, @option{--disable-fft} @cindex FFT multiplication @cindex @code{--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. +By default multiplications are done using Karatsuba, 3-way Toom, and +Fermat FFT@. The FFT is only used on large to very large operands and can be +disabled to save code size if desired. + +@item Berkeley MP, @option{--enable-mpbsd} +@cindex Berkeley MP compatible functions +@cindex BSD MP compatible functions +@cindex @code{--enable-mpbsd} +The Berkeley MP compatibility library (@file{libmp}) and header file +(@file{mp.h}) are built and installed only if @option{--enable-mpbsd} is used. +@xref{BSD Compatible Functions}. @item Assertion Checking, @option{--enable-assert} @cindex Assertion checking @@ -1149,16 +1173,6 @@ gcc -m32 @end example (In GCC 2.95 and earlier there's no @samp{-m32} option, it's the only mode.) - -@item @samp{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. - -@example -gcc -mx32 -@end example - @end table @sp 1 @@ -1284,7 +1298,7 @@ support for n32 or 64 and so only gets a 32-bit limb and the MIPS 2 code. @item PowerPC 64 (@samp{powerpc64}, @samp{powerpc620}, @samp{powerpc630}, @samp{powerpc970}, @samp{power4}, @samp{power5}) @cindex PowerPC @table @asis -@item @samp{ABI=mode64} +@item @samp{ABI=aix64} @cindex AIX The AIX 64 ABI uses 64-bit limbs and pointers and is the default on PowerPC 64 @samp{*-*-aix*} systems. Applications must be compiled with @@ -1294,28 +1308,31 @@ gcc -maix64 xlc -q64 @end example -On 64-bit GNU/Linux, BSD, and Mac OS X/Darwin systems, the applications must -be compiled with +@item @samp{ABI=mode64} +The @samp{mode64} ABI uses 64-bit limbs and pointers, and is the default on +64-bit GNU/Linux, BSD, and Mac OS X/Darwin systems. Applications must be +compiled with @example gcc -m64 @end example @item @samp{ABI=mode32} +@cindex AIX The @samp{mode32} ABI uses a 64-bit @code{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. +on for systems where the true 64-bit ABIs are unavailable. No special compiler +options are needed for applications. @item @samp{ABI=32} This is the basic 32-bit PowerPC ABI, with a 32-bit limb. No special compiler options are needed for applications. @end table -GMP's speed is greatest for the @samp{mode64} ABI, the @samp{mode32} ABI is 2nd -best. In @samp{ABI=32} only the 32-bit ISA is used and this doesn't make full -use of a 64-bit chip. +GMP speed is greatest in @samp{aix64} and @samp{mode32}. In @samp{ABI=32} +only the 32-bit ISA is used and this doesn't make full use of a 64-bit chip. +On a suitable system we could perhaps use more of the ISA, but there are no +plans to do so. @sp 1 @need 1000 @@ -1511,20 +1528,11 @@ involving a @code{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. -@item FreeBSD 7.x, 8.x, 9.0, 9.1, 9.2 -@cindex FreeBSD -@command{m4} in these releases of FreeBSD has an eval function which ignores -its 2nd and 3rd arguments, which makes it unsuitable for @file{.asm} file -processing. @samp{./configure} will detect the problem and either abort or -choose another m4 in the @env{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 @samp{gm4}, which GMP cannot guess. - -@item FreeBSD 7.x, 8.x, 9.x -@cindex FreeBSD -GMP releases starting with 6.0 do not support @samp{ABI=32} on FreeBSD/amd64 -prior to release 10.0 of the system. The cause is a broken @code{limits.h}, -which GMP no longer works around. +@item MacOS 9 +@cindex MacOS 9 +The @file{macos} directory contains an unsupported port to MacOS 9 on Power +Macintosh, see @file{macos/README}. Note that MacOS X ``Darwin'' should use +the normal Unix-style @samp{./configure}. @item MS-DOS and MS Windows @cindex MS-DOS @@ -1586,15 +1594,6 @@ performance boost on applicable CPUs. @samp{m68360} can be used for CPU32 series chips. @samp{m68302} can be used for ``Dragonball'' series chips, though this is merely a synonym for @samp{m68000}. -@item NetBSD 5.x -@cindex NetBSD -@command{m4} in these releases of NetBSD has an eval function which ignores its -2nd and 3rd arguments, which makes it unsuitable for @file{.asm} file -processing. @samp{./configure} will detect the problem and either abort or -choose another m4 in the @env{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 @samp{gm4}, which GMP cannot guess. - @item OpenBSD 2.6 @cindex OpenBSD @command{m4} in this release of OpenBSD has a bug in @code{eval} that makes it @@ -1608,11 +1607,11 @@ In GMP, CPU types @samp{power*} and @samp{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 (@option{--disable-assembly}), -possibly with appropriate compiler options (like @samp{-mcpu=common} for +current suggestion is to use the generic C code (CPU @samp{none}), possibly +with appropriate compiler options (like @samp{-mcpu=common} for @command{gcc}). CPU @samp{rs6000} (which is not a CPU but a family of workstations) is accepted by @file{config.sub}, but is currently equivalent to -@option{--disable-assembly}. +@samp{none}. @item Sparc CPU Types @cindex Sparc @@ -1628,10 +1627,10 @@ that the GCC default @samp{-mapp-regs} does (@pxref{SPARC Options,, SPARC Options, gcc, Using the GNU Compiler Collection (GCC)}). This makes that code unsuitable for use with the special V9 -@samp{-mcmodel=embmedany} (which uses @code{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 -@option{--disable-assembly} to avoid the assembly code. +@samp{-mcmodel=embmedany} (which uses @code{g4} as a data segment pointer), +and for applications wanting to use those registers for special purposes. In +these cases the only suggestion currently is to build GMP with CPU @samp{none} +to avoid the assembly code. @item SunOS 4 @cindex SunOS @@ -1675,7 +1674,7 @@ Install a recent @command{gas} if MMX code is wanted on these systems. @c This section is more or less meant for known build problems that are not @c otherwise worked around and require some sort of manual intervention. -You might find more up-to-date information at @uref{https://gmplib.org/}. +You might find more up-to-date information at @uref{http://gmplib.org/}. @table @asis @item Compiler link options @@ -1796,7 +1795,7 @@ make tuneup will generate better contents for the @file{gmp-mparam.h} parameter file. -To use the results, put the output in the file indicated in the +To use the results, put the output in the file file indicated in the @samp{Parameters for ...} header. Then recompile from scratch. The @code{tuneup} program takes one useful parameter, @samp{-f NNN}, which @@ -1856,10 +1855,10 @@ are only provided if @code{<stdio.h>} is included too. @end example @cindex @code{stdarg.h} -Likewise @code{<stdarg.h>} is required for prototypes with @code{va_list} -parameters, such as @code{gmp_vprintf}. And @code{<obstack.h>} for prototypes -with @code{struct obstack} parameters, such as @code{gmp_obstack_printf}, when -available. +Likewise @code{<stdarg.h>} (or @code{<varargs.h>}) is required for prototypes +with @code{va_list} parameters, such as @code{gmp_vprintf}. And +@code{<obstack.h>} for prototypes with @code{struct obstack} parameters, such +as @code{gmp_obstack_printf}, when available. @cindex Libraries @cindex Linking @@ -1940,15 +1939,9 @@ 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 @code{mp_limb_t}. @tindex @code{mp_size_t} -Counts of limbs of a multi-precision number represented in the C type -@code{mp_size_t}. Currently this is normally a @code{long}, but on some -systems it's an @code{int} for efficiency, and on some systems it will be -@code{long long} in the future. - -@tindex @code{mp_bitcnt_t} -Counts of bits of a multi-precision number are represented in the C type -@code{mp_bitcnt_t}. Currently this is always an @code{unsigned long}, but on -some systems it will be an @code{unsigned long long} in the future. +Counts of limbs are represented in the C type @code{mp_size_t}. Currently +this is normally a @code{long}, but on some systems it's an @code{int} for +efficiency. @cindex Random state @tindex @code{gmp_randstate_t} @@ -1959,7 +1952,7 @@ data type for such objects is @code{gmp_randstate_t}. For example: gmp_randstate_t rstate; @end example -Also, in general @code{mp_bitcnt_t} is used for bit counts and ranges, and +Also, in general @code{unsigned long} is used for bit counts and ranges, and @code{size_t} is used for byte or character counts. @@ -1977,22 +1970,27 @@ functions in this class. (@pxref{Integer Functions}) @item Functions for rational number arithmetic, with names beginning with -@code{mpq_}. The associated type is @code{mpq_t}. There are about 35 +@code{mpq_}. The associated type is @code{mpq_t}. There are about 40 functions in this class, but the integer functions can be used for arithmetic on the numerator and denominator separately. (@pxref{Rational Number Functions}) @item Functions for floating-point arithmetic, with names beginning with -@code{mpf_}. The associated type is @code{mpf_t}. There are about 70 +@code{mpf_}. The associated type is @code{mpf_t}. There are about 60 functions is this class. (@pxref{Floating-point Functions}) @item +Functions compatible with Berkeley MP, such as @code{itom}, @code{madd}, and +@code{mult}. The associated type is @code{MINT}. (@pxref{BSD Compatible +Functions}) + +@item 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 @code{mpn_}. The associated type is array of @code{mp_limb_t}. There are -about 60 (hard-to-use) functions in this class. (@pxref{Low-level Functions}) +about 30 (hard-to-use) functions in this class. (@pxref{Low-level Functions}) @item Miscellaneous functions. Functions for setting up custom allocation and @@ -2176,7 +2174,7 @@ GMP I/O functions using them will not be reentrant either. @item 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 +but it's not safe for one to read while the another might be writing, nor for two threads to write simultaneously. It's not safe for two threads to generate a random number from the same @code{gmp_randstate_t} simultaneously, since this involves an update of that variable. @@ -2210,7 +2208,7 @@ For GMP i.j.k, these numbers will be i, j, and k, respectively. @findex gmp_version The GMP version number, as a null-terminated string, in the form ``i.j.k''. This release is @nicode{"@value{VERSION}"}. Note that the format ``i.j'' was -used, before version 4.3.0, when k was zero. +used when k was zero was used before version 4.3.0. @end deftypevr @defmac __GMP_CC @@ -2226,7 +2224,7 @@ strings. @cindex Past GMP versions @cindex Upward compatibility -This version of GMP is upwardly binary compatible with all 5.x, 4.x, and 3.x +This version of GMP is upwardly binary compatible with all 4.x and 3.x versions, and upwardly compatible at the source level with all 2.x versions, with the following exceptions. @@ -2238,15 +2236,16 @@ with other @code{mpn} functions. @item @code{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. - -@item -@code{mpn_bdivmod}, documented as preliminary in GMP 4, has been removed. @end itemize 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 +course also apply when porting applications from GMP 1 to GMP 4. Please see the GMP 2 manual for details. +The Berkeley MP compatibility library (@pxref{BSD Compatible Functions}) is +source and binary compatible with the standard @file{libmp}. + +@c @enumerate @c @item Integer division functions round the result differently. The obsolete @c functions (@code{mpz_div}, @code{mpz_divmod}, @code{mpz_mdiv}, @c @code{mpz_mdivmod}, etc) now all use floor rounding (i.e., they round the @@ -2625,7 +2624,7 @@ Applications using the low-level @code{mpn} functions, however, will benefit from @option{--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 -@option{--disable-assembly} should be used for maximum checking. +CPU @samp{none} should be used for maximum checking. @item Temporary Memory Checking The build option @option{--enable-alloca=debug} arranges that each block of @@ -2643,7 +2642,7 @@ To summarize the above, a GMP build for maximum debuggability would be @example ./configure --disable-shared --enable-assert \ - --enable-alloca=debug --disable-assembly CFLAGS=-g + --enable-alloca=debug --host=none CFLAGS=-g @end example For C++, add @samp{--enable-cxx CXXFLAGS=-g}. @@ -2651,7 +2650,7 @@ For C++, add @samp{--enable-cxx CXXFLAGS=-g}. @item Checker @cindex Checker @cindex GCC Checker -The GCC checker (@uref{https://savannah.nongnu.org/projects/checker/}) can be +The GCC checker (@uref{http://savannah.nongnu.org/projects/checker/}) can be used with GMP@. It contains a stub library which means GMP applications compiled with checker can use a normal GMP build. @@ -2660,30 +2659,23 @@ very very slowly. On GNU/Linux for example, @cindex @command{checkergcc} @example -./configure --disable-assembly CC=checkergcc +./configure --host=none-pc-linux-gnu CC=checkergcc @end example -@option{--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. +@samp{--host=none} must be used, since the GMP assembly code doesn't support +the checking scheme. The GMP C++ features cannot be used, since current +versions of checker (0.9.9.1) don't yet support the standard C++ library. @item Valgrind @cindex Valgrind -Valgrind (@uref{http://valgrind.org/}) is a memory checker for x86, ARM, MIPS, -PowerPC, and S/390. It translates and emulates machine instructions to do +The valgrind program (@uref{http://valgrind.org/}) is a memory +checker for x86s. It translates and emulates machine instructions to do strong checks for uninitialized data (at the level of individual bits), memory accesses through bad pointers, and memory leaks. -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 @samp{--partial-loads-ok=yes} should help. +Recent versions of Valgrind are getting support for MMX and SSE/SSE2 +instructions, for past versions GMP will need to be configured not to use +those, ie.@: for an x86 without them (for instance plain @samp{i486}). @item Other Problems Any suspected bug in GMP itself should be isolated to make sure it's not an @@ -2812,7 +2804,7 @@ found. For example, @example AC_CHECK_LIB(gmp, __gmpz_init, , - [AC_MSG_ERROR([GNU MP not found, see https://gmplib.org/])]) + [AC_MSG_ERROR([GNU MP not found, see http://gmplib.org/])]) @end example If functions added in some particular version of GMP are required, then one of @@ -2822,7 +2814,7 @@ GMP 3.1, @example AC_CHECK_LIB(gmp, __gmpz_mul_si, , [AC_MSG_ERROR( - [GNU MP not found, or not 3.1 or up, see https://gmplib.org/])]) + [GNU MP not found, or not 3.1 or up, see http://gmplib.org/])]) @end example An alternative would be to test the version number in @file{gmp.h} using say @@ -2882,7 +2874,7 @@ much to ask you to report the bugs you find. Before you report a bug, check it's not already addressed in @ref{Known Build Problems}, or perhaps @ref{Notes for Particular Systems}. You may also want -to check @uref{https://gmplib.org/} for patches for this release. +to check @uref{http://gmplib.org/} for patches for this release. Please include the following in any report, @@ -2906,10 +2898,7 @@ informative (@samp{where} in @command{gdb}, or @samp{$C} in @command{adb}). Please do not send core dumps, executables or @command{strace}s. @item -The @samp{configure} options you used when building GMP, if any. - -@item -The output from @samp{configure}, as printed to stdout, with any options used. +The configuration options you used when building GMP, if any. @item The name of the compiler and its version. For @command{gcc}, get the version @@ -3009,23 +2998,15 @@ object is initialized. Initialize @var{x}, and set its value to 0. @end deftypefun -@deftypefun void mpz_inits (mpz_t @var{x}, ...) -Initialize a NULL-terminated list of @code{mpz_t} variables, and set their -values to 0. -@end deftypefun - -@deftypefun void mpz_init2 (mpz_t @var{x}, mp_bitcnt_t @var{n}) +@deftypefun void mpz_init2 (mpz_t @var{x}, unsigned long @var{n}) Initialize @var{x}, with space for @var{n}-bit numbers, and set its value to 0. Calling this function instead of @code{mpz_init} or @code{mpz_inits} is never necessary; reallocation is handled automatically by GMP when needed. -While @var{n} defines the initial space, @var{x} will grow automatically in the -normal way, if necessary, for subsequent values stored. @code{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 -@var{x}, you need to add the number of bits in @code{mp_limb_t} to @var{n}. +@var{n} is only the initial space, @var{x} will grow automatically in +the normal way, if necessary, for subsequent values stored. @code{mpz_init2} +makes it possible to avoid such reallocations if a maximum size is known in +advance. @end deftypefun @deftypefun void mpz_clear (mpz_t @var{x}) @@ -3033,11 +3014,7 @@ Free the space occupied by @var{x}. Call this function for all @code{mpz_t} variables when you are done with them. @end deftypefun -@deftypefun void mpz_clears (mpz_t @var{x}, ...) -Free the space occupied by a NULL-terminated list of @code{mpz_t} variables. -@end deftypefun - -@deftypefun void mpz_realloc2 (mpz_t @var{x}, mp_bitcnt_t @var{n}) +@deftypefun void mpz_realloc2 (mpz_t @var{x}, unsigned long @var{n}) Change the space allocated for @var{x} to @var{n} bits. The value in @var{x} is preserved if it fits, or is set to 0 if not. @@ -3057,19 +3034,19 @@ to give memory back to the heap. These functions assign new values to already initialized integers (@pxref{Initializing Integers}). -@deftypefun void mpz_set (mpz_t @var{rop}, const mpz_t @var{op}) +@deftypefun void mpz_set (mpz_t @var{rop}, mpz_t @var{op}) @deftypefunx void mpz_set_ui (mpz_t @var{rop}, unsigned long int @var{op}) @deftypefunx void mpz_set_si (mpz_t @var{rop}, signed long int @var{op}) @deftypefunx void mpz_set_d (mpz_t @var{rop}, double @var{op}) -@deftypefunx void mpz_set_q (mpz_t @var{rop}, const mpq_t @var{op}) -@deftypefunx void mpz_set_f (mpz_t @var{rop}, const mpf_t @var{op}) +@deftypefunx void mpz_set_q (mpz_t @var{rop}, mpq_t @var{op}) +@deftypefunx void mpz_set_f (mpz_t @var{rop}, mpf_t @var{op}) Set the value of @var{rop} from @var{op}. @code{mpz_set_d}, @code{mpz_set_q} and @code{mpz_set_f} truncate @var{op} to make it an integer. @end deftypefun -@deftypefun int mpz_set_str (mpz_t @var{rop}, const char *@var{str}, int @var{base}) +@deftypefun int mpz_set_str (mpz_t @var{rop}, char *@var{str}, int @var{base}) Set the value of @var{rop} from @var{str}, a null-terminated C string in base @var{base}. White space is allowed in the string, and is simply ignored. @@ -3128,7 +3105,7 @@ 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! -@deftypefun void mpz_init_set (mpz_t @var{rop}, const mpz_t @var{op}) +@deftypefun void mpz_init_set (mpz_t @var{rop}, mpz_t @var{op}) @deftypefunx void mpz_init_set_ui (mpz_t @var{rop}, unsigned long int @var{op}) @deftypefunx void mpz_init_set_si (mpz_t @var{rop}, signed long int @var{op}) @deftypefunx void mpz_init_set_d (mpz_t @var{rop}, double @var{op}) @@ -3136,7 +3113,7 @@ Initialize @var{rop} with limb space and set the initial numeric value from @var{op}. @end deftypefun -@deftypefun int mpz_init_set_str (mpz_t @var{rop}, const char *@var{str}, int @var{base}) +@deftypefun int mpz_init_set_str (mpz_t @var{rop}, char *@var{str}, int @var{base}) Initialize @var{rop} and set its value like @code{mpz_set_str} (see its documentation above for details). @@ -3156,7 +3133,7 @@ This section describes functions for converting GMP integers to standard C types. Functions for converting @emph{to} GMP integers are described in @ref{Assigning Integers} and @ref{I/O of Integers}. -@deftypefun {unsigned long int} mpz_get_ui (const mpz_t @var{op}) +@deftypefun {unsigned long int} mpz_get_ui (mpz_t @var{op}) Return the value of @var{op} as an @code{unsigned long}. If @var{op} is too big to fit an @code{unsigned long} then just the least @@ -3164,7 +3141,7 @@ significant bits that do fit are returned. The sign of @var{op} is ignored, only the absolute value is used. @end deftypefun -@deftypefun {signed long int} mpz_get_si (const mpz_t @var{op}) +@deftypefun {signed long int} mpz_get_si (mpz_t @var{op}) If @var{op} fits into a @code{signed long int} return the value of @var{op}. Otherwise return the least significant part of @var{op}, with the same sign as @var{op}. @@ -3174,8 +3151,8 @@ result is probably not very useful. To find out if the value will fit, use the function @code{mpz_fits_slong_p}. @end deftypefun -@deftypefun double mpz_get_d (const mpz_t @var{op}) -Convert @var{op} to a @code{double}, truncating if necessary (i.e.@: rounding +@deftypefun double mpz_get_d (mpz_t @var{op}) +Convert @var{op} to a @code{double}, truncating if necessary (ie.@: rounding towards zero). If the exponent from the conversion is too big, the result is system @@ -3183,8 +3160,8 @@ dependent. An infinity is returned where available. A hardware overflow trap may or may not occur. @end deftypefun -@deftypefun double mpz_get_d_2exp (signed long int *@var{exp}, const mpz_t @var{op}) -Convert @var{op} to a @code{double}, truncating if necessary (i.e.@: rounding +@deftypefun double mpz_get_d_2exp (signed long int *@var{exp}, mpz_t @var{op}) +Convert @var{op} to a @code{double}, truncating if necessary (ie.@: rounding towards zero), and returning the exponent separately. The return value is in the range @math{0.5@le{}@GMPabs{@var{d}}<1} and the @@ -3197,7 +3174,7 @@ This is similar to the standard C @code{frexp} function (@pxref{Normalization Functions,,, libc, The GNU C Library Reference Manual}). @end deftypefun -@deftypefun {char *} mpz_get_str (char *@var{str}, int @var{base}, const mpz_t @var{op}) +@deftypefun {char *} mpz_get_str (char *@var{str}, int @var{base}, mpz_t @var{op}) Convert @var{op} to a string of digits in base @var{base}. The base argument may vary from 2 to 62 or from @minus{}2 to @minus{}36. @@ -3228,45 +3205,45 @@ or the given @var{str}. @cindex Integer arithmetic functions @cindex Arithmetic functions -@deftypefun void mpz_add (mpz_t @var{rop}, const mpz_t @var{op1}, const mpz_t @var{op2}) -@deftypefunx void mpz_add_ui (mpz_t @var{rop}, const mpz_t @var{op1}, unsigned long int @var{op2}) +@deftypefun void mpz_add (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx void mpz_add_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) Set @var{rop} to @math{@var{op1} + @var{op2}}. @end deftypefun -@deftypefun void mpz_sub (mpz_t @var{rop}, const mpz_t @var{op1}, const mpz_t @var{op2}) -@deftypefunx void mpz_sub_ui (mpz_t @var{rop}, const mpz_t @var{op1}, unsigned long int @var{op2}) -@deftypefunx void mpz_ui_sub (mpz_t @var{rop}, unsigned long int @var{op1}, const mpz_t @var{op2}) +@deftypefun void mpz_sub (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx void mpz_sub_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +@deftypefunx void mpz_ui_sub (mpz_t @var{rop}, unsigned long int @var{op1}, mpz_t @var{op2}) Set @var{rop} to @var{op1} @minus{} @var{op2}. @end deftypefun -@deftypefun void mpz_mul (mpz_t @var{rop}, const mpz_t @var{op1}, const mpz_t @var{op2}) -@deftypefunx void mpz_mul_si (mpz_t @var{rop}, const mpz_t @var{op1}, long int @var{op2}) -@deftypefunx void mpz_mul_ui (mpz_t @var{rop}, const mpz_t @var{op1}, unsigned long int @var{op2}) +@deftypefun void mpz_mul (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx void mpz_mul_si (mpz_t @var{rop}, mpz_t @var{op1}, long int @var{op2}) +@deftypefunx void mpz_mul_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) Set @var{rop} to @math{@var{op1} @GMPtimes{} @var{op2}}. @end deftypefun -@deftypefun void mpz_addmul (mpz_t @var{rop}, const mpz_t @var{op1}, const mpz_t @var{op2}) -@deftypefunx void mpz_addmul_ui (mpz_t @var{rop}, const mpz_t @var{op1}, unsigned long int @var{op2}) +@deftypefun void mpz_addmul (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx void mpz_addmul_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) Set @var{rop} to @math{@var{rop} + @var{op1} @GMPtimes{} @var{op2}}. @end deftypefun -@deftypefun void mpz_submul (mpz_t @var{rop}, const mpz_t @var{op1}, const mpz_t @var{op2}) -@deftypefunx void mpz_submul_ui (mpz_t @var{rop}, const mpz_t @var{op1}, unsigned long int @var{op2}) +@deftypefun void mpz_submul (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx void mpz_submul_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) Set @var{rop} to @math{@var{rop} - @var{op1} @GMPtimes{} @var{op2}}. @end deftypefun -@deftypefun void mpz_mul_2exp (mpz_t @var{rop}, const mpz_t @var{op1}, mp_bitcnt_t @var{op2}) +@deftypefun void mpz_mul_2exp (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) @cindex Bit shift left Set @var{rop} to @m{@var{op1} \times 2^{op2}, @var{op1} times 2 raised to @var{op2}}. This operation can also be defined as a left shift by @var{op2} bits. @end deftypefun -@deftypefun void mpz_neg (mpz_t @var{rop}, const mpz_t @var{op}) +@deftypefun void mpz_neg (mpz_t @var{rop}, mpz_t @var{op}) Set @var{rop} to @minus{}@var{op}. @end deftypefun -@deftypefun void mpz_abs (mpz_t @var{rop}, const mpz_t @var{op}) +@deftypefun void mpz_abs (mpz_t @var{rop}, mpz_t @var{op}) Set @var{rop} to the absolute value of @var{op}. @end deftypefun @@ -3287,43 +3264,43 @@ same way as for normal C @code{int} arithmetic. @c between each, and seem to let tex do a better job of page breaks than an @c @sp 1 in the middle of one big set. -@deftypefun void mpz_cdiv_q (mpz_t @var{q}, const mpz_t @var{n}, const mpz_t @var{d}) -@deftypefunx void mpz_cdiv_r (mpz_t @var{r}, const mpz_t @var{n}, const mpz_t @var{d}) -@deftypefunx void mpz_cdiv_qr (mpz_t @var{q}, mpz_t @var{r}, const mpz_t @var{n}, const mpz_t @var{d}) +@deftypefun void mpz_cdiv_q (mpz_t @var{q}, mpz_t @var{n}, mpz_t @var{d}) +@deftypefunx void mpz_cdiv_r (mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d}) +@deftypefunx void mpz_cdiv_qr (mpz_t @var{q}, mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d}) @maybepagebreak -@deftypefunx {unsigned long int} mpz_cdiv_q_ui (mpz_t @var{q}, const mpz_t @var{n}, @w{unsigned long int @var{d}}) -@deftypefunx {unsigned long int} mpz_cdiv_r_ui (mpz_t @var{r}, const mpz_t @var{n}, @w{unsigned long int @var{d}}) -@deftypefunx {unsigned long int} mpz_cdiv_qr_ui (mpz_t @var{q}, mpz_t @var{r}, @w{const mpz_t @var{n}}, @w{unsigned long int @var{d}}) -@deftypefunx {unsigned long int} mpz_cdiv_ui (const mpz_t @var{n}, @w{unsigned long int @var{d}}) +@deftypefunx {unsigned long int} mpz_cdiv_q_ui (mpz_t @var{q}, mpz_t @var{n}, @w{unsigned long int @var{d}}) +@deftypefunx {unsigned long int} mpz_cdiv_r_ui (mpz_t @var{r}, mpz_t @var{n}, @w{unsigned long int @var{d}}) +@deftypefunx {unsigned long int} mpz_cdiv_qr_ui (mpz_t @var{q}, mpz_t @var{r}, @w{mpz_t @var{n}}, @w{unsigned long int @var{d}}) +@deftypefunx {unsigned long int} mpz_cdiv_ui (mpz_t @var{n}, @w{unsigned long int @var{d}}) @maybepagebreak -@deftypefunx void mpz_cdiv_q_2exp (mpz_t @var{q}, const mpz_t @var{n}, @w{mp_bitcnt_t @var{b}}) -@deftypefunx void mpz_cdiv_r_2exp (mpz_t @var{r}, const mpz_t @var{n}, @w{mp_bitcnt_t @var{b}}) +@deftypefunx void mpz_cdiv_q_2exp (mpz_t @var{q}, mpz_t @var{n}, @w{unsigned long int @var{b}}) +@deftypefunx void mpz_cdiv_r_2exp (mpz_t @var{r}, mpz_t @var{n}, @w{unsigned long int @var{b}}) @end deftypefun -@deftypefun void mpz_fdiv_q (mpz_t @var{q}, const mpz_t @var{n}, const mpz_t @var{d}) -@deftypefunx void mpz_fdiv_r (mpz_t @var{r}, const mpz_t @var{n}, const mpz_t @var{d}) -@deftypefunx void mpz_fdiv_qr (mpz_t @var{q}, mpz_t @var{r}, const mpz_t @var{n}, const mpz_t @var{d}) +@deftypefun void mpz_fdiv_q (mpz_t @var{q}, mpz_t @var{n}, mpz_t @var{d}) +@deftypefunx void mpz_fdiv_r (mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d}) +@deftypefunx void mpz_fdiv_qr (mpz_t @var{q}, mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d}) @maybepagebreak -@deftypefunx {unsigned long int} mpz_fdiv_q_ui (mpz_t @var{q}, const mpz_t @var{n}, @w{unsigned long int @var{d}}) -@deftypefunx {unsigned long int} mpz_fdiv_r_ui (mpz_t @var{r}, const mpz_t @var{n}, @w{unsigned long int @var{d}}) -@deftypefunx {unsigned long int} mpz_fdiv_qr_ui (mpz_t @var{q}, mpz_t @var{r}, @w{const mpz_t @var{n}}, @w{unsigned long int @var{d}}) -@deftypefunx {unsigned long int} mpz_fdiv_ui (const mpz_t @var{n}, @w{unsigned long int @var{d}}) +@deftypefunx {unsigned long int} mpz_fdiv_q_ui (mpz_t @var{q}, mpz_t @var{n}, @w{unsigned long int @var{d}}) +@deftypefunx {unsigned long int} mpz_fdiv_r_ui (mpz_t @var{r}, mpz_t @var{n}, @w{unsigned long int @var{d}}) +@deftypefunx {unsigned long int} mpz_fdiv_qr_ui (mpz_t @var{q}, mpz_t @var{r}, @w{mpz_t @var{n}}, @w{unsigned long int @var{d}}) +@deftypefunx {unsigned long int} mpz_fdiv_ui (mpz_t @var{n}, @w{unsigned long int @var{d}}) @maybepagebreak -@deftypefunx void mpz_fdiv_q_2exp (mpz_t @var{q}, const mpz_t @var{n}, @w{mp_bitcnt_t @var{b}}) -@deftypefunx void mpz_fdiv_r_2exp (mpz_t @var{r}, const mpz_t @var{n}, @w{mp_bitcnt_t @var{b}}) +@deftypefunx void mpz_fdiv_q_2exp (mpz_t @var{q}, mpz_t @var{n}, @w{unsigned long int @var{b}}) +@deftypefunx void mpz_fdiv_r_2exp (mpz_t @var{r}, mpz_t @var{n}, @w{unsigned long int @var{b}}) @end deftypefun -@deftypefun void mpz_tdiv_q (mpz_t @var{q}, const mpz_t @var{n}, const mpz_t @var{d}) -@deftypefunx void mpz_tdiv_r (mpz_t @var{r}, const mpz_t @var{n}, const mpz_t @var{d}) -@deftypefunx void mpz_tdiv_qr (mpz_t @var{q}, mpz_t @var{r}, const mpz_t @var{n}, const mpz_t @var{d}) +@deftypefun void mpz_tdiv_q (mpz_t @var{q}, mpz_t @var{n}, mpz_t @var{d}) +@deftypefunx void mpz_tdiv_r (mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d}) +@deftypefunx void mpz_tdiv_qr (mpz_t @var{q}, mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d}) @maybepagebreak -@deftypefunx {unsigned long int} mpz_tdiv_q_ui (mpz_t @var{q}, const mpz_t @var{n}, @w{unsigned long int @var{d}}) -@deftypefunx {unsigned long int} mpz_tdiv_r_ui (mpz_t @var{r}, const mpz_t @var{n}, @w{unsigned long int @var{d}}) -@deftypefunx {unsigned long int} mpz_tdiv_qr_ui (mpz_t @var{q}, mpz_t @var{r}, @w{const mpz_t @var{n}}, @w{unsigned long int @var{d}}) -@deftypefunx {unsigned long int} mpz_tdiv_ui (const mpz_t @var{n}, @w{unsigned long int @var{d}}) +@deftypefunx {unsigned long int} mpz_tdiv_q_ui (mpz_t @var{q}, mpz_t @var{n}, @w{unsigned long int @var{d}}) +@deftypefunx {unsigned long int} mpz_tdiv_r_ui (mpz_t @var{r}, mpz_t @var{n}, @w{unsigned long int @var{d}}) +@deftypefunx {unsigned long int} mpz_tdiv_qr_ui (mpz_t @var{q}, mpz_t @var{r}, @w{mpz_t @var{n}}, @w{unsigned long int @var{d}}) +@deftypefunx {unsigned long int} mpz_tdiv_ui (mpz_t @var{n}, @w{unsigned long int @var{d}}) @maybepagebreak -@deftypefunx void mpz_tdiv_q_2exp (mpz_t @var{q}, const mpz_t @var{n}, @w{mp_bitcnt_t @var{b}}) -@deftypefunx void mpz_tdiv_r_2exp (mpz_t @var{r}, const mpz_t @var{n}, @w{mp_bitcnt_t @var{b}}) +@deftypefunx void mpz_tdiv_q_2exp (mpz_t @var{q}, mpz_t @var{n}, @w{unsigned long int @var{b}}) +@deftypefunx void mpz_tdiv_r_2exp (mpz_t @var{r}, mpz_t @var{n}, @w{unsigned long int @var{b}}) @cindex Bit shift right @sp 1 @@ -3371,8 +3348,8 @@ the same as the bitwise logical functions do, whereas @code{mpz_tdiv_q_2exp} effectively treats @var{n} as sign and magnitude. @end deftypefun -@deftypefun void mpz_mod (mpz_t @var{r}, const mpz_t @var{n}, const mpz_t @var{d}) -@deftypefunx {unsigned long int} mpz_mod_ui (mpz_t @var{r}, const mpz_t @var{n}, @w{unsigned long int @var{d}}) +@deftypefun void mpz_mod (mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d}) +@deftypefunx {unsigned long int} mpz_mod_ui (mpz_t @var{r}, mpz_t @var{n}, @w{unsigned long int @var{d}}) Set @var{r} to @var{n} @code{mod} @var{d}. The sign of the divisor is ignored; the result is always non-negative. @@ -3381,8 +3358,8 @@ remainder as well as setting @var{r}. See @code{mpz_fdiv_ui} above if only the return value is wanted. @end deftypefun -@deftypefun void mpz_divexact (mpz_t @var{q}, const mpz_t @var{n}, const mpz_t @var{d}) -@deftypefunx void mpz_divexact_ui (mpz_t @var{q}, const mpz_t @var{n}, unsigned long @var{d}) +@deftypefun void mpz_divexact (mpz_t @var{q}, mpz_t @var{n}, mpz_t @var{d}) +@deftypefunx void mpz_divexact_ui (mpz_t @var{q}, mpz_t @var{n}, unsigned long @var{d}) @cindex Exact division functions Set @var{q} to @var{n}/@var{d}. These functions produce correct results only when it is known in advance that @var{d} divides @var{n}. @@ -3392,9 +3369,9 @@ best choice when exact division is known to occur, for example reducing a rational to lowest terms. @end deftypefun -@deftypefun int mpz_divisible_p (const mpz_t @var{n}, const mpz_t @var{d}) -@deftypefunx int mpz_divisible_ui_p (const mpz_t @var{n}, unsigned long int @var{d}) -@deftypefunx int mpz_divisible_2exp_p (const mpz_t @var{n}, mp_bitcnt_t @var{b}) +@deftypefun int mpz_divisible_p (mpz_t @var{n}, mpz_t @var{d}) +@deftypefunx int mpz_divisible_ui_p (mpz_t @var{n}, unsigned long int @var{d}) +@deftypefunx int mpz_divisible_2exp_p (mpz_t @var{n}, unsigned long int @var{b}) @cindex Divisibility functions Return non-zero if @var{n} is exactly divisible by @var{d}, or in the case of @code{mpz_divisible_2exp_p} by @m{2^b,2^@var{b}}. @@ -3405,9 +3382,9 @@ functions, @math{@var{d}=0} is accepted and following the rule it can be seen that only 0 is considered divisible by 0. @end deftypefun -@deftypefun int mpz_congruent_p (const mpz_t @var{n}, const mpz_t @var{c}, const mpz_t @var{d}) -@deftypefunx int mpz_congruent_ui_p (const mpz_t @var{n}, unsigned long int @var{c}, unsigned long int @var{d}) -@deftypefunx int mpz_congruent_2exp_p (const mpz_t @var{n}, const mpz_t @var{c}, mp_bitcnt_t @var{b}) +@deftypefun int mpz_congruent_p (mpz_t @var{n}, mpz_t @var{c}, mpz_t @var{d}) +@deftypefunx int mpz_congruent_ui_p (mpz_t @var{n}, unsigned long int @var{c}, unsigned long int @var{d}) +@deftypefunx int mpz_congruent_2exp_p (mpz_t @var{n}, mpz_t @var{c}, unsigned long int @var{b}) @cindex Divisibility functions @cindex Congruence functions Return non-zero if @var{n} is congruent to @var{c} modulo @var{d}, or in the @@ -3428,8 +3405,8 @@ only when exactly equal. @cindex Exponentiation functions @cindex Powering functions -@deftypefun void mpz_powm (mpz_t @var{rop}, const mpz_t @var{base}, const mpz_t @var{exp}, const mpz_t @var{mod}) -@deftypefunx void mpz_powm_ui (mpz_t @var{rop}, const mpz_t @var{base}, unsigned long int @var{exp}, const mpz_t @var{mod}) +@deftypefun void mpz_powm (mpz_t @var{rop}, mpz_t @var{base}, mpz_t @var{exp}, mpz_t @var{mod}) +@deftypefunx void mpz_powm_ui (mpz_t @var{rop}, mpz_t @var{base}, unsigned long int @var{exp}, mpz_t @var{mod}) Set @var{rop} to @m{base^{exp} \bmod mod, (@var{base} raised to @var{exp}) modulo @var{mod}}. @@ -3438,20 +3415,7 @@ Negative @var{exp} is supported if an inverse @math{@var{base}^@W{-1} @bmod If an inverse doesn't exist then a divide by zero is raised. @end deftypefun -@deftypefun void mpz_powm_sec (mpz_t @var{rop}, const mpz_t @var{base}, const mpz_t @var{exp}, const mpz_t @var{mod}) -Set @var{rop} to @m{base^{exp} \bmod @var{mod}, (@var{base} raised to @var{exp}) -modulo @var{mod}}. - -It is required that @math{@var{exp} > 0} and that @var{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. -@end deftypefun - -@deftypefun void mpz_pow_ui (mpz_t @var{rop}, const mpz_t @var{base}, unsigned long int @var{exp}) +@deftypefun void mpz_pow_ui (mpz_t @var{rop}, mpz_t @var{base}, unsigned long int @var{exp}) @deftypefunx void mpz_ui_pow_ui (mpz_t @var{rop}, unsigned long int @var{base}, unsigned long int @var{exp}) Set @var{rop} to @m{base^{exp}, @var{base} raised to @var{exp}}. The case @math{0^0} yields 1. @@ -3464,25 +3428,25 @@ Set @var{rop} to @m{base^{exp}, @var{base} raised to @var{exp}}. The case @cindex Integer root functions @cindex Root extraction functions -@deftypefun int mpz_root (mpz_t @var{rop}, const mpz_t @var{op}, unsigned long int @var{n}) +@deftypefun int mpz_root (mpz_t @var{rop}, mpz_t @var{op}, unsigned long int @var{n}) Set @var{rop} to @m{\lfloor\root n \of {op}\rfloor@C{},} the truncated integer part of the @var{n}th root of @var{op}. Return non-zero if the computation was exact, i.e., if @var{op} is @var{rop} to the @var{n}th power. @end deftypefun -@deftypefun void mpz_rootrem (mpz_t @var{root}, mpz_t @var{rem}, const mpz_t @var{u}, unsigned long int @var{n}) +@deftypefun void mpz_rootrem (mpz_t @var{root}, mpz_t @var{rem}, mpz_t @var{u}, unsigned long int @var{n}) Set @var{root} to @m{\lfloor\root n \of {u}\rfloor@C{},} the truncated integer part of the @var{n}th root of @var{u}. Set @var{rem} to the remainder, @m{(@var{u} - @var{root}^n), @var{u}@minus{}@var{root}**@var{n}}. @end deftypefun -@deftypefun void mpz_sqrt (mpz_t @var{rop}, const mpz_t @var{op}) +@deftypefun void mpz_sqrt (mpz_t @var{rop}, mpz_t @var{op}) Set @var{rop} to @m{\lfloor\sqrt{@var{op}}\rfloor@C{},} the truncated integer part of the square root of @var{op}. @end deftypefun -@deftypefun void mpz_sqrtrem (mpz_t @var{rop1}, mpz_t @var{rop2}, const mpz_t @var{op}) +@deftypefun void mpz_sqrtrem (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op}) Set @var{rop1} to @m{\lfloor\sqrt{@var{op}}\rfloor, the truncated integer part of the square root of @var{op}}, like @code{mpz_sqrt}. Set @var{rop2} to the remainder @m{(@var{op} - @var{rop1}^2), @@ -3493,7 +3457,7 @@ If @var{rop1} and @var{rop2} are the same variable, the results are undefined. @end deftypefun -@deftypefun int mpz_perfect_power_p (const mpz_t @var{op}) +@deftypefun int mpz_perfect_power_p (mpz_t @var{op}) @cindex Perfect power functions @cindex Root testing functions Return non-zero if @var{op} is a perfect power, i.e., if there exist integers @@ -3505,7 +3469,7 @@ Negative values of @var{op} are accepted, but of course can only be odd perfect powers. @end deftypefun -@deftypefun int mpz_perfect_square_p (const mpz_t @var{op}) +@deftypefun int mpz_perfect_square_p (mpz_t @var{op}) @cindex Perfect square functions @cindex Root testing functions Return non-zero if @var{op} is a perfect square, i.e., if the square root of @@ -3519,7 +3483,7 @@ be perfect squares. @section Number Theoretic Functions @cindex Number theoretic functions -@deftypefun int mpz_probab_prime_p (const mpz_t @var{n}, int @var{reps}) +@deftypefun int mpz_probab_prime_p (mpz_t @var{n}, int @var{reps}) @cindex Prime testing functions @cindex Probable prime testing functions Determine whether @var{n} is prime. Return 2 if @var{n} is definitely prime, @@ -3527,10 +3491,9 @@ return 1 if @var{n} is probably prime (without being certain), or return 0 if @var{n} is definitely composite. This function does some trial divisions, then some Miller-Rabin probabilistic -primality tests. The argument @var{reps} controls how many such tests are -done; a higher value will reduce the chances of a composite being returned as -``probably prime''. 25 is a reasonable number; a composite number will then be -identified as a prime with a probability of less than @m{2^{-50},2^(-50)}. +primality tests. @var{reps} controls how many such tests are done, 5 to 10 is +a reasonable number, more will reduce the chances of a composite being +returned as ``probably prime''. Miller-Rabin and similar tests can be more properly called compositeness tests. Numbers which fail are known to be composite but those which pass @@ -3538,7 +3501,7 @@ might be prime or might be composite. Only a few composites pass, hence those which pass are considered probably prime. @end deftypefun -@deftypefun void mpz_nextprime (mpz_t @var{rop}, const mpz_t @var{op}) +@deftypefun void mpz_nextprime (mpz_t @var{rop}, mpz_t @var{op}) @cindex Next prime function Set @var{rop} to the next prime greater than @var{op}. @@ -3549,7 +3512,7 @@ extremely small. @c mpz_prime_p not implemented as of gmp 3.0. -@c @deftypefun int mpz_prime_p (const mpz_t @var{n}) +@c @deftypefun int mpz_prime_p (mpz_t @var{n}) @c Return non-zero if @var{n} is prime and zero if @var{n} is a non-prime. @c This function is far slower than @code{mpz_probab_prime_p}, but then it @c never returns non-zero for composite numbers. @@ -3560,15 +3523,15 @@ extremely small. @c prime, if the @var{reps} argument is in the suggested range.) @c @end deftypefun -@deftypefun void mpz_gcd (mpz_t @var{rop}, const mpz_t @var{op1}, const mpz_t @var{op2}) +@deftypefun void mpz_gcd (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) @cindex Greatest common divisor functions @cindex GCD functions -Set @var{rop} to the greatest common divisor of @var{op1} and @var{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 @math{gcd(0,0) = 0}. +Set @var{rop} to the greatest common divisor of @var{op1} and @var{op2}. +The result is always positive even if one or both input operands +are negative. @end deftypefun -@deftypefun {unsigned long int} mpz_gcd_ui (mpz_t @var{rop}, const mpz_t @var{op1}, unsigned long int @var{op2}) +@deftypefun {unsigned long int} mpz_gcd_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) Compute the greatest common divisor of @var{op1} and @var{op2}. If @var{rop} is not @code{NULL}, store the result there. @@ -3578,35 +3541,22 @@ to the argument @var{op1}. Note that the result will always fit if @var{op2} is non-zero. @end deftypefun -@deftypefun void mpz_gcdext (mpz_t @var{g}, mpz_t @var{s}, mpz_t @var{t}, const mpz_t @var{a}, const mpz_t @var{b}) +@deftypefun void mpz_gcdext (mpz_t @var{g}, mpz_t @var{s}, mpz_t @var{t}, mpz_t @var{a}, mpz_t @var{b}) @cindex Extended GCD @cindex GCD extended Set @var{g} to the greatest common divisor of @var{a} and @var{b}, and in addition set @var{s} and @var{t} to coefficients satisfying @math{@var{a}@GMPmultiply{}@var{s} + @var{b}@GMPmultiply{}@var{t} = @var{g}}. The value in @var{g} is always positive, even if one or both of @var{a} and -@var{b} are negative (or zero if both inputs are zero). The values in @var{s} -and @var{t} are chosen such that normally, @math{@GMPabs{@var{s}} < -@GMPabs{@var{b}} / (2 @var{g})} and @math{@GMPabs{@var{t}} < @GMPabs{@var{a}} -/ (2 @var{g})}, and these relations define @var{s} and @var{t} uniquely. There -are a few exceptional cases: - -If @math{@GMPabs{@var{a}} = @GMPabs{@var{b}}}, then @math{@var{s} = 0}, -@math{@var{t} = sgn(@var{b})}. - -Otherwise, @math{@var{s} = sgn(@var{a})} if @math{@var{b} = 0} or -@math{@GMPabs{@var{b}} = 2 @var{g}}, and @math{@var{t} = sgn(@var{b})} if -@math{@var{a} = 0} or @math{@GMPabs{@var{a}} = 2 @var{g}}. - -In all cases, @math{@var{s} = 0} if and only if @math{@var{g} = -@GMPabs{@var{b}}}, i.e., if @var{b} divides @var{a} or @math{@var{a} = @var{b} -= 0}. +@var{b} are negative. The values in @var{s} and @var{t} are chosen such that +@math{@GMPabs{@var{s}} @le{} @GMPabs{@var{b}}} and @math{@GMPabs{@var{t}} +@le{} @GMPabs{@var{a}}}. If @var{t} is @code{NULL} then that value is not computed. @end deftypefun -@deftypefun void mpz_lcm (mpz_t @var{rop}, const mpz_t @var{op1}, const mpz_t @var{op2}) -@deftypefunx void mpz_lcm_ui (mpz_t @var{rop}, const mpz_t @var{op1}, unsigned long @var{op2}) +@deftypefun void mpz_lcm (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx void mpz_lcm_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long @var{op2}) @cindex Least common multiple functions @cindex LCM functions Set @var{rop} to the least common multiple of @var{op1} and @var{op2}. @@ -3614,34 +3564,33 @@ Set @var{rop} to the least common multiple of @var{op1} and @var{op2}. @var{op2}. @var{rop} will be zero if either @var{op1} or @var{op2} is zero. @end deftypefun -@deftypefun int mpz_invert (mpz_t @var{rop}, const mpz_t @var{op1}, const mpz_t @var{op2}) +@deftypefun int mpz_invert (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) @cindex Modular inverse functions @cindex Inverse modulo functions Compute the inverse of @var{op1} modulo @var{op2} and put the result in @var{rop}. If the inverse exists, the return value is non-zero and @var{rop} -will satisfy @math{0 < @var{rop} < @GMPabs{@var{op2}}}. If an inverse doesn't -exist the return value is zero and @var{rop} is undefined. The behaviour of -this function is undefined when @var{op2} is zero. +will satisfy @math{0 @le{} @var{rop} < @var{op2}}. If an inverse doesn't exist +the return value is zero and @var{rop} is undefined. @end deftypefun -@deftypefun int mpz_jacobi (const mpz_t @var{a}, const mpz_t @var{b}) +@deftypefun int mpz_jacobi (mpz_t @var{a}, mpz_t @var{b}) @cindex Jacobi symbol functions Calculate the Jacobi symbol @m{\left(a \over b\right), (@var{a}/@var{b})}. This is defined only for @var{b} odd. @end deftypefun -@deftypefun int mpz_legendre (const mpz_t @var{a}, const mpz_t @var{p}) +@deftypefun int mpz_legendre (mpz_t @var{a}, mpz_t @var{p}) @cindex Legendre symbol functions Calculate the Legendre symbol @m{\left(a \over p\right), (@var{a}/@var{p})}. This is defined only for @var{p} an odd positive prime, and for such @var{p} it's identical to the Jacobi symbol. @end deftypefun -@deftypefun int mpz_kronecker (const mpz_t @var{a}, const mpz_t @var{b}) -@deftypefunx int mpz_kronecker_si (const mpz_t @var{a}, long @var{b}) -@deftypefunx int mpz_kronecker_ui (const mpz_t @var{a}, unsigned long @var{b}) -@deftypefunx int mpz_si_kronecker (long @var{a}, const mpz_t @var{b}) -@deftypefunx int mpz_ui_kronecker (unsigned long @var{a}, const mpz_t @var{b}) +@deftypefun int mpz_kronecker (mpz_t @var{a}, mpz_t @var{b}) +@deftypefunx int mpz_kronecker_si (mpz_t @var{a}, long @var{b}) +@deftypefunx int mpz_kronecker_ui (mpz_t @var{a}, unsigned long @var{b}) +@deftypefunx int mpz_si_kronecker (long @var{a}, mpz_t @var{b}) +@deftypefunx int mpz_ui_kronecker (unsigned long @var{a}, mpz_t @var{b}) @cindex Kronecker symbol functions Calculate the Jacobi symbol @m{\left(a \over b\right), (@var{a}/@var{b})} with the Kronecker extension @m{\left(a \over @@ -3657,7 +3606,7 @@ or any number theory textbook. See also the example program @file{demos/qcn.c} which uses @code{mpz_kronecker_ui}. @end deftypefun -@deftypefun {mp_bitcnt_t} mpz_remove (mpz_t @var{rop}, const mpz_t @var{op}, const mpz_t @var{f}) +@deftypefun {unsigned long int} mpz_remove (mpz_t @var{rop}, mpz_t @var{op}, mpz_t @var{f}) @cindex Remove factor functions @cindex Factor removal functions Remove all occurrences of the factor @var{f} from @var{op} and store the @@ -3665,22 +3614,12 @@ result in @var{rop}. The return value is how many such occurrences were removed. @end deftypefun -@deftypefun void mpz_fac_ui (mpz_t @var{rop}, unsigned long int @var{n}) -@deftypefunx void mpz_2fac_ui (mpz_t @var{rop}, unsigned long int @var{n}) -@deftypefunx void mpz_mfac_uiui (mpz_t @var{rop}, unsigned long int @var{n}, unsigned long int @var{m}) +@deftypefun void mpz_fac_ui (mpz_t @var{rop}, unsigned long int @var{op}) @cindex Factorial functions -Set @var{rop} to the factorial of @var{n}: @code{mpz_fac_ui} computes the plain factorial @var{n}!, -@code{mpz_2fac_ui} computes the double-factorial @var{n}!!, and @code{mpz_mfac_uiui} the -@var{m}-multi-factorial @m{n!^{(m)}, @var{n}!^(@var{m})}. +Set @var{rop} to @var{op}!, the factorial of @var{op}. @end deftypefun -@deftypefun void mpz_primorial_ui (mpz_t @var{rop}, unsigned long int @var{n}) -@cindex Primorial functions -Set @var{rop} to the primorial of @var{n}, i.e. the product of all positive -prime numbers @math{@le{}@var{n}}. -@end deftypefun - -@deftypefun void mpz_bin_ui (mpz_t @var{rop}, const mpz_t @var{n}, unsigned long int @var{k}) +@deftypefun void mpz_bin_ui (mpz_t @var{rop}, mpz_t @var{n}, unsigned long int @var{k}) @deftypefunx void mpz_bin_uiui (mpz_t @var{rop}, unsigned long int @var{n}, @w{unsigned long int @var{k}}) @cindex Binomial coefficient functions Compute the binomial coefficient @m{\left({n}\atop{k}\right), @var{n} over @@ -3729,10 +3668,10 @@ Algorithm}, the reverse is straightforward too. @cindex Integer comparison functions @cindex Comparison functions -@deftypefn Function int mpz_cmp (const mpz_t @var{op1}, const mpz_t @var{op2}) -@deftypefnx Function int mpz_cmp_d (const mpz_t @var{op1}, double @var{op2}) -@deftypefnx Macro int mpz_cmp_si (const mpz_t @var{op1}, signed long int @var{op2}) -@deftypefnx Macro int mpz_cmp_ui (const mpz_t @var{op1}, unsigned long int @var{op2}) +@deftypefn Function int mpz_cmp (mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefnx Function int mpz_cmp_d (mpz_t @var{op1}, double @var{op2}) +@deftypefnx Macro int mpz_cmp_si (mpz_t @var{op1}, signed long int @var{op2}) +@deftypefnx Macro int mpz_cmp_ui (mpz_t @var{op1}, unsigned long int @var{op2}) Compare @var{op1} and @var{op2}. Return a positive value if @math{@var{op1} > @var{op2}}, zero if @math{@var{op1} = @var{op2}}, or a negative value if @math{@var{op1} < @var{op2}}. @@ -3742,9 +3681,9 @@ arguments more than once. @code{mpz_cmp_d} can be called with an infinity, but results are undefined for a NaN. @end deftypefn -@deftypefn Function int mpz_cmpabs (const mpz_t @var{op1}, const mpz_t @var{op2}) -@deftypefnx Function int mpz_cmpabs_d (const mpz_t @var{op1}, double @var{op2}) -@deftypefnx Function int mpz_cmpabs_ui (const mpz_t @var{op1}, unsigned long int @var{op2}) +@deftypefn Function int mpz_cmpabs (mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefnx Function int mpz_cmpabs_d (mpz_t @var{op1}, double @var{op2}) +@deftypefnx Function int mpz_cmpabs_ui (mpz_t @var{op1}, unsigned long int @var{op2}) Compare the absolute values of @var{op1} and @var{op2}. Return a positive value if @math{@GMPabs{@var{op1}} > @GMPabs{@var{op2}}}, zero if @math{@GMPabs{@var{op1}} = @GMPabs{@var{op2}}}, or a negative value if @@ -3754,7 +3693,7 @@ value if @math{@GMPabs{@var{op1}} > @GMPabs{@var{op2}}}, zero if for a NaN. @end deftypefn -@deftypefn Macro int mpz_sgn (const mpz_t @var{op}) +@deftypefn Macro int mpz_sgn (mpz_t @var{op}) @cindex Sign tests @cindex Integer sign tests Return @math{+1} if @math{@var{op} > 0}, 0 if @math{@var{op} = 0}, and @@ -3777,39 +3716,40 @@ These functions behave as if twos complement arithmetic were used (although sign-magnitude is the actual implementation). The least significant bit is number 0. -@deftypefun void mpz_and (mpz_t @var{rop}, const mpz_t @var{op1}, const mpz_t @var{op2}) +@deftypefun void mpz_and (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) Set @var{rop} to @var{op1} bitwise-and @var{op2}. @end deftypefun -@deftypefun void mpz_ior (mpz_t @var{rop}, const mpz_t @var{op1}, const mpz_t @var{op2}) +@deftypefun void mpz_ior (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) Set @var{rop} to @var{op1} bitwise inclusive-or @var{op2}. @end deftypefun -@deftypefun void mpz_xor (mpz_t @var{rop}, const mpz_t @var{op1}, const mpz_t @var{op2}) +@deftypefun void mpz_xor (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) Set @var{rop} to @var{op1} bitwise exclusive-or @var{op2}. @end deftypefun -@deftypefun void mpz_com (mpz_t @var{rop}, const mpz_t @var{op}) +@deftypefun void mpz_com (mpz_t @var{rop}, mpz_t @var{op}) Set @var{rop} to the one's complement of @var{op}. @end deftypefun -@deftypefun {mp_bitcnt_t} mpz_popcount (const mpz_t @var{op}) -If @math{@var{op}@ge{}0}, return the population count of @var{op}, which is the -number of 1 bits in the binary representation. If @math{@var{op}<0}, the -number of 1s is infinite, and the return value is the largest possible -@code{mp_bitcnt_t}. +@deftypefun {unsigned long int} mpz_popcount (mpz_t @var{op}) +If @math{@var{op}@ge{}0}, return the population count of @var{op}, which is +the number of 1 bits in the binary representation. If @math{@var{op}<0}, the +number of 1s is infinite, and the return value is @var{ULONG_MAX}, the largest +possible @code{unsigned long}. @end deftypefun -@deftypefun {mp_bitcnt_t} mpz_hamdist (const mpz_t @var{op1}, const mpz_t @var{op2}) -If @var{op1} and @var{op2} are both @math{@ge{}0} or both @math{<0}, return the -hamming distance between the two operands, which is the number of bit positions -where @var{op1} and @var{op2} have different bit values. If one operand is -@math{@ge{}0} and the other @math{<0} then the number of bits different is -infinite, and the return value is the largest possible @code{mp_bitcnt_t}. +@deftypefun {unsigned long int} mpz_hamdist (mpz_t @var{op1}, mpz_t @var{op2}) +If @var{op1} and @var{op2} are both @math{@ge{}0} or both @math{<0}, return +the hamming distance between the two operands, which is the number of bit +positions where @var{op1} and @var{op2} have different bit values. If one +operand is @math{@ge{}0} and the other @math{<0} then the number of bits +different is infinite, and the return value is @var{ULONG_MAX}, the largest +possible @code{unsigned long}. @end deftypefun -@deftypefun {mp_bitcnt_t} mpz_scan0 (const mpz_t @var{op}, mp_bitcnt_t @var{starting_bit}) -@deftypefunx {mp_bitcnt_t} mpz_scan1 (const mpz_t @var{op}, mp_bitcnt_t @var{starting_bit}) +@deftypefun {unsigned long int} mpz_scan0 (mpz_t @var{op}, unsigned long int @var{starting_bit}) +@deftypefunx {unsigned long int} mpz_scan1 (mpz_t @var{op}, unsigned long int @var{starting_bit}) @cindex Bit scanning functions @cindex Scan bit functions Scan @var{op}, starting from bit @var{starting_bit}, towards more significant @@ -3819,24 +3759,24 @@ the found bit. If the bit at @var{starting_bit} is already what's sought, then @var{starting_bit} is returned. -If there's no bit found, then the largest possible @code{mp_bitcnt_t} is -returned. This will happen in @code{mpz_scan0} past the end of a negative -number, or @code{mpz_scan1} past the end of a nonnegative number. +If there's no bit found, then @var{ULONG_MAX} is returned. This will happen +in @code{mpz_scan0} past the end of a negative number, or @code{mpz_scan1} +past the end of a nonnegative number. @end deftypefun -@deftypefun void mpz_setbit (mpz_t @var{rop}, mp_bitcnt_t @var{bit_index}) +@deftypefun void mpz_setbit (mpz_t @var{rop}, unsigned long int @var{bit_index}) Set bit @var{bit_index} in @var{rop}. @end deftypefun -@deftypefun void mpz_clrbit (mpz_t @var{rop}, mp_bitcnt_t @var{bit_index}) +@deftypefun void mpz_clrbit (mpz_t @var{rop}, unsigned long int @var{bit_index}) Clear bit @var{bit_index} in @var{rop}. @end deftypefun -@deftypefun void mpz_combit (mpz_t @var{rop}, mp_bitcnt_t @var{bit_index}) +@deftypefun void mpz_combit (mpz_t @var{rop}, unsigned long int @var{bit_index}) Complement bit @var{bit_index} in @var{rop}. @end deftypefun -@deftypefun int mpz_tstbit (const mpz_t @var{op}, mp_bitcnt_t @var{bit_index}) +@deftypefun int mpz_tstbit (mpz_t @var{op}, unsigned long int @var{bit_index}) Test bit @var{bit_index} in @var{op} and return 0 or 1 accordingly. @end deftypefun @@ -3849,17 +3789,15 @@ Test bit @var{bit_index} in @var{op} and return 0 or 1 accordingly. @cindex I/O functions Functions that perform input from a stdio stream, and functions that output to -a stdio stream, of @code{mpz} numbers. Passing a @code{NULL} pointer for a -@var{stream} argument to any of these functions will make them read from -@code{stdin} and write to @code{stdout}, respectively. +a stdio stream. Passing a @code{NULL} pointer for a @var{stream} argument to any of +these functions will make them read from @code{stdin} and write to +@code{stdout}, respectively. When using any of these functions, it is a good idea to include @file{stdio.h} before @file{gmp.h}, since that will allow @file{gmp.h} to define prototypes for these functions. -See also @ref{Formatted Output} and @ref{Formatted Input}. - -@deftypefun size_t mpz_out_str (FILE *@var{stream}, int @var{base}, const mpz_t @var{op}) +@deftypefun size_t mpz_out_str (FILE *@var{stream}, int @var{base}, mpz_t @var{op}) Output @var{op} on stdio stream @var{stream}, as a string of digits in base @var{base}. The base argument may vary from 2 to 62 or from @minus{}2 to @minus{}36. @@ -3887,7 +3825,7 @@ the same value. For bases 37 to 62, upper-case letter represent the usual Return the number of bytes read, or if an error occurred, return 0. @end deftypefun -@deftypefun size_t mpz_out_raw (FILE *@var{stream}, const mpz_t @var{op}) +@deftypefun size_t mpz_out_raw (FILE *@var{stream}, mpz_t @var{op}) Output @var{op} on stdio stream @var{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 @@ -3925,7 +3863,7 @@ parameter that is read and modified. Please see the @ref{Random Number Functions} for more information on how to use and not to use random number functions. -@deftypefun void mpz_urandomb (mpz_t @var{rop}, gmp_randstate_t @var{state}, mp_bitcnt_t @var{n}) +@deftypefun void mpz_urandomb (mpz_t @var{rop}, gmp_randstate_t @var{state}, unsigned long int @var{n}) Generate a uniformly distributed random integer in the range 0 to @m{2^n-1, 2^@var{n}@minus{}1}, inclusive. @@ -3934,7 +3872,7 @@ The variable @var{state} must be initialized by calling one of the invoking this function. @end deftypefun -@deftypefun void mpz_urandomm (mpz_t @var{rop}, gmp_randstate_t @var{state}, const mpz_t @var{n}) +@deftypefun void mpz_urandomm (mpz_t @var{rop}, gmp_randstate_t @var{state}, mpz_t @var{n}) Generate a uniform random integer in the range 0 to @math{@var{n}-1}, inclusive. @@ -3943,7 +3881,7 @@ The variable @var{state} must be initialized by calling one of the before invoking this function. @end deftypefun -@deftypefun void mpz_rrandomb (mpz_t @var{rop}, gmp_randstate_t @var{state}, mp_bitcnt_t @var{n}) +@deftypefun void mpz_rrandomb (mpz_t @var{rop}, gmp_randstate_t @var{state}, unsigned long int @var{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 @@ -4017,7 +3955,7 @@ feature can account for this, by passing for instance @code{8*sizeof(int)-INT_BIT}. @end deftypefun -@deftypefun {void *} mpz_export (void *@var{rop}, size_t *@var{countp}, int @var{order}, size_t @var{size}, int @var{endian}, size_t @var{nails}, const mpz_t @var{op}) +@deftypefun {void *} mpz_export (void *@var{rop}, size_t *@var{countp}, int @var{order}, size_t @var{size}, int @var{endian}, size_t @var{nails}, mpz_t @var{op}) @cindex Integer export @cindex Export Fill @var{rop} with word data from @var{op}. @@ -4068,24 +4006,24 @@ p = malloc (count * size); @cindex Miscellaneous integer functions @cindex Integer miscellaneous functions -@deftypefun int mpz_fits_ulong_p (const mpz_t @var{op}) -@deftypefunx int mpz_fits_slong_p (const mpz_t @var{op}) -@deftypefunx int mpz_fits_uint_p (const mpz_t @var{op}) -@deftypefunx int mpz_fits_sint_p (const mpz_t @var{op}) -@deftypefunx int mpz_fits_ushort_p (const mpz_t @var{op}) -@deftypefunx int mpz_fits_sshort_p (const mpz_t @var{op}) +@deftypefun int mpz_fits_ulong_p (mpz_t @var{op}) +@deftypefunx int mpz_fits_slong_p (mpz_t @var{op}) +@deftypefunx int mpz_fits_uint_p (mpz_t @var{op}) +@deftypefunx int mpz_fits_sint_p (mpz_t @var{op}) +@deftypefunx int mpz_fits_ushort_p (mpz_t @var{op}) +@deftypefunx int mpz_fits_sshort_p (mpz_t @var{op}) Return non-zero iff the value of @var{op} fits in an @code{unsigned long int}, @code{signed long int}, @code{unsigned int}, @code{signed int}, @code{unsigned short int}, or @code{signed short int}, respectively. Otherwise, return zero. @end deftypefun -@deftypefn Macro int mpz_odd_p (const mpz_t @var{op}) -@deftypefnx Macro int mpz_even_p (const mpz_t @var{op}) +@deftypefn Macro int mpz_odd_p (mpz_t @var{op}) +@deftypefnx Macro int mpz_even_p (mpz_t @var{op}) Determine whether @var{op} is odd or even, respectively. Return non-zero if yes, zero if no. These macros evaluate their argument more than once. @end deftypefn -@deftypefun size_t mpz_sizeinbase (const mpz_t @var{op}, int @var{base}) +@deftypefun size_t mpz_sizeinbase (mpz_t @var{op}, int @var{base}) @cindex Size in digits @cindex Digits in an integer Return the size of @var{op} measured in number of digits in the given @@ -4116,7 +4054,57 @@ The functions in this section are for various special purposes. Most applications will not need them. @deftypefun void mpz_array_init (mpz_t @var{integer_array}, mp_size_t @var{array_size}, @w{mp_size_t @var{fixed_num_bits}}) -@strong{This is an obsolete function. Do not use it.} +This is a special type of initialization. @strong{Fixed} space of +@var{fixed_num_bits} is allocated to each of the @var{array_size} integers in +@var{integer_array}. There is no way to free the storage allocated by this +function. Don't call @code{mpz_clear}! + +The @var{integer_array} parameter is the first @code{mpz_t} in the array. For +example, + +@example +mpz_t arr[20000]; +mpz_array_init (arr[0], 20000, 512); +@end example + +@c In case anyone's wondering, yes this parameter style is a bit anomalous, +@c it'd probably be nicer if it was "arr" instead of "arr[0]". Obviously the +@c two differ only in the declaration, not the pointer value, but changing is +@c not possible since it'd provoke warnings or errors in existing sources. + +This function is only intended for programs that create a large number +of integers and need to reduce memory usage by avoiding the overheads of +allocating and reallocating lots of small blocks. In normal programs this +function is not recommended. + +The space allocated to each integer by this function will not be automatically +increased, unlike the normal @code{mpz_init}, so an application must ensure it +is sufficient for any value stored. The following space requirements apply to +various routines, + +@itemize @bullet +@item +@code{mpz_abs}, @code{mpz_neg}, @code{mpz_set}, @code{mpz_set_si} and +@code{mpz_set_ui} need room for the value they store. + +@item +@code{mpz_add}, @code{mpz_add_ui}, @code{mpz_sub} and @code{mpz_sub_ui} need +room for the larger of the two operands, plus an extra +@code{mp_bits_per_limb}. + +@item +@code{mpz_mul}, @code{mpz_mul_ui} and @code{mpz_mul_ui} need room for the sum +of the number of bits in their operands, but each rounded up to a multiple of +@code{mp_bits_per_limb}. + +@item +@code{mpz_swap} can be used between two array variables, but not between an +array and a normal variable. +@end itemize + +For other functions, or if in doubt, the suggestion is to calculate in a +regular @code{mpz_init} variable and copy the result to an array variable with +@code{mpz_set}. @end deftypefun @deftypefun {void *} _mpz_realloc (mpz_t @var{integer}, mp_size_t @var{new_alloc}) @@ -4129,7 +4117,7 @@ this. @code{mpz_realloc2} and @code{_mpz_realloc} are the same except that @code{_mpz_realloc} takes its size in limbs. @end deftypefun -@deftypefun mp_limb_t mpz_getlimbn (const mpz_t @var{op}, mp_size_t @var{n}) +@deftypefun mp_limb_t mpz_getlimbn (mpz_t @var{op}, mp_size_t @var{n}) Return limb number @var{n} from @var{op}. The sign of @var{op} is ignored, just the absolute value is used. The least significant limb is number 0. @@ -4138,88 +4126,12 @@ just the absolute value is used. The least significant limb is number 0. @code{mpz_size(@var{op})-1}. @end deftypefun -@deftypefun size_t mpz_size (const mpz_t @var{op}) +@deftypefun size_t mpz_size (mpz_t @var{op}) Return the size of @var{op} measured in number of limbs. If @var{op} is zero, the returned value will be zero. @c (@xref{Nomenclature}, for an explanation of the concept @dfn{limb}.) @end deftypefun -@deftypefun {const mp_limb_t *} mpz_limbs_read (const mpz_t @var{x}) -Return a pointer to the limb array representing the absolute value of @var{x}. -The size of the array is @code{mpz_size(@var{x})}. Intended for read access -only. -@end deftypefun - -@deftypefun {mp_limb_t *} mpz_limbs_write (mpz_t @var{x}, mp_size_t @var{n}) -@deftypefunx {mp_limb_t *} mpz_limbs_modify (mpz_t @var{x}, mp_size_t @var{n}) -Return a pointer to the limb array, intended for write access. The array is -reallocated as needed, to make room for @var{n} limbs. Requires @math{@var{n} -> 0}. The @code{mpz_limbs_modify} function returns an array that holds the old -absolute value of @var{x}, while @code{mpz_limbs_write} may destroy the old -value and return an array with unspecified contents. -@end deftypefun - -@deftypefun void mpz_limbs_finish (mpz_t @var{x}, mp_size_t @var{s}) -Updates the internal size field of @var{x}. Used after writing to the limb -array pointer returned by @code{mpz_limbs_write} or @code{mpz_limbs_modify} is -completed. The array should contain @math{@GMPabs{@var{s}}} valid limbs, -representing the new absolute value for @var{x}, and the sign of @var{x} is -taken from the sign of @var{s}. This function never reallocates @var{x}, so -the limb pointer remains valid. -@end deftypefun - -@c FIXME: Some more useful and less silly example? -@example -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); -@} -@end example - -@deftypefun mpz_srcptr mpz_roinit_n (mpz_t @var{x}, const mp_limb_t *@var{xp}, mp_size_t @var{xs}) -Special initialization of @var{x}, using the given limb array and size. -@var{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 @var{xp} must point to at -least a readable limb, its size is -@math{@GMPabs{@var{xs}}}, and the sign of @var{x} is the sign of @var{xs}. For -convenience, the function returns @var{x}, but cast to a const pointer type. -@end deftypefun - -@example -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)); -@} -@end example - -@deftypefn Macro mpz_t MPZ_ROINIT_N (mp_limb_t *@var{xp}, mp_size_t @var{xs}) -This macro expands to an initializer which can be assigned to an mpz_t -variable. The limb array @var{xp} must point to at least a readable limb, -moreover, unlike the @code{mpz_roinit_n} function, the array must be -normalized: if @var{xs} is non-zero, then -@code{@var{xp}[@math{@GMPabs{@var{xs}}-1}]} must be non-zero. Intended -primarily for constant values. Using it for non-constant values requires a C -compiler supporting C99. -@end deftypefn - -@example -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); -@} -@end example @node Rational Number Functions, Floating-point Functions, Integer Functions, Top @@ -4269,22 +4181,13 @@ initialized once, or at least cleared out (using the function @code{mpq_clear}) between each initialization. @end deftypefun -@deftypefun void mpq_inits (mpq_t @var{x}, ...) -Initialize a NULL-terminated list of @code{mpq_t} variables, and set their -values to 0/1. -@end deftypefun - @deftypefun void mpq_clear (mpq_t @var{x}) Free the space occupied by @var{x}. Make sure to call this function for all @code{mpq_t} variables when you are done with them. @end deftypefun -@deftypefun void mpq_clears (mpq_t @var{x}, ...) -Free the space occupied by a NULL-terminated list of @code{mpq_t} variables. -@end deftypefun - -@deftypefun void mpq_set (mpq_t @var{rop}, const mpq_t @var{op}) -@deftypefunx void mpq_set_z (mpq_t @var{rop}, const mpz_t @var{op}) +@deftypefun void mpq_set (mpq_t @var{rop}, mpq_t @var{op}) +@deftypefunx void mpq_set_z (mpq_t @var{rop}, mpz_t @var{op}) Assign @var{rop} from @var{op}. @end deftypefun @@ -4295,7 +4198,7 @@ Set the value of @var{rop} to @var{op1}/@var{op2}. Note that if @var{op1} and @code{mpq_canonicalize} before any operations are performed on @var{rop}. @end deftypefun -@deftypefun int mpq_set_str (mpq_t @var{rop}, const char *@var{str}, int @var{base}) +@deftypefun int mpq_set_str (mpq_t @var{rop}, char *@var{str}, int @var{base}) Set @var{rop} from a null-terminated string @var{str} in the given @var{base}. The string can be an integer like ``41'' or a fraction like ``41/152''. The @@ -4327,8 +4230,8 @@ Swap the values @var{rop1} and @var{rop2} efficiently. @cindex Rational conversion functions @cindex Conversion functions -@deftypefun double mpq_get_d (const mpq_t @var{op}) -Convert @var{op} to a @code{double}, truncating if necessary (i.e.@: rounding +@deftypefun double mpq_get_d (mpq_t @var{op}) +Convert @var{op} to a @code{double}, truncating if necessary (ie.@: rounding towards zero). If the exponent from the conversion is too big or too small to fit a @@ -4338,12 +4241,12 @@ Hardware overflow, underflow and denorm traps may or may not occur. @end deftypefun @deftypefun void mpq_set_d (mpq_t @var{rop}, double @var{op}) -@deftypefunx void mpq_set_f (mpq_t @var{rop}, const mpf_t @var{op}) +@deftypefunx void mpq_set_f (mpq_t @var{rop}, mpf_t @var{op}) Set @var{rop} to the value of @var{op}. There is no rounding, this conversion is exact. @end deftypefun -@deftypefun {char *} mpq_get_str (char *@var{str}, int @var{base}, const mpq_t @var{op}) +@deftypefun {char *} mpq_get_str (char *@var{str}, int @var{base}, mpq_t @var{op}) Convert @var{op} to a string of digits in base @var{base}. The base may vary from 2 to 36. The string will be of the form @samp{num/den}, or if the denominator is 1 then just @samp{num}. @@ -4375,42 +4278,42 @@ or the given @var{str}. @cindex Rational arithmetic functions @cindex Arithmetic functions -@deftypefun void mpq_add (mpq_t @var{sum}, const mpq_t @var{addend1}, const mpq_t @var{addend2}) +@deftypefun void mpq_add (mpq_t @var{sum}, mpq_t @var{addend1}, mpq_t @var{addend2}) Set @var{sum} to @var{addend1} + @var{addend2}. @end deftypefun -@deftypefun void mpq_sub (mpq_t @var{difference}, const mpq_t @var{minuend}, const mpq_t @var{subtrahend}) +@deftypefun void mpq_sub (mpq_t @var{difference}, mpq_t @var{minuend}, mpq_t @var{subtrahend}) Set @var{difference} to @var{minuend} @minus{} @var{subtrahend}. @end deftypefun -@deftypefun void mpq_mul (mpq_t @var{product}, const mpq_t @var{multiplier}, const mpq_t @var{multiplicand}) +@deftypefun void mpq_mul (mpq_t @var{product}, mpq_t @var{multiplier}, mpq_t @var{multiplicand}) Set @var{product} to @math{@var{multiplier} @GMPtimes{} @var{multiplicand}}. @end deftypefun -@deftypefun void mpq_mul_2exp (mpq_t @var{rop}, const mpq_t @var{op1}, mp_bitcnt_t @var{op2}) +@deftypefun void mpq_mul_2exp (mpq_t @var{rop}, mpq_t @var{op1}, unsigned long int @var{op2}) Set @var{rop} to @m{@var{op1} \times 2^{op2}, @var{op1} times 2 raised to @var{op2}}. @end deftypefun -@deftypefun void mpq_div (mpq_t @var{quotient}, const mpq_t @var{dividend}, const mpq_t @var{divisor}) +@deftypefun void mpq_div (mpq_t @var{quotient}, mpq_t @var{dividend}, mpq_t @var{divisor}) @cindex Division functions Set @var{quotient} to @var{dividend}/@var{divisor}. @end deftypefun -@deftypefun void mpq_div_2exp (mpq_t @var{rop}, const mpq_t @var{op1}, mp_bitcnt_t @var{op2}) +@deftypefun void mpq_div_2exp (mpq_t @var{rop}, mpq_t @var{op1}, unsigned long int @var{op2}) Set @var{rop} to @m{@var{op1}/2^{op2}, @var{op1} divided by 2 raised to @var{op2}}. @end deftypefun -@deftypefun void mpq_neg (mpq_t @var{negated_operand}, const mpq_t @var{operand}) +@deftypefun void mpq_neg (mpq_t @var{negated_operand}, mpq_t @var{operand}) Set @var{negated_operand} to @minus{}@var{operand}. @end deftypefun -@deftypefun void mpq_abs (mpq_t @var{rop}, const mpq_t @var{op}) +@deftypefun void mpq_abs (mpq_t @var{rop}, mpq_t @var{op}) Set @var{rop} to the absolute value of @var{op}. @end deftypefun -@deftypefun void mpq_inv (mpq_t @var{inverted_number}, const mpq_t @var{number}) +@deftypefun void mpq_inv (mpq_t @var{inverted_number}, mpq_t @var{number}) Set @var{inverted_number} to 1/@var{number}. If the new denominator is zero, this routine will divide by zero. @end deftypefun @@ -4421,7 +4324,7 @@ zero, this routine will divide by zero. @cindex Rational comparison functions @cindex Comparison functions -@deftypefun int mpq_cmp (const mpq_t @var{op1}, const mpq_t @var{op2}) +@deftypefun int mpq_cmp (mpq_t @var{op1}, mpq_t @var{op2}) Compare @var{op1} and @var{op2}. Return a positive value if @math{@var{op1} > @var{op2}}, zero if @math{@var{op1} = @var{op2}}, and a negative value if @math{@var{op1} < @var{op2}}. @@ -4430,8 +4333,8 @@ To determine if two rationals are equal, @code{mpq_equal} is faster than @code{mpq_cmp}. @end deftypefun -@deftypefn Macro int mpq_cmp_ui (const mpq_t @var{op1}, unsigned long int @var{num2}, unsigned long int @var{den2}) -@deftypefnx Macro int mpq_cmp_si (const mpq_t @var{op1}, long int @var{num2}, unsigned long int @var{den2}) +@deftypefn Macro int mpq_cmp_ui (mpq_t @var{op1}, unsigned long int @var{num2}, unsigned long int @var{den2}) +@deftypefnx Macro int mpq_cmp_si (mpq_t @var{op1}, long int @var{num2}, unsigned long int @var{den2}) Compare @var{op1} and @var{num2}/@var{den2}. Return a positive value if @math{@var{op1} > @var{num2}/@var{den2}}, zero if @math{@var{op1} = @var{num2}/@var{den2}}, and a negative value if @math{@var{op1} < @@ -4443,17 +4346,17 @@ These functions are implemented as a macros and evaluate their arguments multiple times. @end deftypefn -@deftypefn Macro int mpq_sgn (const mpq_t @var{op}) +@deftypefn Macro int mpq_sgn (mpq_t @var{op}) @cindex Sign tests @cindex Rational sign tests Return @math{+1} if @math{@var{op} > 0}, 0 if @math{@var{op} = 0}, and @math{-1} if @math{@var{op} < 0}. This function is actually implemented as a macro. It evaluates its -argument multiple times. +arguments multiple times. @end deftypefn -@deftypefun int mpq_equal (const mpq_t @var{op1}, const mpq_t @var{op2}) +@deftypefun int mpq_equal (mpq_t @var{op1}, mpq_t @var{op2}) Return non-zero if @var{op1} and @var{op2} are equal, zero if they are non-equal. Although @code{mpq_cmp} can be used for the same purpose, this function is much faster. @@ -4474,16 +4377,16 @@ Note that if an assignment to the numerator and/or denominator could take an (@pxref{Rational Number Functions}) then @code{mpq_canonicalize} must be called before any other @code{mpq} functions are applied to that @code{mpq_t}. -@deftypefn Macro mpz_t mpq_numref (const mpq_t @var{op}) -@deftypefnx Macro mpz_t mpq_denref (const mpq_t @var{op}) +@deftypefn Macro mpz_t mpq_numref (mpq_t @var{op}) +@deftypefnx Macro mpz_t mpq_denref (mpq_t @var{op}) Return a reference to the numerator and denominator of @var{op}, respectively. The @code{mpz} functions can be used on the result of these macros. @end deftypefn -@deftypefun void mpq_get_num (mpz_t @var{numerator}, const mpq_t @var{rational}) -@deftypefunx void mpq_get_den (mpz_t @var{denominator}, const mpq_t @var{rational}) -@deftypefunx void mpq_set_num (mpq_t @var{rational}, const mpz_t @var{numerator}) -@deftypefunx void mpq_set_den (mpq_t @var{rational}, const mpz_t @var{denominator}) +@deftypefun void mpq_get_num (mpz_t @var{numerator}, mpq_t @var{rational}) +@deftypefunx void mpq_get_den (mpz_t @var{denominator}, mpq_t @var{rational}) +@deftypefunx void mpq_set_num (mpq_t @var{rational}, mpz_t @var{numerator}) +@deftypefunx void mpq_set_den (mpq_t @var{rational}, mpz_t @var{denominator}) Get or set the numerator or denominator of a rational. These functions are equivalent to calling @code{mpz_set} with an appropriate @code{mpq_numref} or @code{mpq_denref}. Direct use of @code{mpq_numref} or @code{mpq_denref} is @@ -4500,18 +4403,15 @@ recommended instead of these functions. @cindex Output functions @cindex I/O functions -Functions that perform input from a stdio stream, and functions that output to -a stdio stream, of @code{mpq} numbers. Passing a @code{NULL} pointer for a -@var{stream} argument to any of these functions will make them read from -@code{stdin} and write to @code{stdout}, respectively. - -When using any of these functions, it is a good idea to include @file{stdio.h} +When using any of these functions, it's a good idea to include @file{stdio.h} before @file{gmp.h}, since that will allow @file{gmp.h} to define prototypes for these functions. -See also @ref{Formatted Output} and @ref{Formatted Input}. +Passing a @code{NULL} pointer for a @var{stream} argument to any of these +functions will make them read from @code{stdin} and write to @code{stdout}, +respectively. -@deftypefun size_t mpq_out_str (FILE *@var{stream}, int @var{base}, const mpq_t @var{op}) +@deftypefun size_t mpq_out_str (FILE *@var{stream}, int @var{base}, mpq_t @var{op}) Output @var{op} on stdio stream @var{stream}, as a string of digits in base @var{base}. The base may vary from 2 to 36. Output is in the form @samp{num/den} or if the denominator is 1 then just @samp{num}. @@ -4559,7 +4459,7 @@ The exponent of each float is a fixed precision, one machine word on most systems. In the current implementation the exponent is a count of limbs, so for example on a 32-bit system this means a range of roughly @math{2^@W{-68719476768}} to @math{2^@W{68719476736}}, or on a 64-bit system -this will be greater. Note however that @code{mpf_get_str} can only return an +this will be greater. Note however @code{mpf_get_str} can only return an exponent which fits an @code{mp_exp_t} and currently @code{mpf_set_str} doesn't accept exponents bigger than a @code{long}. @@ -4572,19 +4472,21 @@ Each function is defined to calculate with ``infinite precision'' followed by a truncation to the destination precision, but of course the work done is only what's needed to determine a result under that definition. -The precision selected by the user for a variable is a minimum value, GMP may -increase it to facilitate efficient calculation. Currently this means -rounding up to a whole limb, and then sometimes having a further partial limb, -depending on the high limb of the mantissa. +The precision selected for a variable is a minimum value, GMP may increase it +a little to facilitate efficient calculation. Currently this means rounding +up to a whole limb, and then sometimes having a further partial limb, +depending on the high limb of the mantissa. But applications shouldn't be +concerned by such details. -The mantissa is stored in binary. One consequence of this is that decimal +The mantissa in stored in binary, as might be imagined from the fact +precisions are expressed in bits. One consequence of this is that decimal fractions like @math{0.1} cannot be represented exactly. The same is true of plain IEEE @code{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 @code{mpf} functions and variables have no special notion of infinity or +@code{mpf} functions and variables have no special notion of infinity or not-a-number, and applications must take care not to overflow the exponent or results will be unpredictable. This might change in a future release. @@ -4593,10 +4495,6 @@ 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. -The GMP extension library MPFR (@url{http://mpfr.org}) is an alternative to -GMP's @code{mpf} functions. MPFR provides well-defined precision and accurate -rounding, and thereby naturally extends IEEE P754. - @menu * Initializing Floats:: * Assigning Floats:: @@ -4614,13 +4512,13 @@ rounding, and thereby naturally extends IEEE P754. @cindex Float initialization functions @cindex Initialization functions -@deftypefun void mpf_set_default_prec (mp_bitcnt_t @var{prec}) +@deftypefun void mpf_set_default_prec (unsigned long int @var{prec}) Set the default precision to be @strong{at least} @var{prec} bits. All subsequent calls to @code{mpf_init} will use this precision, but previously initialized variables are unaffected. @end deftypefun -@deftypefun {mp_bitcnt_t} mpf_get_default_prec (void) +@deftypefun {unsigned long int} mpf_get_default_prec (void) Return the default precision actually used. @end deftypefun @@ -4635,28 +4533,17 @@ precision of @var{x} is undefined unless a default precision has already been established by a call to @code{mpf_set_default_prec}. @end deftypefun -@deftypefun void mpf_init2 (mpf_t @var{x}, mp_bitcnt_t @var{prec}) +@deftypefun void mpf_init2 (mpf_t @var{x}, unsigned long int @var{prec}) Initialize @var{x} to 0 and set its precision to be @strong{at least} @var{prec} bits. Normally, a variable should be initialized once only or at least be cleared, using @code{mpf_clear}, between initializations. @end deftypefun -@deftypefun void mpf_inits (mpf_t @var{x}, ...) -Initialize a NULL-terminated list of @code{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 -@code{mpf_set_default_prec}. -@end deftypefun - @deftypefun void mpf_clear (mpf_t @var{x}) Free the space occupied by @var{x}. Make sure to call this function for all @code{mpf_t} variables when you are done with them. @end deftypefun -@deftypefun void mpf_clears (mpf_t @var{x}, ...) -Free the space occupied by a NULL-terminated list of @code{mpf_t} variables. -@end deftypefun - @need 2000 Here is an example on how to initialize floating-point variables: @example @@ -4676,11 +4563,11 @@ 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. -@deftypefun {mp_bitcnt_t} mpf_get_prec (const mpf_t @var{op}) +@deftypefun {unsigned long int} mpf_get_prec (mpf_t @var{op}) Return the current precision of @var{op}, in bits. @end deftypefun -@deftypefun void mpf_set_prec (mpf_t @var{rop}, mp_bitcnt_t @var{prec}) +@deftypefun void mpf_set_prec (mpf_t @var{rop}, unsigned long int @var{prec}) Set the precision of @var{rop} to be @strong{at least} @var{prec} bits. The value in @var{rop} will be truncated to the new precision. @@ -4688,7 +4575,7 @@ This function requires a call to @code{realloc}, and so should not be used in a tight loop. @end deftypefun -@deftypefun void mpf_set_prec_raw (mpf_t @var{rop}, mp_bitcnt_t @var{prec}) +@deftypefun void mpf_set_prec_raw (mpf_t @var{rop}, unsigned long int @var{prec}) Set the precision of @var{rop} to be @strong{at least} @var{prec} bits, without changing the memory allocated. @@ -4725,16 +4612,16 @@ different purposes during a calculation. These functions assign new values to already initialized floats (@pxref{Initializing Floats}). -@deftypefun void mpf_set (mpf_t @var{rop}, const mpf_t @var{op}) +@deftypefun void mpf_set (mpf_t @var{rop}, mpf_t @var{op}) @deftypefunx void mpf_set_ui (mpf_t @var{rop}, unsigned long int @var{op}) @deftypefunx void mpf_set_si (mpf_t @var{rop}, signed long int @var{op}) @deftypefunx void mpf_set_d (mpf_t @var{rop}, double @var{op}) -@deftypefunx void mpf_set_z (mpf_t @var{rop}, const mpz_t @var{op}) -@deftypefunx void mpf_set_q (mpf_t @var{rop}, const mpq_t @var{op}) +@deftypefunx void mpf_set_z (mpf_t @var{rop}, mpz_t @var{op}) +@deftypefunx void mpf_set_q (mpf_t @var{rop}, mpq_t @var{op}) Set the value of @var{rop} from @var{op}. @end deftypefun -@deftypefun int mpf_set_str (mpf_t @var{rop}, const char *@var{str}, int @var{base}) +@deftypefun int mpf_set_str (mpf_t @var{rop}, char *@var{str}, int @var{base}) Set the value of @var{rop} from the string in @var{str}. The string is of the form @samp{M@@N} or, if the base is 10 or less, alternatively @samp{MeN}. @samp{M} is the mantissa and @samp{N} is the exponent. The mantissa is always @@ -4789,7 +4676,7 @@ 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! -@deftypefun void mpf_init_set (mpf_t @var{rop}, const mpf_t @var{op}) +@deftypefun void mpf_init_set (mpf_t @var{rop}, mpf_t @var{op}) @deftypefunx void mpf_init_set_ui (mpf_t @var{rop}, unsigned long int @var{op}) @deftypefunx void mpf_init_set_si (mpf_t @var{rop}, signed long int @var{op}) @deftypefunx void mpf_init_set_d (mpf_t @var{rop}, double @var{op}) @@ -4799,7 +4686,7 @@ The precision of @var{rop} will be taken from the active default precision, as set by @code{mpf_set_default_prec}. @end deftypefun -@deftypefun int mpf_init_set_str (mpf_t @var{rop}, const char *@var{str}, int @var{base}) +@deftypefun int mpf_init_set_str (mpf_t @var{rop}, char *@var{str}, int @var{base}) Initialize @var{rop} and set its value from the string in @var{str}. See @code{mpf_set_str} above for details on the assignment operation. @@ -4817,8 +4704,8 @@ set by @code{mpf_set_default_prec}. @cindex Float conversion functions @cindex Conversion functions -@deftypefun double mpf_get_d (const mpf_t @var{op}) -Convert @var{op} to a @code{double}, truncating if necessary (i.e.@: rounding +@deftypefun double mpf_get_d (mpf_t @var{op}) +Convert @var{op} to a @code{double}, truncating if necessary (ie.@: rounding towards zero). If the exponent in @var{op} is too big or too small to fit a @code{double} @@ -4827,22 +4714,22 @@ available. For too small @math{0.0} is normally returned. Hardware overflow, underflow and denorm traps may or may not occur. @end deftypefun -@deftypefun double mpf_get_d_2exp (signed long int *@var{exp}, const mpf_t @var{op}) -Convert @var{op} to a @code{double}, truncating if necessary (i.e.@: rounding +@deftypefun double mpf_get_d_2exp (signed long int *@var{exp}, mpf_t @var{op}) +Convert @var{op} to a @code{double}, truncating if necessary (ie.@: rounding towards zero), and with an exponent returned separately. The return value is in the range @math{0.5@le{}@GMPabs{@var{d}}<1} and the -exponent is stored to @code{*@var{exp}}. @m{@var{d} \times 2^{exp}, -@var{d} * 2^@var{exp}} is the (truncated) @var{op} value. If @var{op} is zero, -the return is @math{0.0} and 0 is stored to @code{*@var{exp}}. +exponent is stored to @code{*@var{exp}}. @m{@var{d} * 2^{exp}, @var{d} * +2^@var{exp}} is the (truncated) @var{op} value. If @var{op} is zero, the +return is @math{0.0} and 0 is stored to @code{*@var{exp}}. @cindex @code{frexp} This is similar to the standard C @code{frexp} function (@pxref{Normalization Functions,,, libc, The GNU C Library Reference Manual}). @end deftypefun -@deftypefun long mpf_get_si (const mpf_t @var{op}) -@deftypefunx {unsigned long} mpf_get_ui (const mpf_t @var{op}) +@deftypefun long mpf_get_si (mpf_t @var{op}) +@deftypefunx {unsigned long} mpf_get_ui (mpf_t @var{op}) Convert @var{op} to a @code{long} or @code{unsigned long}, truncating any fraction part. If @var{op} is too big for the return type, the result is undefined. @@ -4851,7 +4738,7 @@ See also @code{mpf_fits_slong_p} and @code{mpf_fits_ulong_p} (@pxref{Miscellaneous Float Functions}). @end deftypefun -@deftypefun {char *} mpf_get_str (char *@var{str}, mp_exp_t *@var{expptr}, int @var{base}, size_t @var{n_digits}, const mpf_t @var{op}) +@deftypefun {char *} mpf_get_str (char *@var{str}, mp_exp_t *@var{expptr}, int @var{base}, size_t @var{n_digits}, mpf_t @var{op}) Convert @var{op} to a string of digits in base @var{base}. The base argument may vary from 2 to 62 or from @minus{}2 to @minus{}36. Up to @var{n_digits} digits will be generated. Trailing zeros are not returned. No more digits @@ -4893,19 +4780,19 @@ or the given @var{str}. @cindex Float arithmetic functions @cindex Arithmetic functions -@deftypefun void mpf_add (mpf_t @var{rop}, const mpf_t @var{op1}, const mpf_t @var{op2}) -@deftypefunx void mpf_add_ui (mpf_t @var{rop}, const mpf_t @var{op1}, unsigned long int @var{op2}) +@deftypefun void mpf_add (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2}) +@deftypefunx void mpf_add_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2}) Set @var{rop} to @math{@var{op1} + @var{op2}}. @end deftypefun -@deftypefun void mpf_sub (mpf_t @var{rop}, const mpf_t @var{op1}, const mpf_t @var{op2}) -@deftypefunx void mpf_ui_sub (mpf_t @var{rop}, unsigned long int @var{op1}, const mpf_t @var{op2}) -@deftypefunx void mpf_sub_ui (mpf_t @var{rop}, const mpf_t @var{op1}, unsigned long int @var{op2}) +@deftypefun void mpf_sub (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2}) +@deftypefunx void mpf_ui_sub (mpf_t @var{rop}, unsigned long int @var{op1}, mpf_t @var{op2}) +@deftypefunx void mpf_sub_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2}) Set @var{rop} to @var{op1} @minus{} @var{op2}. @end deftypefun -@deftypefun void mpf_mul (mpf_t @var{rop}, const mpf_t @var{op1}, const mpf_t @var{op2}) -@deftypefunx void mpf_mul_ui (mpf_t @var{rop}, const mpf_t @var{op1}, unsigned long int @var{op2}) +@deftypefun void mpf_mul (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2}) +@deftypefunx void mpf_mul_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2}) Set @var{rop} to @math{@var{op1} @GMPtimes{} @var{op2}}. @end deftypefun @@ -4914,39 +4801,39 @@ 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. -@deftypefun void mpf_div (mpf_t @var{rop}, const mpf_t @var{op1}, const mpf_t @var{op2}) -@deftypefunx void mpf_ui_div (mpf_t @var{rop}, unsigned long int @var{op1}, const mpf_t @var{op2}) -@deftypefunx void mpf_div_ui (mpf_t @var{rop}, const mpf_t @var{op1}, unsigned long int @var{op2}) +@deftypefun void mpf_div (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2}) +@deftypefunx void mpf_ui_div (mpf_t @var{rop}, unsigned long int @var{op1}, mpf_t @var{op2}) +@deftypefunx void mpf_div_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2}) @cindex Division functions Set @var{rop} to @var{op1}/@var{op2}. @end deftypefun -@deftypefun void mpf_sqrt (mpf_t @var{rop}, const mpf_t @var{op}) +@deftypefun void mpf_sqrt (mpf_t @var{rop}, mpf_t @var{op}) @deftypefunx void mpf_sqrt_ui (mpf_t @var{rop}, unsigned long int @var{op}) @cindex Root extraction functions Set @var{rop} to @m{\sqrt{@var{op}}, the square root of @var{op}}. @end deftypefun -@deftypefun void mpf_pow_ui (mpf_t @var{rop}, const mpf_t @var{op1}, unsigned long int @var{op2}) +@deftypefun void mpf_pow_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2}) @cindex Exponentiation functions @cindex Powering functions Set @var{rop} to @m{@var{op1}^{op2}, @var{op1} raised to the power @var{op2}}. @end deftypefun -@deftypefun void mpf_neg (mpf_t @var{rop}, const mpf_t @var{op}) +@deftypefun void mpf_neg (mpf_t @var{rop}, mpf_t @var{op}) Set @var{rop} to @minus{}@var{op}. @end deftypefun -@deftypefun void mpf_abs (mpf_t @var{rop}, const mpf_t @var{op}) +@deftypefun void mpf_abs (mpf_t @var{rop}, mpf_t @var{op}) Set @var{rop} to the absolute value of @var{op}. @end deftypefun -@deftypefun void mpf_mul_2exp (mpf_t @var{rop}, const mpf_t @var{op1}, mp_bitcnt_t @var{op2}) +@deftypefun void mpf_mul_2exp (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2}) Set @var{rop} to @m{@var{op1} \times 2^{op2}, @var{op1} times 2 raised to @var{op2}}. @end deftypefun -@deftypefun void mpf_div_2exp (mpf_t @var{rop}, const mpf_t @var{op1}, mp_bitcnt_t @var{op2}) +@deftypefun void mpf_div_2exp (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2}) Set @var{rop} to @m{@var{op1}/2^{op2}, @var{op1} divided by 2 raised to @var{op2}}. @end deftypefun @@ -4957,10 +4844,10 @@ Set @var{rop} to @m{@var{op1}/2^{op2}, @var{op1} divided by 2 raised to @cindex Float comparison functions @cindex Comparison functions -@deftypefun int mpf_cmp (const mpf_t @var{op1}, const mpf_t @var{op2}) -@deftypefunx int mpf_cmp_d (const mpf_t @var{op1}, double @var{op2}) -@deftypefunx int mpf_cmp_ui (const mpf_t @var{op1}, unsigned long int @var{op2}) -@deftypefunx int mpf_cmp_si (const mpf_t @var{op1}, signed long int @var{op2}) +@deftypefun int mpf_cmp (mpf_t @var{op1}, mpf_t @var{op2}) +@deftypefunx int mpf_cmp_d (mpf_t @var{op1}, double @var{op2}) +@deftypefunx int mpf_cmp_ui (mpf_t @var{op1}, unsigned long int @var{op2}) +@deftypefunx int mpf_cmp_si (mpf_t @var{op1}, signed long int @var{op2}) Compare @var{op1} and @var{op2}. Return a positive value if @math{@var{op1} > @var{op2}}, zero if @math{@var{op1} = @var{op2}}, and a negative value if @math{@var{op1} < @var{op2}}. @@ -4969,7 +4856,7 @@ Compare @var{op1} and @var{op2}. Return a positive value if @math{@var{op1} > a NaN. @end deftypefun -@deftypefun int mpf_eq (const mpf_t @var{op1}, const mpf_t @var{op2}, mp_bitcnt_t op3) +@deftypefun int mpf_eq (mpf_t @var{op1}, mpf_t @var{op2}, unsigned long int op3) Return non-zero if the first @var{op3} bits of @var{op1} and @var{op2} are equal, zero otherwise. I.e., test if @var{op1} and @var{op2} are approximately equal. @@ -4982,18 +4869,18 @@ even if ... is replaced by a semi-infinite number of bits. Such numbers are really just one ulp off, and should be considered equal. @end deftypefun -@deftypefun void mpf_reldiff (mpf_t @var{rop}, const mpf_t @var{op1}, const mpf_t @var{op2}) +@deftypefun void mpf_reldiff (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2}) Compute the relative difference between @var{op1} and @var{op2} and store the result in @var{rop}. This is @math{@GMPabs{@var{op1}-@var{op2}}/@var{op1}}. @end deftypefun -@deftypefn Macro int mpf_sgn (const mpf_t @var{op}) +@deftypefn Macro int mpf_sgn (mpf_t @var{op}) @cindex Sign tests @cindex Float sign tests Return @math{+1} if @math{@var{op} > 0}, 0 if @math{@var{op} = 0}, and @math{-1} if @math{@var{op} < 0}. -This function is actually implemented as a macro. It evaluates its argument +This function is actually implemented as a macro. It evaluates its arguments multiple times. @end deftypefn @@ -5006,17 +4893,15 @@ multiple times. @cindex I/O functions Functions that perform input from a stdio stream, and functions that output to -a stdio stream, of @code{mpf} numbers. Passing a @code{NULL} pointer for a -@var{stream} argument to any of these functions will make them read from -@code{stdin} and write to @code{stdout}, respectively. +a stdio stream. Passing a @code{NULL} pointer for a @var{stream} argument to +any of these functions will make them read from @code{stdin} and write to +@code{stdout}, respectively. When using any of these functions, it is a good idea to include @file{stdio.h} before @file{gmp.h}, since that will allow @file{gmp.h} to define prototypes for these functions. -See also @ref{Formatted Output} and @ref{Formatted Input}. - -@deftypefun size_t mpf_out_str (FILE *@var{stream}, int @var{base}, size_t @var{n_digits}, const mpf_t @var{op}) +@deftypefun size_t mpf_out_str (FILE *@var{stream}, int @var{base}, size_t @var{n_digits}, mpf_t @var{op}) Print @var{op} to @var{stream}, as a string of digits. Return the number of bytes written, or if an error occurred, return 0. @@ -5056,7 +4941,7 @@ numbers like @samp{0.23} are not interpreted as octal. Return the number of bytes read, or if an error occurred, return 0. @end deftypefun -@c @deftypefun void mpf_out_raw (FILE *@var{stream}, const mpf_t @var{float}) +@c @deftypefun void mpf_out_raw (FILE *@var{stream}, mpf_t @var{float}) @c Output @var{float} on stdio stream @var{stream}, in raw binary @c format. The float is written in a portable format, with 4 bytes of @c size information, and that many bytes of limbs. Both the size and the @@ -5075,9 +4960,9 @@ Return the number of bytes read, or if an error occurred, return 0. @cindex Miscellaneous float functions @cindex Float miscellaneous functions -@deftypefun void mpf_ceil (mpf_t @var{rop}, const mpf_t @var{op}) -@deftypefunx void mpf_floor (mpf_t @var{rop}, const mpf_t @var{op}) -@deftypefunx void mpf_trunc (mpf_t @var{rop}, const mpf_t @var{op}) +@deftypefun void mpf_ceil (mpf_t @var{rop}, mpf_t @var{op}) +@deftypefunx void mpf_floor (mpf_t @var{rop}, mpf_t @var{op}) +@deftypefunx void mpf_trunc (mpf_t @var{rop}, mpf_t @var{op}) @cindex Rounding functions @cindex Float rounding functions Set @var{rop} to @var{op} rounded to an integer. @code{mpf_ceil} rounds to the @@ -5085,26 +4970,25 @@ next higher integer, @code{mpf_floor} to the next lower, and @code{mpf_trunc} to the integer towards zero. @end deftypefun -@deftypefun int mpf_integer_p (const mpf_t @var{op}) +@deftypefun int mpf_integer_p (mpf_t @var{op}) Return non-zero if @var{op} is an integer. @end deftypefun -@deftypefun int mpf_fits_ulong_p (const mpf_t @var{op}) -@deftypefunx int mpf_fits_slong_p (const mpf_t @var{op}) -@deftypefunx int mpf_fits_uint_p (const mpf_t @var{op}) -@deftypefunx int mpf_fits_sint_p (const mpf_t @var{op}) -@deftypefunx int mpf_fits_ushort_p (const mpf_t @var{op}) -@deftypefunx int mpf_fits_sshort_p (const mpf_t @var{op}) +@deftypefun int mpf_fits_ulong_p (mpf_t @var{op}) +@deftypefunx int mpf_fits_slong_p (mpf_t @var{op}) +@deftypefunx int mpf_fits_uint_p (mpf_t @var{op}) +@deftypefunx int mpf_fits_sint_p (mpf_t @var{op}) +@deftypefunx int mpf_fits_ushort_p (mpf_t @var{op}) +@deftypefunx int mpf_fits_sshort_p (mpf_t @var{op}) Return non-zero if @var{op} would fit in the respective C data type, when truncated to an integer. @end deftypefun -@deftypefun void mpf_urandomb (mpf_t @var{rop}, gmp_randstate_t @var{state}, mp_bitcnt_t @var{nbits}) +@deftypefun void mpf_urandomb (mpf_t @var{rop}, gmp_randstate_t @var{state}, unsigned long int @var{nbits}) @cindex Random number functions @cindex Float random number functions Generate a uniformly distributed random float in @var{rop}, such that @math{0 -@le{} @var{rop} < 1}, with @var{nbits} significant bits in the mantissa or -less if the precision of @var{rop} is smaller. +@le{} @var{rop} < 1}, with @var{nbits} significant bits in the mantissa. The variable @var{state} must be initialized by calling one of the @code{gmp_randinit} functions (@ref{Random State Initialization}) before @@ -5120,7 +5004,7 @@ numbers have proven to be more likely to trigger corner-case bugs. Negative random numbers are generated when @var{max_size} is negative. @end deftypefun -@c @deftypefun size_t mpf_size (const mpf_t @var{op}) +@c @deftypefun size_t mpf_size (mpf_t @var{op}) @c Return the size of @var{op} measured in number of limbs. If @var{op} is @c zero, the returned value will be zero. (@xref{Nomenclature}, for an @c explanation of the concept @dfn{limb}.) @@ -5242,13 +5126,6 @@ This function requires that @var{s1n} is greater than or equal to @var{s2n}. @end deftypefun -@deftypefun mp_limb_t mpn_neg (mp_limb_t *@var{rp}, const mp_limb_t *@var{sp}, mp_size_t @var{n}) -Perform the negation of @{@var{sp}, @var{n}@}, and write the result to -@{@var{rp}, @var{n}@}. This is equivalent to calling @code{mpn_sub_n} with a -@var{n}-limb zero minuend and passing @{@var{sp}, @var{n}@} as subtrahend. -Return borrow, either 0 or 1. -@end deftypefun - @deftypefun void mpn_mul_n (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n}) Multiply @{@var{s1p}, @var{n}@} and @{@var{s2p}, @var{n}@}, and write the 2*@var{n}-limb result to @var{rp}. @@ -5257,7 +5134,7 @@ The destination has to have space for 2*@var{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 @code{mpn_sqr}. +If the two input operands are the same, use @code{mpn_sqr_n}. @end deftypefun @deftypefun mp_limb_t mpn_mul (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, mp_size_t @var{s1n}, const mp_limb_t *@var{s2p}, mp_size_t @var{s2n}) @@ -5272,11 +5149,11 @@ destination and either source. This function requires that @var{s1n} is greater than or equal to @var{s2n}. @end deftypefun -@deftypefun void mpn_sqr (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, mp_size_t @var{n}) +@deftypefun void mpn_sqr_n (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, mp_size_t @var{n}) Compute the square of @{@var{s1p}, @var{n}@} and write the 2*@var{n}-limb result to @var{rp}. -The destination has to have space for 2@var{n} limbs, even if the result's +The destination has to have space for 2*@var{n} limbs, even if the result's most significant limb is zero. No overlap is permitted between the destination and the source. @end deftypefun @@ -5322,10 +5199,10 @@ Divide @{@var{np}, @var{nn}@} by @{@var{dp}, @var{dn}@} and put the quotient at @{@var{qp}, @var{nn}@minus{}@var{dn}+1@} and the remainder at @{@var{rp}, @var{dn}@}. The quotient is rounded towards 0. -No overlap is permitted between arguments, except that @var{np} might equal -@var{rp}. The dividend size @var{nn} must be greater than or equal to divisor -size @var{dn}. The most significant limb of the divisor must be non-zero. The -@var{qxn} operand must be zero. +No overlap is permitted between arguments. @var{nn} must be greater than or +equal to @var{dn}. The most significant limb of @var{dp} must be non-zero. +The @var{qxn} operand must be zero. +@comment FIXME: Relax overlap requirements! @end deftypefun @deftypefun mp_limb_t mpn_divrem (mp_limb_t *@var{r1p}, mp_size_t @var{qxn}, mp_limb_t *@var{rs2p}, mp_size_t @var{rs2n}, const mp_limb_t *@var{s3p}, mp_size_t @var{s3n}) @@ -5399,11 +5276,32 @@ be 0, 1 or 2 (these are both borrows really). When @math{c=0} clearly @code{mp_bits_per_limb} is even, which is always so currently). @end deftypefn -@deftypefun mp_limb_t mpn_mod_1 (const mp_limb_t *@var{s1p}, mp_size_t @var{s1n}, mp_limb_t @var{s2limb}) +@deftypefun mp_limb_t mpn_mod_1 (mp_limb_t *@var{s1p}, mp_size_t @var{s1n}, mp_limb_t @var{s2limb}) Divide @{@var{s1p}, @var{s1n}@} by @var{s2limb}, and return the remainder. @var{s1n} can be zero. @end deftypefun +@deftypefun mp_limb_t mpn_bdivmod (mp_limb_t *@var{rp}, mp_limb_t *@var{s1p}, mp_size_t @var{s1n}, const mp_limb_t *@var{s2p}, mp_size_t @var{s2n}, unsigned long int @var{d}) +This function puts the low +@math{@GMPfloor{@var{d}/@nicode{mp\_bits\_per\_limb}}} limbs of @var{q} = +@{@var{s1p}, @var{s1n}@}/@{@var{s2p}, @var{s2n}@} mod @m{2^d,2^@var{d}} at +@var{rp}, and returns the high @var{d} mod @code{mp_bits_per_limb} bits of +@var{q}. + +@{@var{s1p}, @var{s1n}@} - @var{q} * @{@var{s2p}, @var{s2n}@} mod @m{2 +\GMPraise{@var{s1n}*@code{mp\_bits\_per\_limb}}, +2^(@var{s1n}*@nicode{mp\_bits\_per\_limb})} is placed at @var{s1p}. Since the +low @math{@GMPfloor{@var{d}/@nicode{mp\_bits\_per\_limb}}} limbs of this +difference are zero, it is possible to overwrite the low limbs at @var{s1p} +with this difference, provided @math{@var{rp} @le{} @var{s1p}}. + +This function requires that @math{@var{s1n} * @nicode{mp\_bits\_per\_limb} +@ge{} @var{D}}, and that @{@var{s2p}, @var{s2n}@} is odd. + +@strong{This interface is preliminary. It might change incompatibly in future +revisions.} +@end deftypefun + @deftypefun mp_limb_t mpn_lshift (mp_limb_t *@var{rp}, const mp_limb_t *@var{sp}, mp_size_t @var{n}, unsigned int @var{count}) Shift @{@var{sp}, @var{n}@} left by @var{count} bits, and write the result to @{@var{rp}, @var{n}@}. The bits shifted out at the left are returned in the @@ -5442,9 +5340,10 @@ Set @{@var{rp}, @var{retval}@} to the greatest common divisor of @{@var{xp}, the return value is the actual number produced. Both source operands are destroyed. -It is required that @math{@var{xn} @ge @var{yn} > 0}, and the most significant -limb of @{@var{yp}, @var{yn}@} must be non-zero. No overlap is permitted -between @{@var{xp}, @var{xn}@} and @{@var{yp}, @var{yn}@}. +@{@var{xp}, @var{xn}@} must have at least as many bits as @{@var{yp}, +@var{yn}@}. @{@var{yp}, @var{yn}@} must be odd. Both operands must have +non-zero most significant limbs. No overlap is permitted between @{@var{xp}, +@var{xn}@} and @{@var{yp}, @var{yn}@}. @end deftypefun @deftypefun mp_limb_t mpn_gcd_1 (const mp_limb_t *@var{xp}, mp_size_t @var{xn}, mp_limb_t @var{ylimb}) @@ -5452,35 +5351,30 @@ Return the greatest common divisor of @{@var{xp}, @var{xn}@} and @var{ylimb}. Both operands must be non-zero. @end deftypefun -@deftypefun mp_size_t mpn_gcdext (mp_limb_t *@var{gp}, mp_limb_t *@var{sp}, mp_size_t *@var{sn}, mp_limb_t *@var{up}, mp_size_t @var{un}, mp_limb_t *@var{vp}, mp_size_t @var{vn}) -Let @m{U,@var{U}} be defined by @{@var{up}, @var{un}@} and let @m{V,@var{V}} be -defined by @{@var{vp}, @var{vn}@}. +@deftypefun mp_size_t mpn_gcdext (mp_limb_t *@var{gp}, mp_limb_t *@var{sp}, mp_size_t *@var{sn}, mp_limb_t *@var{xp}, mp_size_t @var{xn}, mp_limb_t *@var{yp}, mp_size_t @var{yn}) +Let @m{U,@var{U}} be defined by @{@var{xp}, @var{xn}@} and let @m{V,@var{V}} be +defined by @{@var{yp}, @var{yn}@}. Compute the greatest common divisor @math{G} of @math{U} and @math{V}. Compute a cofactor @math{S} such that @math{G = US + VT}. The second cofactor @var{T} is not computed but can easily be obtained from @m{(G - US) / V, (@var{G} - @var{U}*@var{S}) / @var{V}} (the division will be exact). It is required that -@math{@var{un} @ge @var{vn} > 0}, and the most significant -limb of @{@var{vp}, @var{vn}@} must be non-zero. +@math{U @ge V > 0}. @math{S} satisfies @math{S = 1} or @math{@GMPabs{S} < V / (2 G)}. @math{S = 0} if and only if @math{V} divides @math{U} (i.e., @math{G = V}). Store @math{G} at @var{gp} and let the return value define its limb count. Store @math{S} at @var{sp} and let |*@var{sn}| define its limb count. @math{S} -can be negative; when this happens *@var{sn} will be negative. The area at -@var{gp} should have room for @var{vn} limbs and the area at @var{sp} should -have room for @math{@var{vn}+1} limbs. +can be negative; when this happens *@var{sn} will be negative. The areas at +@var{gp} and @var{sp} should each have room for @math{@var{xn}+1} limbs. -Both source operands are destroyed. +The areas @{@var{xp}, @math{@var{xn}+1}@} and @{@var{yp}, @math{@var{yn}+1}@} +are destroyed (i.e.@: the input operands plus an extra limb past the end of +each). -Compatibility notes: GMP 4.3.0 and 4.3.1 defined @math{S} less strictly. +Compatibility note: GMP 4.3.0 and 4.3.1 defined @math{S} less strictly. Earlier as well as later GMP releases define @math{S} as described here. -GMP releases before GMP 4.3.0 required additional space for both input and output -areas. More precisely, the areas @{@var{up}, @math{@var{un}+1}@} and -@{@var{vp}, @math{@var{vn}+1}@} were destroyed (i.e.@: the operands plus an -extra limb past the end of each), and the areas pointed to by @var{gp} and -@var{sp} should each have room for @math{@var{un}+1} limbs. @end deftypefun @deftypefun mp_size_t mpn_sqrtrem (mp_limb_t *@var{r1p}, mp_limb_t *@var{r2p}, const mp_limb_t *@var{sp}, mp_size_t @var{n}) @@ -5499,14 +5393,7 @@ 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 -@code{mpn_perfect_square_p}. -@end deftypefun - -@deftypefun size_t mpn_sizeinbase (const mp_limb_t *@var{xp}, mp_size_t @var{n}, int @var{base}) -Return the size of @{@var{xp},@var{n}@} measured in number of digits in the -given @var{base}. @var{base} can vary from 2 to 62. Requires @math{@var{n} > 0} -and @math{@var{xp}[@var{n}-1] > 0}. The result will be either exact or -1 too big. If @var{base} is a power of 2, the result is always exact. +@code{mpz_perfect_square_p}. @end deftypefun @deftypefun mp_size_t mpn_get_str (unsigned char *@var{str}, int @var{base}, mp_limb_t *@var{s1p}, mp_size_t @var{s1n}) @@ -5528,31 +5415,30 @@ represented by a @var{s1n} long limb array, plus one extra character. Convert bytes @{@var{str},@var{strsize}@} in the given @var{base} to limbs at @var{rp}. -@math{@var{str}[0]} is the most significant input byte and -@math{@var{str}[@var{strsize}-1]} is the least significant input byte. Each -byte should be a value in the range 0 to @math{@var{base}-1}, not an ASCII -character. @var{base} can vary from 2 to 256. +@math{@var{str}[0]} is the most significant byte and +@math{@var{str}[@var{strsize}-1]} is the least significant. Each byte should +be a value in the range 0 to @math{@var{base}-1}, not an ASCII character. +@var{base} can vary from 2 to 256. -The converted value is @{@var{rp},@var{rn}@} where @var{rn} is the return -value. If the most significant input byte @math{@var{str}[0]} is non-zero, -then @math{@var{rp}[@var{rn}-1]} will be non-zero, else -@math{@var{rp}[@var{rn}-1]} and some number of subsequent limbs may be zero. +The return value is the number of limbs written to @var{rp}. If the most +significant input byte is non-zero then the high limb at @var{rp} will be +non-zero, and only that exact number of limbs will be required there. -The area at @var{rp} has to have space for the largest possible number with -@var{strsize} digits in the chosen base, plus one extra limb. +If the most significant input byte is zero then there may be high zero limbs +written to @var{rp} and included in the return value. -The input must have at least one byte, and no overlap is permitted between +@var{strsize} must be at least 1, and no overlap is permitted between @{@var{str},@var{strsize}@} and the result at @var{rp}. @end deftypefun -@deftypefun {mp_bitcnt_t} mpn_scan0 (const mp_limb_t *@var{s1p}, mp_bitcnt_t @var{bit}) +@deftypefun {unsigned long int} mpn_scan0 (const mp_limb_t *@var{s1p}, unsigned long int @var{bit}) Scan @var{s1p} from bit position @var{bit} for the next clear bit. It is required that there be a clear bit within the area at @var{s1p} at or beyond bit position @var{bit}, so that the function has something to return. @end deftypefun -@deftypefun {mp_bitcnt_t} mpn_scan1 (const mp_limb_t *@var{s1p}, mp_bitcnt_t @var{bit}) +@deftypefun {unsigned long int} mpn_scan1 (const mp_limb_t *@var{s1p}, unsigned long int @var{bit}) Scan @var{s1p} from bit position @var{bit} for the next set bit. It is required that there be a set bit within the area at @var{s1p} at or @@ -5570,11 +5456,11 @@ zeros and ones in the binary representation. routines. @end deftypefun -@deftypefun {mp_bitcnt_t} mpn_popcount (const mp_limb_t *@var{s1p}, mp_size_t @var{n}) +@deftypefun {unsigned long int} mpn_popcount (const mp_limb_t *@var{s1p}, mp_size_t @var{n}) Count the number of set bits in @{@var{s1p}, @var{n}@}. @end deftypefun -@deftypefun {mp_bitcnt_t} mpn_hamdist (const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n}) +@deftypefun {unsigned long int} mpn_hamdist (const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n}) Compute the hamming distance between @{@var{s1p}, @var{n}@} and @{@var{s2p}, @var{n}@}, which is the number of bit positions where the two operands have different bit values. @@ -5582,245 +5468,6 @@ different bit values. @deftypefun int mpn_perfect_square_p (const mp_limb_t *@var{s1p}, mp_size_t @var{n}) Return non-zero iff @{@var{s1p}, @var{n}@} is a perfect square. -The most significant limb of the input @{@var{s1p}, @var{n}@} must be -non-zero. -@end deftypefun - -@deftypefun void mpn_and_n (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n}) -Perform the bitwise logical and of @{@var{s1p}, @var{n}@} and @{@var{s2p}, -@var{n}@}, and write the result to @{@var{rp}, @var{n}@}. -@end deftypefun - -@deftypefun void mpn_ior_n (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n}) -Perform the bitwise logical inclusive or of @{@var{s1p}, @var{n}@} and -@{@var{s2p}, @var{n}@}, and write the result to @{@var{rp}, @var{n}@}. -@end deftypefun - -@deftypefun void mpn_xor_n (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n}) -Perform the bitwise logical exclusive or of @{@var{s1p}, @var{n}@} and -@{@var{s2p}, @var{n}@}, and write the result to @{@var{rp}, @var{n}@}. -@end deftypefun - -@deftypefun void mpn_andn_n (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n}) -Perform the bitwise logical and of @{@var{s1p}, @var{n}@} and the bitwise -complement of @{@var{s2p}, @var{n}@}, and write the result to @{@var{rp}, @var{n}@}. -@end deftypefun - -@deftypefun void mpn_iorn_n (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n}) -Perform the bitwise logical inclusive or of @{@var{s1p}, @var{n}@} and the bitwise -complement of @{@var{s2p}, @var{n}@}, and write the result to @{@var{rp}, @var{n}@}. -@end deftypefun - -@deftypefun void mpn_nand_n (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n}) -Perform the bitwise logical and of @{@var{s1p}, @var{n}@} and @{@var{s2p}, -@var{n}@}, and write the bitwise complement of the result to @{@var{rp}, @var{n}@}. -@end deftypefun - -@deftypefun void mpn_nior_n (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n}) -Perform the bitwise logical inclusive or of @{@var{s1p}, @var{n}@} and -@{@var{s2p}, @var{n}@}, and write the bitwise complement of the result to -@{@var{rp}, @var{n}@}. -@end deftypefun - -@deftypefun void mpn_xnor_n (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n}) -Perform the bitwise logical exclusive or of @{@var{s1p}, @var{n}@} and -@{@var{s2p}, @var{n}@}, and write the bitwise complement of the result to -@{@var{rp}, @var{n}@}. -@end deftypefun - -@deftypefun void mpn_com (mp_limb_t *@var{rp}, const mp_limb_t *@var{sp}, mp_size_t @var{n}) -Perform the bitwise complement of @{@var{sp}, @var{n}@}, and write the result -to @{@var{rp}, @var{n}@}. -@end deftypefun - -@deftypefun void mpn_copyi (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, mp_size_t @var{n}) -Copy from @{@var{s1p}, @var{n}@} to @{@var{rp}, @var{n}@}, increasingly. -@end deftypefun - -@deftypefun void mpn_copyd (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, mp_size_t @var{n}) -Copy from @{@var{s1p}, @var{n}@} to @{@var{rp}, @var{n}@}, decreasingly. -@end deftypefun - -@deftypefun void mpn_zero (mp_limb_t *@var{rp}, mp_size_t @var{n}) -Zero @{@var{rp}, @var{n}@}. -@end deftypefun - -@sp 1 -@section Low-level functions for cryptography -@cindex Low-level functions for cryptography -@cindex Cryptography functions, low-level - -The functions prefixed with @code{mpn_sec_} and @code{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 @code{mpn} -functions are naturally side-channel resistant: @code{mpn_add_n}, -@code{mpn_sub_n}, @code{mpn_lshift}, @code{mpn_rshift}, @code{mpn_zero}, -@code{mpn_copyi}, @code{mpn_copyd}, @code{mpn_com}, and the logical function -(@code{mpn_and_n}, etc). - -There are some exceptions from the side-channel resilience: (1) Some assembly -implementations of @code{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 @code{mpn_add_n} and -@code{mpn_sub_n}. (3) Alpha ev6 has a leaky @code{mpn_mul_1} which also makes -@code{mpn_sec_mul} on those systems unsafe. - -@deftypefun mp_limb_t mpn_cnd_add_n (mp_limb_t @var{cnd}, mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n}) -@deftypefunx mp_limb_t mpn_cnd_sub_n (mp_limb_t @var{cnd}, mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n}) -These functions do conditional addition and subtraction. If @var{cnd} is -non-zero, they produce the same result as a regular @code{mpn_add_n} or -@code{mpn_sub_n}, and if @var{cnd} is zero, they copy @{@var{s1p},@var{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 @var{cnd}. Like for @code{mpn_add_n} and -@code{mpn_sub_n}, on most machines, the timing will also be independent of the -actual limb values. -@end deftypefun - -@deftypefun mp_limb_t mpn_sec_add_1 (mp_limb_t *@var{rp}, const mp_limb_t *@var{ap}, mp_size_t @var{n}, mp_limb_t @var{b}, mp_limb_t *@var{tp}) -@deftypefunx mp_limb_t mpn_sec_sub_1 (mp_limb_t *@var{rp}, const mp_limb_t *@var{ap}, mp_size_t @var{n}, mp_limb_t @var{b}, mp_limb_t *@var{tp}) -Set @var{R} to @var{A} + @var{b} or @var{A} - @var{b}, respectively, where -@var{R} = @{@var{rp},@var{n}@}, @var{A} = @{@var{ap},@var{n}@}, and @var{b} is -a single limb. Returns carry. - -These functions take @math{O(N)} time, unlike the leaky functions -@code{mpn_add_1} which are @math{O(1)} on average. They require scratch space -of @code{mpn_sec_add_1_itch(@var{n})} and @code{mpn_sec_sub_1_itch(@var{n})} -limbs, respectively, to be passed in the @var{tp} parameter. The scratch space -requirements are guaranteed to increase monotonously in the operand size. -@end deftypefun - -@deftypefun void mpn_sec_mul (mp_limb_t *@var{rp}, const mp_limb_t *@var{ap}, mp_size_t @var{an}, const mp_limb_t *@var{bp}, mp_size_t @var{bn}, mp_limb_t *@var{tp}) -@deftypefunx mp_size_t mpn_sec_mul_itch (mp_size_t @var{an}, mp_size_t @var{bn}) -Set @var{R} to @math{A @times{} B}, where @var{A} = @{@var{ap},@var{an}@}, -@var{B} = @{@var{bp},@var{bn}@}, and @var{R} = -@{@var{rp},@math{@var{an}+@var{bn}}@}. - -It is required that @math{@var{an} @ge @var{bn} > 0}. - -No overlapping between @var{R} and the input operands is allowed. For -@math{@var{A} = @var{B}}, use @code{mpn_sec_sqr} for optimal performance. - -This function requires scratch space of @code{mpn_sec_mul_itch(@var{an}, -@var{bn})} limbs to be passed in the @var{tp} parameter. The scratch space -requirements are guaranteed to increase monotonously in the operand sizes. -@end deftypefun - - -@deftypefun void mpn_sec_sqr (mp_limb_t *@var{rp}, const mp_limb_t *@var{ap}, mp_size_t @var{an}, mp_limb_t *@var{tp}) -@deftypefunx mp_size_t mpn_sec_sqr_itch (mp_size_t @var{an}) -Set @var{R} to @math{A^2}, where @var{A} = @{@var{ap},@var{an}@}, and @var{R} = -@{@var{rp},@math{2@var{an}}@}. - -It is required that @math{@var{an} > 0}. - -No overlapping between @var{R} and the input operands is allowed. - -This function requires scratch space of @code{mpn_sec_sqr_itch(@var{an})} limbs -to be passed in the @var{tp} parameter. The scratch space requirements are -guaranteed to increase monotonously in the operand size. -@end deftypefun - - -@deftypefun void mpn_sec_powm (mp_limb_t *@var{rp}, const mp_limb_t *@var{bp}, mp_size_t @var{bn}, const mp_limb_t *@var{ep}, mp_bitcnt_t @var{enb}, const mp_limb_t *@var{mp}, mp_size_t @var{n}, mp_limb_t *@var{tp}) -@deftypefunx mp_size_t mpn_sec_powm_itch (mp_size_t @var{bn}, mp_bitcnt_t @var{enb}, size_t @var{n}) -Set @var{R} to @m{B^E \bmod @var{M}, (@var{B} raised to @var{E}) modulo -@var{M}}, where @var{R} = @{@var{rp},@var{n}@}, @var{M} = @{@var{mp},@var{n}@}, -and @var{E} = @{@var{ep},@math{@GMPceil{@var{enb} / -@code{GMP\_NUMB\_BITS}}}@}. - -It is required that @math{@var{B} > 0}, that @math{@var{M} > 0} is odd, and -that @m{@var{E} < 2@GMPraise{@var{enb}}, @var{E} < 2^@var{enb}}. - -No overlapping between @var{R} and the input operands is allowed. - -This function requires scratch space of @code{mpn_sec_powm_itch(@var{bn}, -@var{enb}, @var{n})} limbs to be passed in the @var{tp} parameter. The scratch -space requirements are guaranteed to increase monotonously in the operand -sizes. -@end deftypefun - -@deftypefun void mpn_sec_tabselect (mp_limb_t *@var{rp}, const mp_limb_t *@var{tab}, mp_size_t @var{n}, mp_size_t @var{nents}, mp_size_t @var{which}) -Select entry @var{which} from table @var{tab}, which has @var{nents} entries, each @var{n} -limbs. Store the selected entry at @var{rp}. - -This function reads the entire table to avoid side-channel information leaks. -@end deftypefun - -@deftypefun mp_limb_t mpn_sec_div_qr (mp_limb_t *@var{qp}, mp_limb_t *@var{np}, mp_size_t @var{nn}, const mp_limb_t *@var{dp}, mp_size_t @var{dn}, mp_limb_t *@var{tp}) -@deftypefunx mp_size_t mpn_sec_div_qr_itch (mp_size_t @var{nn}, mp_size_t @var{dn}) - -Set @var{Q} to @m{\lfloor @var{N} / @var{D}\rfloor, the truncated quotient -@var{N} / @var{D}} and @var{R} to @m{@var{N} \bmod @var{D}, @var{N} modulo -@var{D}}, where @var{N} = @{@var{np},@var{nn}@}, @var{D} = -@{@var{dp},@var{dn}@}, @var{Q}'s most significant limb is the function return -value and the remaining limbs are @{@var{qp},@var{nn-dn}@}, and @var{R} = -@{@var{np},@var{dn}@}. - -It is required that @math{@var{nn} @ge @var{dn} @ge 1}, and that -@m{@var{dp}[@var{dn}-1] @neq 0, @var{dp}[@var{dn}-1] != 0}. This does not -imply that @math{@var{N} @ge @var{D}} since @var{N} might be zero-padded. - -Note the overlapping between @var{N} and @var{R}. No other operand overlapping -is allowed. The entire space occupied by @var{N} is overwritten. - -This function requires scratch space of @code{mpn_sec_div_qr_itch(@var{nn}, -@var{dn})} limbs to be passed in the @var{tp} parameter. -@end deftypefun - -@deftypefun void mpn_sec_div_r (mp_limb_t *@var{np}, mp_size_t @var{nn}, const mp_limb_t *@var{dp}, mp_size_t @var{dn}, mp_limb_t *@var{tp}) -@deftypefunx mp_size_t mpn_sec_div_r_itch (mp_size_t @var{nn}, mp_size_t @var{dn}) - -Set @var{R} to @m{@var{N} \bmod @var{D}, @var{N} modulo @var{D}}, where @var{N} -= @{@var{np},@var{nn}@}, @var{D} = @{@var{dp},@var{dn}@}, and @var{R} = -@{@var{np},@var{dn}@}. - -It is required that @math{@var{nn} @ge @var{dn} @ge 1}, and that -@m{@var{dp}[@var{dn}-1] @neq 0, @var{dp}[@var{dn}-1] != 0}. This does not -imply that @math{@var{N} @ge @var{D}} since @var{N} might be zero-padded. - -Note the overlapping between @var{N} and @var{R}. No other operand overlapping -is allowed. The entire space occupied by @var{N} is overwritten. - -This function requires scratch space of @code{mpn_sec_div_r_itch(@var{nn}, -@var{dn})} limbs to be passed in the @var{tp} parameter. -@end deftypefun - -@deftypefun int mpn_sec_invert (mp_limb_t *@var{rp}, mp_limb_t *@var{ap}, const mp_limb_t *@var{mp}, mp_size_t @var{n}, mp_bitcnt_t @var{nbcnt}, mp_limb_t *@var{tp}) -@deftypefunx mp_size_t mpn_sec_invert_itch (mp_size_t @var{n}) -Set @var{R} to @m{@var{A}^{-1} \bmod @var{M}, the inverse of @var{A} modulo -@var{M}}, where @var{R} = @{@var{rp},@var{n}@}, @var{A} = @{@var{ap},@var{n}@}, -and @var{M} = @{@var{mp},@var{n}@}. @strong{This function's interface is -preliminary.} - -If an inverse exists, return 1, otherwise return 0 and leave @var{R} -undefined. In either case, the input @var{A} is destroyed. - -It is required that @var{M} is odd, and that @math{@var{nbcnt} @ge -@GMPceil{\log(@var{A}+1)} + @GMPceil{\log(@var{M}+1)}}. A safe choice is -@m{@var{nbcnt} = 2@var{n} @times{} @code{GMP\_NUMB\_BITS}, @var{nbcnt} = 2 -@times{} @var{n} @times{} GMP_NUMB_BITS}, but a smaller value might improve -performance if @var{M} or @var{A} are known to have leading zero bits. - -This function requires scratch space of @code{mpn_sec_invert_itch(@var{n})} -limbs to be passed in the @var{tp} parameter. @end deftypefun @@ -5934,7 +5581,7 @@ Initialize @var{state} for a Mersenne Twister algorithm. This algorithm is fast and has good randomness properties. @end deftypefun -@deftypefun void gmp_randinit_lc_2exp (gmp_randstate_t @var{state}, const mpz_t @var{a}, @w{unsigned long @var{c}}, @w{mp_bitcnt_t @var{m2exp}}) +@deftypefun void gmp_randinit_lc_2exp (gmp_randstate_t @var{state}, mpz_t @var{a}, @w{unsigned long @var{c}}, @w{unsigned long @var{m2exp}}) @cindex Linear congruential random numbers Initialize @var{state} with a linear congruential algorithm @m{X = (@var{a}X + @var{c}) @bmod 2^{m2exp}, X = (@var{a}*X + @var{c}) mod 2^@var{m2exp}}. @@ -5949,12 +5596,12 @@ generated, multiple iterations of the recurrence are used and the results concatenated. @end deftypefun -@deftypefun int gmp_randinit_lc_2exp_size (gmp_randstate_t @var{state}, mp_bitcnt_t @var{size}) +@deftypefun int gmp_randinit_lc_2exp_size (gmp_randstate_t @var{state}, unsigned long @var{size}) @cindex Linear congruential random numbers Initialize @var{state} for a linear congruential algorithm as per @code{gmp_randinit_lc_2exp}. @var{a}, @var{c} and @var{m2exp} are selected from a table, chosen so that @var{size} bits (or more) of each @math{X} will -be used, i.e.@: @math{@var{m2exp}/2 @ge{} @var{size}}. +be used, ie.@: @math{@var{m2exp}/2 @ge{} @var{size}}. If successful the return value is non-zero. If @var{size} is bigger than the table data provides then the return value is zero. The maximum @var{size} @@ -6002,7 +5649,7 @@ Free all memory occupied by @var{state}. @cindex Random number seeding @cindex Seeding random numbers -@deftypefun void gmp_randseed (gmp_randstate_t @var{state}, const mpz_t @var{seed}) +@deftypefun void gmp_randseed (gmp_randstate_t @var{state}, mpz_t @var{seed}) @deftypefunx void gmp_randseed_ui (gmp_randstate_t @var{state}, @w{unsigned long int @var{seed}}) Set an initial seed value into @var{state}. @@ -6027,7 +5674,7 @@ random data better suited for use as a seed. @section Random State Miscellaneous @deftypefun {unsigned long} gmp_urandomb_ui (gmp_randstate_t @var{state}, unsigned long @var{n}) -Return a uniformly distributed random number of @var{n} bits, i.e.@: in the +Return a uniformly distributed random number of @var{n} bits, ie.@: in the range 0 to @m{2^n-1,2^@var{n}-1} inclusive. @var{n} must be less than or equal to the number of bits in an @code{unsigned long}. @end deftypefun @@ -6182,7 +5829,7 @@ instance extensions registered with GLIBC @code{register_printf_function}. Also currently there's no support for POSIX @samp{$} style numbered arguments (perhaps this will be added in the future). -The precision field has its usual meaning for integer @samp{Z} and float +The precision field has it's usual meaning for integer @samp{Z} and float @samp{F} types, but is currently undefined for @samp{Q} and should not be used with that. @@ -6193,10 +5840,7 @@ happens even for an @samp{f} conversion of an @code{mpf_t} which is an integer, for instance @math{2^@W{1024}} in an @code{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 @samp{%.Fe} or @samp{%.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 @samp{%Ff}, @samp{%.Ff}, and @samp{%.0Ff} will all be -different. +be used to specifically request just the significant digits. The decimal point character (or string) is taken from the current locale settings on systems which provide @code{localeconv} (@pxref{Locales,, Locales @@ -6307,7 +5951,7 @@ The following functions are provided in @file{libgmpxx} (@pxref{Headers and Libraries}), which is built if C++ support is enabled (@pxref{Build Options}). Prototypes are available from @code{<gmp.h>}. -@deftypefun ostream& operator<< (ostream& @var{stream}, const mpz_t @var{op}) +@deftypefun ostream& operator<< (ostream& @var{stream}, mpz_t @var{op}) Print @var{op} to @var{stream}, using its @code{ios} formatting settings. @code{ios::width} is reset to 0 after output, the same as the standard @code{ostream operator<<} routines do. @@ -6317,7 +5961,7 @@ decimal. This is unlike the standard @code{operator<<} routines on @code{int} etc, which instead give twos complement. @end deftypefun -@deftypefun ostream& operator<< (ostream& @var{stream}, const mpq_t @var{op}) +@deftypefun ostream& operator<< (ostream& @var{stream}, mpq_t @var{op}) Print @var{op} to @var{stream}, using its @code{ios} formatting settings. @code{ios::width} is reset to 0 after output, the same as the standard @code{ostream operator<<} routines do. @@ -6330,7 +5974,7 @@ decimal. If @code{ios::showbase} is set then a base indicator is shown on both the numerator and denominator (if the denominator is required). @end deftypefun -@deftypefun ostream& operator<< (ostream& @var{stream}, const mpf_t @var{op}) +@deftypefun ostream& operator<< (ostream& @var{stream}, mpf_t @var{op}) Print @var{op} to @var{stream}, using its @code{ios} formatting settings. @code{ios::width} is reset to 0 after output, the same as the standard @code{ostream operator<<} routines do. @@ -6639,7 +6283,7 @@ results. For classes with overloading, see @ref{C++ Class Interface}. -@node C++ Class Interface, Custom Allocation, Formatted Input, Top +@node C++ Class Interface, BSD Compatible Functions, Formatted Input, Top @chapter C++ Class Interface @cindex C++ interface @@ -6651,7 +6295,7 @@ 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. +and member templates. For GCC this means version 2.91 or later. @strong{Everything described in this chapter is to be considered preliminary and might be subject to incompatible changes if some unforeseen difficulty @@ -6774,23 +6418,23 @@ anything. @node C++ Interface Integers, C++ Interface Rationals, C++ Interface General, C++ Class Interface @section C++ Interface Integers -@deftypefun {} mpz_class::mpz_class (type @var{n}) +@deftypefun void mpz_class::mpz_class (type @var{n}) Construct an @code{mpz_class}. All the standard C++ types may be used, except @code{long long} and @code{long double}, and all the GMP C++ classes can be -used, although conversions from @code{mpq_class} and @code{mpf_class} are -@code{explicit}. Any necessary conversion follows the corresponding C -function, for example @code{double} follows @code{mpz_set_d} -(@pxref{Assigning Integers}). +used. Any necessary conversion follows the corresponding C function, for +example @code{double} follows @code{mpz_set_d} (@pxref{Assigning Integers}). @end deftypefun -@deftypefun explicit mpz_class::mpz_class (const mpz_t @var{z}) +@deftypefun void mpz_class::mpz_class (mpz_t @var{z}) Construct an @code{mpz_class} from an @code{mpz_t}. The value in @var{z} is copied into the new @code{mpz_class}, there won't be any permanent association between it and @var{z}. @end deftypefun -@deftypefun explicit mpz_class::mpz_class (const char *@var{s}, int @var{base} = 0) -@deftypefunx explicit mpz_class::mpz_class (const string& @var{s}, int @var{base} = 0) +@deftypefun void mpz_class::mpz_class (const char *@var{s}) +@deftypefunx void mpz_class::mpz_class (const char *@var{s}, int @var{base} = 0) +@deftypefunx void mpz_class::mpz_class (const string& @var{s}) +@deftypefunx void mpz_class::mpz_class (const string& @var{s}, int @var{base} = 0) Construct an @code{mpz_class} converted from a string using @code{mpz_set_str} (@pxref{Assigning Integers}). @@ -6798,11 +6442,6 @@ If the string is not a valid integer, an @code{std::invalid_argument} exception is thrown. The same applies to @code{operator=}. @end deftypefun -@deftypefun mpz_class operator"" _mpz (const char *@var{str}) -With C++11 compilers, integers can be constructed with the syntax -@code{123_mpz} which is equivalent to @code{mpz_class("123")}. -@end deftypefun - @deftypefun mpz_class operator/ (mpz_class @var{a}, mpz_class @var{d}) @deftypefunx mpz_class operator% (mpz_class @var{a}, mpz_class @var{d}) Divisions involving @code{mpz_class} round towards zero, as per the @@ -6819,7 +6458,7 @@ mpz_fdiv_q (q.get_mpz_t(), a.get_mpz_t(), d.get_mpz_t()); @end example @end deftypefun -@deftypefun mpz_class abs (mpz_class @var{op}) +@deftypefun mpz_class abs (mpz_class @var{op1}) @deftypefunx int cmp (mpz_class @var{op1}, type @var{op2}) @deftypefunx int cmp (type @var{op1}, mpz_class @var{op2}) @maybepagebreak @@ -6840,9 +6479,6 @@ mpz_fdiv_q (q.get_mpz_t(), a.get_mpz_t(), d.get_mpz_t()); @deftypefunx int mpz_class::set_str (const string& @var{str}, int @var{base}) @deftypefunx int sgn (mpz_class @var{op}) @deftypefunx mpz_class sqrt (mpz_class @var{op}) -@maybepagebreak -@deftypefunx void mpz_class::swap (mpz_class& @var{op}) -@deftypefunx void swap (mpz_class& @var{op1}, mpz_class& @var{op2}) These functions provide a C++ class interface to the corresponding GMP C routines. @@ -6868,13 +6504,12 @@ And comparisons are always made exactly, as per @code{mpz_cmp_d}. In all the following constructors, if a fraction is given then it should be in canonical form, or if not then @code{mpq_class::canonicalize} called. -@deftypefun {} mpq_class::mpq_class (type @var{op}) -@deftypefunx {} mpq_class::mpq_class (integer @var{num}, integer @var{den}) +@deftypefun void mpq_class::mpq_class (type @var{op}) +@deftypefunx void mpq_class::mpq_class (integer @var{num}, integer @var{den}) Construct an @code{mpq_class}. The initial value can be a single value of any -type (conversion from @code{mpf_class} is @code{explicit}), or a pair of -integers (@code{mpz_class} or standard C++ integer types) representing a -fraction, except that @code{long long} and @code{long double} are not -supported. For example, +type, or a pair of integers (@code{mpz_class} or standard C++ integer types) +representing a fraction, except that @code{long long} and @code{long double} +are not supported. For example, @example mpq_class q (99); @@ -6883,14 +6518,16 @@ mpq_class q (1, 3); @end example @end deftypefun -@deftypefun explicit mpq_class::mpq_class (const mpq_t @var{q}) +@deftypefun void mpq_class::mpq_class (mpq_t @var{q}) Construct an @code{mpq_class} from an @code{mpq_t}. The value in @var{q} is copied into the new @code{mpq_class}, there won't be any permanent association between it and @var{q}. @end deftypefun -@deftypefun explicit mpq_class::mpq_class (const char *@var{s}, int @var{base} = 0) -@deftypefunx explicit mpq_class::mpq_class (const string& @var{s}, int @var{base} = 0) +@deftypefun void mpq_class::mpq_class (const char *@var{s}) +@deftypefunx void mpq_class::mpq_class (const char *@var{s}, int @var{base} = 0) +@deftypefunx void mpq_class::mpq_class (const string& @var{s}) +@deftypefunx void mpq_class::mpq_class (const string& @var{s}, int @var{base} = 0) Construct an @code{mpq_class} converted from a string using @code{mpq_set_str} (@pxref{Initializing Rationals}). @@ -6898,12 +6535,6 @@ If the string is not a valid rational, an @code{std::invalid_argument} exception is thrown. The same applies to @code{operator=}. @end deftypefun -@deftypefun mpq_class operator"" _mpq (const char *@var{str}) -With C++11 compilers, integral rationals can be constructed with the syntax -@code{123_mpq} which is equivalent to @code{mpq_class(123_mpz)}. Other -rationals can be built as @code{-1_mpq/2} or @code{0xb_mpq/123456_mpz}. -@end deftypefun - @deftypefun void mpq_class::canonicalize () Put an @code{mpq_class} into canonical form, as per @ref{Rational Number Functions}. All arithmetic operators require their operands in canonical @@ -6920,9 +6551,6 @@ form, and will return results in canonical form. @deftypefunx int mpq_class::set_str (const char *@var{str}, int @var{base}) @deftypefunx int mpq_class::set_str (const string& @var{str}, int @var{base}) @deftypefunx int sgn (mpq_class @var{op}) -@maybepagebreak -@deftypefunx void mpq_class::swap (mpq_class& @var{op}) -@deftypefunx void swap (mpq_class& @var{op1}, mpq_class& @var{op2}) These functions provide a C++ class interface to the corresponding GMP C routines. @@ -6969,7 +6597,7 @@ as the destination @code{f}. Explicit constructors can be used if this doesn't suit. @deftypefun {} mpf_class::mpf_class (type @var{op}) -@deftypefunx {} mpf_class::mpf_class (type @var{op}, mp_bitcnt_t @var{prec}) +@deftypefunx {} mpf_class::mpf_class (type @var{op}, unsigned long @var{prec}) Construct an @code{mpf_class}. Any standard C++ type can be used, except @code{long long} and @code{long double}, and any of the GMP C++ classes can be used. @@ -6992,20 +6620,10 @@ mpf_class f(x+y); // greater of precisions of x and y @end example @end deftypefun -@deftypefun explicit mpf_class::mpf_class (const mpf_t @var{f}) -@deftypefunx {} mpf_class::mpf_class (const mpf_t @var{f}, mp_bitcnt_t @var{prec}) -Construct an @code{mpf_class} from an @code{mpf_t}. The value in @var{f} is -copied into the new @code{mpf_class}, there won't be any permanent association -between it and @var{f}. - -If @var{prec} is given, the initial precision is that value, in bits. If -@var{prec} is not given, then the initial precision is that of @var{f}. -@end deftypefun - -@deftypefun explicit mpf_class::mpf_class (const char *@var{s}) -@deftypefunx {} mpf_class::mpf_class (const char *@var{s}, mp_bitcnt_t @var{prec}, int @var{base} = 0) -@deftypefunx explicit mpf_class::mpf_class (const string& @var{s}) -@deftypefunx {} mpf_class::mpf_class (const string& @var{s}, mp_bitcnt_t @var{prec}, int @var{base} = 0) +@deftypefun void mpf_class::mpf_class (const char *@var{s}) +@deftypefunx void mpf_class::mpf_class (const char *@var{s}, unsigned long @var{prec}, int @var{base} = 0) +@deftypefunx void mpf_class::mpf_class (const string& @var{s}) +@deftypefunx void mpf_class::mpf_class (const string& @var{s}, unsigned long @var{prec}, int @var{base} = 0) Construct an @code{mpf_class} converted from a string using @code{mpf_set_str} (@pxref{Assigning Floats}). If @var{prec} is given, the initial precision is that value, in bits. If not, the default @code{mpf} precision @@ -7015,11 +6633,6 @@ If the string is not a valid float, an @code{std::invalid_argument} exception is thrown. The same applies to @code{operator=}. @end deftypefun -@deftypefun mpf_class operator"" _mpf (const char *@var{str}) -With C++11 compilers, floats can be constructed with the syntax -@code{1.23e-1_mpf} which is equivalent to @code{mpf_class("1.23e-1")}. -@end deftypefun - @deftypefun {mpf_class&} mpf_class::operator= (type @var{op}) Convert and store the given @var{op} value to an @code{mpf_class} object. The same types are accepted as for the constructors above. @@ -7070,9 +6683,6 @@ with the builtin float types. @deftypefunx int mpf_class::set_str (const string& @var{str}, int @var{base}) @deftypefunx int sgn (mpf_class @var{op}) @deftypefunx mpf_class sqrt (mpf_class @var{op}) -@maybepagebreak -@deftypefunx void mpf_class::swap (mpf_class& @var{op}) -@deftypefunx void swap (mpf_class& @var{op1}, mpf_class& @var{op2}) @deftypefunx mpf_class trunc (mpf_class @var{op}) These functions provide a C++ class interface to the corresponding GMP C routines. @@ -7083,9 +6693,9 @@ except @code{long long} and @code{long double}. The accuracy provided by @code{hypot} is not currently guaranteed. @end deftypefun -@deftypefun {mp_bitcnt_t} mpf_class::get_prec () -@deftypefunx void mpf_class::set_prec (mp_bitcnt_t @var{prec}) -@deftypefunx void mpf_class::set_prec_raw (mp_bitcnt_t @var{prec}) +@deftypefun {unsigned long int} mpf_class::get_prec () +@deftypefunx void mpf_class::set_prec (unsigned long @var{prec}) +@deftypefunx void mpf_class::set_prec_raw (unsigned long @var{prec}) Get or set the current precision of an @code{mpf_class}. The restrictions described for @code{mpf_set_prec_raw} (@pxref{Initializing @@ -7134,7 +6744,7 @@ Seed a random number generator. See @pxref{Random Number Functions}, for how to choose a good seed. @end deftypefun -@deftypefun mpz_class gmp_randclass::get_z_bits (mp_bitcnt_t @var{bits}) +@deftypefun mpz_class gmp_randclass::get_z_bits (unsigned long @var{bits}) @deftypefunx mpz_class gmp_randclass::get_z_bits (mpz_class @var{bits}) Generate a random integer with a specified number of bits. @end deftypefun @@ -7144,7 +6754,7 @@ Generate a random integer in the range 0 to @math{@var{n}-1} inclusive. @end deftypefun @deftypefun mpf_class gmp_randclass::get_f () -@deftypefunx mpf_class gmp_randclass::get_f (mp_bitcnt_t @var{prec}) +@deftypefunx mpf_class gmp_randclass::get_f (unsigned long @var{prec}) Generate a random float @var{f} in the range @math{0 <= @var{f} < 1}. @var{f} will be to @var{prec} bits precision, or if @var{prec} is not given then to the precision of the destination. For example, @@ -7241,35 +6851,134 @@ void fun (T f, T g) fun2 (f, T(f+g)); // Good @} @end example +@end table -@item C++11 -C++11 provides several new ways in which types can be inferred: @code{auto}, -@code{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 @code{sum} as a macro. -@example -mpz_class z = 33; -auto sum = z + z; -mpz_class prod = sum * sum; -@end example +@node BSD Compatible Functions, Custom Allocation, C++ Class Interface, Top +@comment node-name, next, previous, up +@chapter Berkeley MP Compatible Functions +@cindex Berkeley MP compatible functions +@cindex BSD MP compatible functions -This other example may crash, though some compilers might make it look like -it is working, because the expression @code{z+z} goes out of scope before it -is evaluated. +These functions are intended to be fully compatible with the Berkeley MP +library which is available on many BSD derived U*ix systems. The +@samp{--enable-mpbsd} option must be used when building GNU MP to make these +available (@pxref{Installing GMP}). -@example -mpz_class z = 33; -auto sum = z + z + z; -mpz_class prod = sum * 2; -@end example +The original Berkeley MP library has a usage restriction: you cannot use the +same variable as both source and destination in a single function call. The +compatible functions in GNU MP do not share this restriction---inputs and +outputs may overlap. -It is thus strongly recommended to avoid @code{auto} anywhere a GMP C++ -expression may appear. -@end table +It is not recommended that new programs are written using these functions. +Apart from the incomplete set of functions, the interface for initializing +@code{MINT} objects is more error prone, and the @code{pow} function collides +with @code{pow} in @file{libm.a}. + +@cindex @code{mp.h} +@tindex MINT +Include the header @file{mp.h} to get the definition of the necessary types and +functions. If you are on a BSD derived system, make sure to include GNU +@file{mp.h} if you are going to link the GNU @file{libmp.a} to your program. +This means that you probably need to give the @samp{-I<dir>} option to the +compiler, where @samp{<dir>} is the directory where you have GNU @file{mp.h}. + +@deftypefun {MINT *} itom (signed short int @var{initial_value}) +Allocate an integer consisting of a @code{MINT} object and dynamic limb space. +Initialize the integer to @var{initial_value}. Return a pointer to the +@code{MINT} object. +@end deftypefun + +@deftypefun {MINT *} xtom (char *@var{initial_value}) +Allocate an integer consisting of a @code{MINT} object and dynamic limb space. +Initialize the integer from @var{initial_value}, a hexadecimal, +null-terminated C string. Return a pointer to the @code{MINT} object. +@end deftypefun + +@deftypefun void move (MINT *@var{src}, MINT *@var{dest}) +Set @var{dest} to @var{src} by copying. Both variables must be previously +initialized. +@end deftypefun + +@deftypefun void madd (MINT *@var{src_1}, MINT *@var{src_2}, MINT *@var{destination}) +Add @var{src_1} and @var{src_2} and put the sum in @var{destination}. +@end deftypefun + +@deftypefun void msub (MINT *@var{src_1}, MINT *@var{src_2}, MINT *@var{destination}) +Subtract @var{src_2} from @var{src_1} and put the difference in +@var{destination}. +@end deftypefun + +@deftypefun void mult (MINT *@var{src_1}, MINT *@var{src_2}, MINT *@var{destination}) +Multiply @var{src_1} and @var{src_2} and put the product in @var{destination}. +@end deftypefun + +@deftypefun void mdiv (MINT *@var{dividend}, MINT *@var{divisor}, MINT *@var{quotient}, MINT *@var{remainder}) +@deftypefunx void sdiv (MINT *@var{dividend}, signed short int @var{divisor}, MINT *@var{quotient}, signed short int *@var{remainder}) +Set @var{quotient} to @var{dividend}/@var{divisor}, and @var{remainder} to +@var{dividend} mod @var{divisor}. The quotient is rounded towards zero; the +remainder has the same sign as the dividend unless it is zero. + +Some implementations of these functions work differently---or not at all---for +negative arguments. +@end deftypefun + +@deftypefun void msqrt (MINT *@var{op}, MINT *@var{root}, MINT *@var{remainder}) +Set @var{root} to @m{\lfloor\sqrt{@var{op}}\rfloor, the truncated integer part +of the square root of @var{op}}, like @code{mpz_sqrt}. Set @var{remainder} to +@m{(@var{op} - @var{root}^2), @var{op}@minus{}@var{root}*@var{root}}, i.e. +zero if @var{op} is a perfect square. + +If @var{root} and @var{remainder} are the same variable, the results are +undefined. +@end deftypefun + +@deftypefun void pow (MINT *@var{base}, MINT *@var{exp}, MINT *@var{mod}, MINT *@var{dest}) +Set @var{dest} to (@var{base} raised to @var{exp}) modulo @var{mod}. + +Note that the name @code{pow} clashes with @code{pow} from the standard C math +library (@pxref{Exponents and Logarithms,, Exponentiation and Logarithms, +libc, The GNU C Library Reference Manual}). An application will only be able +to use one or the other. +@end deftypefun + +@deftypefun void rpow (MINT *@var{base}, signed short int @var{exp}, MINT *@var{dest}) +Set @var{dest} to @var{base} raised to @var{exp}. +@end deftypefun +@deftypefun void gcd (MINT *@var{op1}, MINT *@var{op2}, MINT *@var{res}) +Set @var{res} to the greatest common divisor of @var{op1} and @var{op2}. +@end deftypefun -@node Custom Allocation, Language Bindings, C++ Class Interface, Top +@deftypefun int mcmp (MINT *@var{op1}, MINT *@var{op2}) +Compare @var{op1} and @var{op2}. Return a positive value if @var{op1} > +@var{op2}, zero if @var{op1} = @var{op2}, and a negative value if @var{op1} < +@var{op2}. +@end deftypefun + +@deftypefun void min (MINT *@var{dest}) +Input a decimal string from @code{stdin}, and put the read integer in +@var{dest}. SPC and TAB are allowed in the number string, and are ignored. +@end deftypefun + +@deftypefun void mout (MINT *@var{src}) +Output @var{src} to @code{stdout}, as a decimal string. Also output a newline. +@end deftypefun + +@deftypefun {char *} mtox (MINT *@var{op}) +Convert @var{op} to a hexadecimal string, and return a pointer to the string. +The returned string is allocated using the default memory allocation function, +@code{malloc} by default. It will be @code{strlen(str)+1} bytes, that being +exactly enough for the string and null-terminator. +@end deftypefun + +@deftypefun void mfree (MINT *@var{op}) +De-allocate, the space used by @var{op}. @strong{This function should only be +passed a value returned by @code{itom} or @code{xtom}.} +@end deftypefun + + +@node Custom Allocation, Language Bindings, BSD Compatible Functions, Top @comment node-name, next, previous, up @chapter Custom Allocation @cindex Custom allocation @@ -7283,6 +6992,9 @@ and terminates the program. Alternate functions can be specified, to allocate memory in a different way or to have a different error action on running out of memory. +This feature is available in the Berkeley compatibility library (@pxref{BSD +Compatible Functions}) as well as the main GMP library. + @deftypefun void mp_set_memory_functions (@* void *(*@var{alloc_func_ptr}) (size_t), @* void *(*@var{realloc_func_ptr}) (void *, size_t, size_t), @* void (*@var{free_func_ptr}) (void *, size_t)) Replace the current allocation functions from the arguments. If an argument is @code{NULL}, the corresponding default function is used. @@ -7325,10 +7037,10 @@ De-allocate the space pointed to by @var{ptr}. A @dfn{byte} here means the unit used by the @code{sizeof} operator. -The @var{reallocate_function} parameter @var{old_size} and the -@var{free_function} parameter @var{size} are passed for convenience, but of -course they can be ignored if not needed by an implementation. The default -functions using @code{malloc} and friends for instance don't use them. +The @var{old_size} parameters to @var{reallocate_function} and +@var{free_function} are passed for convenience, but of course can be ignored +if not needed. The default functions using @code{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 @@ -7398,14 +7110,17 @@ than C, though perhaps with varying levels of functionality and efficiency. GMP C++ class interface, @pxref{C++ Class Interface} @* Straightforward interface, expression templates to eliminate temporaries. @item -ALP @spaceuref{https://www-sop.inria.fr/saga/logiciels/ALP/} @* Linear algebra and +ALP @spaceuref{http://www-sop.inria.fr/saga/logiciels/ALP/} @* Linear algebra and polynomials using templates. @item -Arithmos @spaceuref{http://cant.ua.ac.be/old/arithmos/} @* Rationals +Arithmos @spaceuref{http://www.win.ua.ac.be/~cant/arithmos/} @* Rationals with infinities and square roots. @item CLN @spaceuref{http://www.ginac.de/CLN/} @* High level classes for arithmetic. @item +LiDIA @spaceuref{http://www.cdc.informatik.tu-darmstadt.de/TI/LiDIA/} @* A C++ +library for computational number theory. +@item Linbox @spaceuref{http://www.linalg.org/} @* Sparse vectors and matrices. @item NTL @spaceuref{http://www.shoup.net/ntl/} @* A C++ number theory library. @@ -7417,35 +7132,31 @@ NTL @spaceuref{http://www.shoup.net/ntl/} @* A C++ number theory library. @c gmp-d @spaceuref{http://home.comcast.net/~benhinkle/gmp-d/} @c @end itemize -@item Eiffel +@item Fortran @itemize @bullet @item -Eiffelroom @spaceuref{http://www.eiffelroom.org/node/442} +Omni F77 @spaceuref{http://phase.hpcc.jp/Omni/home.html} @* Arbitrary +precision floats. @end itemize -@c @item Fortran -@c @itemize @bullet -@c @item -@c Omni F77 @spaceuref{http://phase.hpcc.jp/Omni/home.html} @* Arbitrary -@c precision floats. -@c @end itemize - @item Haskell @itemize @bullet @item -Glasgow Haskell Compiler @spaceuref{https://www.haskell.org/ghc/} +Glasgow Haskell Compiler @spaceuref{http://www.haskell.org/ghc/} @end itemize @item Java @itemize @bullet @item -Kaffe @spaceuref{https://github.com/kaffe/kaffe} +Kaffe @spaceuref{http://www.kaffe.org/} +@item +Kissme @spaceuref{http://kissme.sourceforge.net/} @end itemize @item Lisp @itemize @bullet @item -GNU Common Lisp @spaceuref{https://www.gnu.org/software/gcl/gcl.html} +GNU Common Lisp @spaceuref{http://www.gnu.org/software/gcl/gcl.html} @item Librep @spaceuref{http://librep.sourceforge.net/} @item @@ -7473,7 +7184,7 @@ MLton compiler @spaceuref{http://mlton.org/} @item Objective Caml @itemize @bullet @item -MLGMP @spaceuref{http://opam.ocamlpro.com/pkg/mlgmp.20120224.html} +MLGMP @spaceuref{http://www.di.ens.fr/~monniaux/programmes.html.en} @item Numerix @spaceuref{http://pauillac.inria.fr/~quercia/} @* Optionally using GMP. @@ -7482,7 +7193,7 @@ GMP. @item Oz @itemize @bullet @item -Mozart @spaceuref{http://mozart.github.io/} +Mozart @spaceuref{http://www.mozart-oz.org/} @end itemize @item Pascal @@ -7525,23 +7236,19 @@ Arbitrary precision floats. @item Python @itemize @bullet @item -GMPY @uref{https://code.google.com/p/gmpy/} -@end itemize - -@item Ruby -@itemize @bullet +mpz module in the standard distribution, @uref{http://www.python.org/} @item -http://rubygems.org/gems/gmp +GMPY @uref{http://gmpy.sourceforge.net/} @end itemize @item Scheme @itemize @bullet @item -GNU Guile @spaceuref{https://www.gnu.org/software/guile/guile.html} +GNU Guile (upcoming 1.8) @spaceuref{http://www.gnu.org/software/guile/guile.html} @item RScheme @spaceuref{http://www.rscheme.org/} @item -STklos @spaceuref{http://www.stklos.net/} +STklos @spaceuref{http://www.stklos.org/} @c @c For reference, MzScheme uses some of gmp, but (as of version 205) it only @c has copies of some of the generic C code, and we don't consider that a @@ -7558,7 +7265,7 @@ GNU Smalltalk @spaceuref{http://www.smalltalk.org/versions/GNUSmalltalk.html} @item Other @itemize @bullet @item -Axiom @uref{https://savannah.nongnu.org/projects/axiom} @* Computer algebra +Axiom @uref{http://savannah.nongnu.org/projects/axiom} @* Computer algebra using GCL. @item DrGenius @spaceuref{http://drgenius.seul.org/} @* Geometry system and @@ -7566,17 +7273,18 @@ mathematical programming language. @item GiNaC @spaceuref{http://www.ginac.de/} @* C++ computer algebra using CLN. @item -GOO @spaceuref{https://www.eecs.berkeley.edu/~jrb/goo/} @* Dynamic object oriented +GOO @spaceuref{http://www.googoogaga.org/} @* Dynamic object oriented language. @item -Maxima @uref{https://www.ma.utexas.edu/users/wfs/maxima.html} @* Macsyma +Maxima @uref{http://www.ma.utexas.edu/users/wfs/maxima.html} @* Macsyma computer algebra using GCL. -@c @item -@c Q @spaceuref{http://q-lang.sourceforge.net/} @* Equational programming system. +@item +Q @spaceuref{http://q-lang.sourceforge.net/} @* Equational programming system. @item Regina @spaceuref{http://regina.sourceforge.net/} @* Topological calculator. @item -Yacas @spaceuref{http://yacas.sourceforge.net} @* Yet another computer algebra system. +Yacas @spaceuref{http://www.xs4all.nl/~apinkus/yacas.html} @* Yet another +computer algebra system. @end itemize @end table @@ -7610,18 +7318,16 @@ documented functions. @section Multiplication @cindex Multiplication algorithms -N@cross{}N limb multiplications and squares are done using one of seven +N@cross{}N limb multiplications and squares are done using one of five algorithms, as the size N increases. @quotation @multitable {KaratsubaMMM} {MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM} @item Algorithm @tab Threshold @item Basecase @tab (none) -@item Karatsuba @tab @code{MUL_TOOM22_THRESHOLD} +@item Karatsuba @tab @code{MUL_KARATSUBA_THRESHOLD} @item Toom-3 @tab @code{MUL_TOOM33_THRESHOLD} @item Toom-4 @tab @code{MUL_TOOM44_THRESHOLD} -@item Toom-6.5 @tab @code{MUL_TOOM6H_THRESHOLD} -@item Toom-8.5 @tab @code{MUL_TOOM8H_THRESHOLD} @item FFT @tab @code{MUL_FFT_THRESHOLD} @end multitable @end quotation @@ -7629,7 +7335,7 @@ algorithms, as the size N increases. Similarly for squaring, with the @code{SQR} thresholds. N@cross{}M multiplications of operands with different sizes above -@code{MUL_TOOM22_THRESHOLD} are currently done by special Toom-inspired +@code{MUL_KARATSUBA_THRESHOLD} are currently done by special Toom-inspired algorithms or directly with FFT, depending on operand size (@pxref{Unbalanced Multiplication}). @@ -7638,7 +7344,6 @@ Multiplication}). * Karatsuba Multiplication:: * Toom 3-Way Multiplication:: * Toom 4-Way Multiplication:: -* Higher degree Toom'n'half:: * FFT Multiplication:: * Other Multiplication:: * Unbalanced Multiplication:: @@ -7781,7 +7486,7 @@ equal length (or the most significant part one limb shorter if N is odd). @end example @end ifnottex -Let @math{b} be the power of 2 where the split occurs, i.e.@: if @ms{x,0} is +Let @math{b} be the power of 2 where the split occurs, ie.@: if @ms{x,0} is @math{k} limbs (@ms{y,0} the same) then @m{b=2\GMPraise{$k*$@code{mp\_bits\_per\_limb}}, b=2^(k*mp_bits_per_limb)}. With that @m{x=x_1b+x_0,x=x1*b+x0} and @m{y=y_1b+y_0,y=y1*b+y0}, and the @@ -7879,7 +7584,7 @@ Karatsuba multiplication is asymptotically an @math{O(N^@W{1.585})} algorithm, the exponent being @m{\log3/\log2,log(3)/log(2)}, representing 3 multiplies each @math{1/2} the size of the inputs. This is a big improvement over the basecase multiply at @math{O(N^2)} and the advantage soon overcomes the extra -additions Karatsuba performs. @code{MUL_TOOM22_THRESHOLD} can be as little +additions Karatsuba performs. @code{MUL_KARATSUBA_THRESHOLD} can be as little as 10 limbs. The @code{SQR} threshold is usually about twice the @code{MUL}. The basecase algorithm will take a time of the form @m{M(N) = aN^2 + bN + c, @@ -7960,7 +7665,7 @@ These parts are treated as the coefficients of two polynomials @end display Let @math{b} equal the power of 2 which is the size of the @ms{x,0}, @ms{x,1}, -@ms{y,0} and @ms{y,1} pieces, i.e.@: if they're @math{k} limbs each then +@ms{y,0} and @ms{y,1} pieces, ie.@: if they're @math{k} limbs each then @m{b=2\GMPraise{$k*$@code{mp\_bits\_per\_limb}}, b=2^(k*mp_bits_per_limb)}. With this @math{x=X(b)} and @math{y=Y(b)}. @@ -8095,7 +7800,7 @@ the @m{w_i,w[i]}. Squaring follows the same procedure as multiplication, but there's only one @math{X(t)} and it's evaluated at the 5 points, and those values squared to give values of @math{W(t)}. The interpolation is then identical, and in fact -the same @code{toom_interpolate_5pts} subroutine is used for both squaring and +the same @code{toom3_interpolate} subroutine is used for both squaring and multiplying. Toom-3 is asymptotically @math{O(N^@W{1.465})}, the exponent being @@ -8133,7 +7838,7 @@ and for example with a bit of rearrangement just one division by 6 can be done. -@node Toom 4-Way Multiplication, Higher degree Toom'n'half, Toom 3-Way Multiplication, Multiplication Algorithms +@node Toom 4-Way Multiplication, FFT Multiplication, Toom 3-Way Multiplication, Multiplication Algorithms @subsection Toom 4-Way Multiplication @cindex Toom multiplication @@ -8176,32 +7881,7 @@ Toom-4 is asymptotically @math{O(N^@W{1.404})}, the exponent being original size each. -@node Higher degree Toom'n'half, FFT Multiplication, Toom 4-Way Multiplication, Multiplication Algorithms -@subsection Higher degree Toom'n'half -@cindex Toom multiplication - -The Toom algorithms described above (@pxref{Toom 3-Way Multiplication}, -@pxref{Toom 4-Way Multiplication}) generalizes to split into an arbitrary -number of pieces. In general a split of two equally long operands into -@math{r} pieces leads to evaluations and pointwise multiplications done at -@m{2r-1,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 @math{r}, -Toom-@m{r{1\over2},r+1/2} requires @math{2r} points, a multiple of four. - -The four-plets of points include 0, @m{\infty,inf}, +1, -1 and -@m{\pm2^i,+-2^i}, @m{\pm2^{-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 equanl in size to the result of the product. - -Current GMP uses both Toom-6'n'half and Toom-8'n'half. - - -@node FFT Multiplication, Other Multiplication, Higher degree Toom'n'half, Multiplication Algorithms +@node FFT Multiplication, Other Multiplication, Toom 4-Way Multiplication, Multiplication Algorithms @subsection FFT Multiplication @cindex FFT multiplication @cindex Fast Fourier Transform @@ -8250,13 +7930,13 @@ The points used for the evaluation are @math{g^i} for @math{i=0} to @math{2^k-1} where @m{g=2^{2N'/2^k}, g=2^(2N'/2^k)}. @math{g} is a @m{2^k,2^k'}th root of unity mod @m{2^{N'}+1,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 +fast fourier transforms used for the evaluation and interpolation do only shifts, adds and negations. The pointwise multiplications are done modulo @m{2^{N'}+1, 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 @math{N'}. The interpolation is -an inverse fast Fourier transform. The resulting set of sums of @m{x_iy_j, +an inverse fast fourier transform. The resulting set of sums of @m{x_iy_j, x[i]*y[j]} are added at appropriate offsets to give the final result. Squaring is the same, but @math{x} is the only input so it's one transform at @@ -8328,7 +8008,7 @@ currently used. The notes here are merely for interest. In general a split into @math{r+1} pieces is made, and evaluations and pointwise multiplications done at @m{2r+1,2*r+1} points. A 4-way split does 7 pointwise multiplies, 5-way does 9, etc. Asymptotically an @math{(r+1)}-way -algorithm is @m{O(N^{log(2r+1)/log(r+1)}), O(N^(log(2*r+1)/log(r+1)))}. Only +algorithm is @m{O(N^{log(2r+1)/log(r+1)}, O(N^(log(2*r+1)/log(r+1)))}. Only the pointwise multiplications count towards big-@math{O} complexity, but the time spent in the evaluate and interpolate stages grows with @math{r} and has a significant practical impact, with the asymptotic advantage of each @math{r} @@ -8348,10 +8028,10 @@ Splitting odd and even parts through positive and negative points can be thought of as using @math{-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 -@m{i=\sqrt{-1}, i=sqrt(-1)} doesn't help, essentially because in Cartesian +@m{i=\sqrt{-1}, i=sqrt(-1)} doesn't help, essentially because in cartesian form it takes three real multiplies to do a complex multiply. The existence of @m{2^k,2^k'}th roots of unity in a suitable ring or field lets the fast -Fourier transform keep splitting and get to @m{O(N \log r), O(N*log(r))}. +fourier transform keep splitting and get to @m{O(N \log r), 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 @@ -8366,7 +8046,7 @@ GMP. @cindex Unbalanced multiplication Multiplication of operands with different sizes, both below -@code{MUL_TOOM22_THRESHOLD} are done with plain schoolbook multiplication +@code{MUL_KARATSUBA_THRESHOLD} are done with plain schoolbook multiplication (@pxref{Basecase Multiplication}). For really large operands, we invoke FFT directly. @@ -8391,7 +8071,6 @@ can be split into 2, 3, or 4 coefficients, i.e., a polynomial of degree 1 to * Single Limb Division:: * Basecase Division:: * Divide and Conquer Division:: -* Block-Wise Barrett Division:: * Exact Division:: * Exact Remainder:: * Small Quotient Division:: @@ -8472,10 +8151,10 @@ Q@cross{}M multiplication, differing in fact only in the extra multiply and divide for each of the Q quotient limbs. -@node Divide and Conquer Division, Block-Wise Barrett Division, Basecase Division, Division Algorithms +@node Divide and Conquer Division, Exact Division, Basecase Division, Division Algorithms @subsection Divide and Conquer Division -For divisors larger than @code{DC_DIV_QR_THRESHOLD}, division is done by dividing. +For divisors larger than @code{DIV_DC_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 (@pxref{References}). @@ -8491,11 +8170,11 @@ If the (N/2)@cross{}(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 -@code{MUL_TOOM22_THRESHOLD} that divide and conquer is of use. +@code{MUL_KARATSUBA_THRESHOLD} that divide and conquer is of use. -@code{DC_DIV_QR_THRESHOLD} is based on the divisor size N, so it will be somewhere -above twice @code{MUL_TOOM22_THRESHOLD}, but how much above depends on the -CPU@. An optimized @code{mpn_mul_basecase} can lower @code{DC_DIV_QR_THRESHOLD} a +@code{DIV_DC_THRESHOLD} is based on the divisor size N, so it will be somewhere +above twice @code{MUL_KARATSUBA_THRESHOLD}, but how much above depends on the +CPU@. An optimized @code{mpn_mul_basecase} can lower @code{DIV_DC_THRESHOLD} a little by offering a ready-made advantage over repeated @code{mpn_submul_1} calls. @@ -8508,24 +8187,14 @@ algorithms the @math{M(N)} term improves and the multiplier tends to @m{\log N, log(N)}. In practice, at moderate to large sizes, a 2N@cross{}N division is about 2 to 4 times slower than an N@cross{}N multiplication. +Newton's method used for division is asymptotically @math{O(M(N))} and should +therefore be superior to divide and conquer, but it's believed this would only +be for large to very large N. -@node Block-Wise Barrett Division, Exact Division, Divide and Conquer Division, Division Algorithms -@subsection 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 @math{2n/n} division, the inverse will be just @m{\lceil n/2 -\rceil, ceil(n/2)} limbs. - -@node Exact Division, Exact Remainder, Block-Wise Barrett Division, Division Algorithms +@node Exact Division, Exact Remainder, Divide and Conquer Division, Division Algorithms @subsection 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 (@pxref{References}). @@ -8561,7 +8230,7 @@ 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 @code{binvert_limb} in +The modular inverse used is calculated efficiently by @code{modlimb_invert} in @file{gmp-impl.h}. This does four multiplies for a 32-bit limb, or six for a 64-bit limb. @file{tune/modlinv.c} has some alternate implementations that might suit processors better at bit twiddling than multiplying. @@ -8614,10 +8283,10 @@ products must be done as a normal division, but there's still some single limb divisions saved. When @math{d} is a single limb some simplifications arise, providing good speedups on a number of processors. -The functions @code{mpn_divexact_by3}, @code{mpn_modexact_1_odd} and the -internal @code{mpn_redc_X} functions differ subtly in how they return @math{r}, -leading to some negations in the above formula, but all are essentially the -same. +@code{mpn_bdivmod}, @code{mpn_divexact_by3}, @code{mpn_modexact_1_odd} and the +@code{redc} function in @code{mpz_powm} differ subtly in how they return +@math{r}, leading to some negations in the above formula, but all are +essentially the same. @cindex Divisibility algorithm @cindex Congruence algorithm @@ -8626,8 +8295,9 @@ leads to divisibility or congruence tests which are potentially more efficient than a normal division. The factor of @math{b^n} on @math{r} can be ignored in a GCD when @math{d} is -odd, hence the use of @code{mpn_modexact_1_odd} by @code{mpn_gcd_1} and -@code{mpz_kronecker_ui} etc (@pxref{Greatest Common Divisor Algorithms}). +odd, hence the use of @code{mpn_bdivmod} in @code{mpn_gcd}, and the use of +@code{mpn_modexact_1_odd} by @code{mpn_gcd_1} and @code{mpz_kronecker_ui} etc +(@pxref{Greatest Common Divisor Algorithms}). Montgomery's REDC method for modular multiplications uses operands of the form of @m{xb^{-n}, x*b^-n} and @m{yb^{-n}, y*b^-n} and on calculating @m{(xb^{-n}) @@ -8764,7 +8434,7 @@ single-limb elements. This is done by the function @code{mpn_hgcd2}. The resulting matrix is applied to the inputs using @code{mpn_mul_1} and @code{mpn_submul_1}. Each iteration usually reduces the inputs by almost one limb. In the rare case of a large quotient, no progress can be made by -examining just the most significant two limbs, and the quotient is computed +examining just the most significant two limbs, and the quotient is computing using plain division. The resulting algorithm is asymptotically @math{O(N^2)}, just as the Euclidean @@ -8881,9 +8551,6 @@ current size of the cofactors. @subsection Jacobi Symbol @cindex Jacobi symbol algorithm -[This section is obsolete. The current Jacobi code actually uses a very -efficient algorithm.] - @code{mpz_jacobi} and @code{mpz_kronecker} are currently implemented with a simple binary algorithm similar to that described for the GCDs (@pxref{Binary GCD}). They're not very fast when both inputs are large. Lehmer's multi-step @@ -8930,10 +8597,14 @@ exponent. Larger exponents use larger values of @math{k}, the choice being made to minimize the average number of multiplications that must supplement the squaring. -The modular multiplies and squarings use either a simple division or the REDC +The modular multiplies and squares use either a simple division or the REDC method by Montgomery (@pxref{References}). REDC is a little faster, essentially saving N single limb divisions in a fashion similar to an exact -remainder (@pxref{Exact Remainder}). +remainder (@pxref{Exact Remainder}). The current REDC has some limitations. +It's only @math{O(N^2)} so above @code{POWM_THRESHOLD} division becomes faster +and is used. It doesn't attempt to detect small bases, but rather always uses +a REDC form, which is usually a full size operand. And lastly it's only +applied to odd moduli. @node Root Extraction Algorithms, Radix Conversion Algorithms, Powering Algorithms, Algorithms @@ -9092,7 +8763,7 @@ to save operations, so long as the lookup tables don't become too big. A square root must still be taken for any value that passes these tests, to verify it's really a square and not one of the small fraction of non-squares -that get through (i.e.@: a pseudo-square to all the tested bases). +that get through (ie.@: a pseudo-square to all the tested bases). Clearly more residue tests could be done, @code{mpz_perfect_square_p} only uses a compact and efficient set. Big inputs would probably benefit from more @@ -9194,7 +8865,7 @@ calculating a bigger radix power. Another possible improvement for the sub-quadratic part would be to arrange for radix powers that balanced the sizes of quotient and remainder produced, -i.e.@: the highest power would be an @m{b^{nk},b^(n*k)} approximately equal to +ie.@: the highest power would be an @m{b^{nk},b^(n*k)} approximately equal to @m{\sqrt{t},sqrt(t)}, not restricted to a @math{2^i} factor. That ought to smooth out a graph of times against sizes, but may or may not be a net speedup. @@ -9285,75 +8956,42 @@ for an arbitrary @math{n}. @subsection Factorial @cindex Factorial algorithm -Factorials are calculated by a combination of two algorithms. An idea is -shared among them: to compute the odd part of the factorial; a final step -takes account of the power of @math{2} term, by shifting. - -For small @math{n}, the odd factor of @math{n!} is computed with the simple -observation that it is equal to the product of all positive odd numbers -smaller than @math{n} times the odd factor of @m{\lfloor n/2\rfloor!, [n/2]!}, -where @m{\lfloor x\rfloor, [x]} is the integer part of @math{x}, and so on -recursively. The procedure can be best illustrated with an example, +Factorials are calculated by a combination of removal of twos, powering, and +binary splitting. The procedure can be best illustrated with an example, @quotation -@math{23! = (23.21.19.17.15.13.11.9.7.5.3)(11.9.7.5.3)(5.3)2^{19}} +@math{23! = 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23} @end quotation -Current code collects all the factors in a single list, with a loop and no -recursion, and compute the product, with no special care for repeated chunks. - -When @math{n} is larger, computation pass trough prime sieving. An helper -function is used, as suggested by Peter Luschny: -@tex -$$\mathop{\rm msf}(n) = {n!\over\lfloor n/2\rfloor!^2\cdot2^k} = \prod_{p=3}^{n} -p^{\mathop{\rm L}(p,n)} $$ -@end tex -@ifnottex - -@example - n - ----- - n! | | L(p,n) -msf(n) = -------------- = | | p - [n/2]!^2.2^k p=3 -@end example -@end ifnottex +@noindent +has factors of two removed, -Where @math{p} ranges on odd prime numbers. The exponent @math{k} is chosen to -obtain an odd integer number: @math{k} is the number of 1 bits in the binary -representation of @m{\lfloor n/2\rfloor, [n/2]}. The function L@math{(p,n)} -can be defined as zero when @math{p} is composite, and, for any prime -@math{p}, it is computed with: -@tex -$$\mathop{\rm L}(p,n) = \sum_{i>0}\left\lfloor{n\over p^i}\right\rfloor\bmod2 -\leq\log_p(n)$$ -@end tex -@ifnottex +@quotation +@math{23! = 2^{19}.1.1.3.1.5.3.7.1.9.5.11.3.13.7.15.1.17.9.19.5.21.11.23} +@end quotation -@example - --- - \ n -L(p,n) = / [---] mod 2 <= log (n) . - --- p^i p - i>0 -@end example -@end ifnottex +@noindent +and the resulting terms collected up according to their multiplicity, -With this helper function, we are able to compute the odd part of @math{n!} -using the recursion implied by @m{n!=\lfloor n/2\rfloor!^2\cdot\mathop{\rm -msf}(n)\cdot2^k , n!=[n/2]!^2*msf(n)*2^k}. The recursion stops using the -small-@math{n} algorithm on some @m{\lfloor n/2^i\rfloor, [n/2^i]}. +@quotation +@math{23! = 2^{19}.(3.5)^3.(7.9.11)^2.(13.15.17.19.21.23)} +@end quotation -Both the above algorithms use binary splitting to compute the product of many -small factors. At first as many products as possible are accumulated in a -single register, generating a list of factors that fit in a machine word. This -list is then split into halves, and the product is computed recursively. +Each sequence such as @math{13.15.17.19.21.23} is evaluated by splitting into +every second term, as for instance @math{(13.17.21).(15.19.23)}, and the same +recursively on each half. This is implemented iteratively using some bit +twiddling. Such splitting is more efficient than repeated N@cross{}1 multiplies since it forms big multiplies, allowing Karatsuba and higher algorithms to be used. And even below the Karatsuba threshold a big block of work can be more efficient for the basecase algorithm. +Splitting into subsequences of every second term keeps the resulting products +more nearly equal in size than would the simpler approach of say taking the +first half and second half of the sequence. Nearly equal products are more +efficient for the current multiply implementation. + @node Binomial Coefficients Algorithm, Fibonacci Numbers Algorithm, Factorial Algorithm, Other Algorithms @subsection Binomial Coefficients @@ -9533,7 +9171,7 @@ are also very good and this is the default algorithm used by GMP. @cindex Linear congruential algorithm Linear congruential generators are described in many text books, for instance Knuth volume 2 (@pxref{References}). With a modulus @math{M} and parameters -@math{A} and @math{C}, an integer state @math{S} is iterated by the formula +@math{A} and @math{C}, a integer state @math{S} is iterated by the formula @math{S @leftarrow{} A@GMPmultiply{}S+C @bmod{} M}. At each step the new state is a linear function of the previous, mod @math{M}, hence the name of the generator. @@ -10480,10 +10118,7 @@ evaluating it, @example struct __gmp_binary_plus @{ - static void eval(mpf_t f, const mpf_t g, const mpf_t h) - @{ - mpf_add(f, g, h); - @} + static void eval(mpf_t f, mpf_t g, mpf_t h) @{ mpf_add(f, g, h); @} @}; @end example @@ -10516,7 +10151,7 @@ mpf_class & mpf_class::operator=(const __gmp_expr<T> &expr) template <class Op> void __gmp_expr<__gmp_binary_expr<mpf_class, mpf_class, Op> >::eval -(mpf_t f, mp_bitcnt_t precision) +(mpf_t f, unsigned long int precision) @{ Op::eval(f, expr.val1.get_mpf_t(), expr.val2.get_mpf_t()); @} @@ -10552,7 +10187,7 @@ And the corresponding specializations of @code{__gmp_expr::eval}: template <class T, class U, class Op> void __gmp_expr <__gmp_binary_expr<__gmp_expr<T>, __gmp_expr<U>, Op> >::eval -(mpf_t f, mp_bitcnt_t precision) +(mpf_t f, unsigned long int precision) @{ // declare two temporaries mpf_class temp1(expr.val1, precision), temp2(expr.val2, precision); @@ -10594,9 +10229,8 @@ was a driving force behind many of the optimizations in GMP 3. Paul also wrote the new GMP 4.3 nth root code (with Torbj@"orn). Ken Weber (Kent State University, Universidade Federal do Rio Grande do Sul) -contributed now defunct versions of @code{mpz_gcd}, @code{mpz_divexact}, -@code{mpn_gcd}, and @code{mpn_bdivmod}, partially supported by CNPq (Brazil) -grant 301314194-2. +contributed @code{mpz_gcd}, @code{mpz_divexact}, @code{mpn_gcd}, and +@code{mpn_bdivmod}, partially supported by CNPq (Brazil) grant 301314194-2. Per Bothner of Cygnus Support helped to set up GMP to use Cygnus' configure. He has also made valuable suggestions and tested numerous intermediary @@ -10642,46 +10276,19 @@ Jason Moxham rewrote @code{mpz_fac_ui}. Pedro Gimeno implemented the Mersenne Twister and made other random number improvements. -Niels M@"oller wrote the sub-quadratic GCD, extended GCD and jacobi code, the +Niels M@"oller wrote the sub-quadratic GCD and extended GCD code, the quadratic Hensel division code, and (with Torbj@"orn) the new divide and conquer division code for GMP 4.3. Niels also helped implement the new Toom -multiply code for GMP 4.3 and implemented helper functions to simplify Toom -evaluations for GMP 5.0. He wrote the original version of mpn_mulmod_bnm1, and -he is the main author of the mini-gmp package used for gmp bootstrapping. +multiply code for GMP 4.3. Alberto Zanoni and Marco Bodrato suggested the unbalanced multiply strategy, and found the optimal strategies for evaluation and interpolation in Toom -multiplication. - -Marco Bodrato helped implement the new Toom multiply code for GMP 4.3 and -implemented most of the new Toom multiply and squaring code for 5.0. -He is the main author of the current mpn_mulmod_bnm1 and mpn_mullo_n. Marco -also wrote the functions mpn_invert and mpn_invertappr. He is the author of -the current combinatorial functions: binomial, factorial, multifactorial, -primorial. +multiplication. Marco also helped implement the new Toom multiply code for +GMP 4.3. David Harvey suggested the internal function @code{mpn_bdiv_dbm1}, implementing division relevant to Toom multiplication. He also worked on fast assembly -sequences, in particular on a fast AMD64 @code{mpn_mul_basecase}. He wrote -the internal middle product functions @code{mpn_mulmid_basecase}, -@code{mpn_toom42_mulmid}, @code{mpn_mulmid_n} and related helper routines. - -Martin Boij wrote @code{mpn_perfect_power_p}. - -Marc Glisse improved @file{gmpxx.h}: use fewer temporaries (faster), -specializations of @code{numeric_limits} and @code{common_type}, C++11 -features (move constructors, explicit bool conversion, UDL), make the -conversion from @code{mpq_class} to @code{mpz_class} explicit, optimize -operations where one argument is a small compile-time constant, replace -some heap allocations by stack allocations. He also fixed the eofbit -handling of C++ streams, and removed one division from @file{mpq/aors.c}. - -David S Miller wrote assembly code for SPARC T3 and T4. - -Mark Sofroniou cleaned up the types of mul_fft.c, letting it work for huge -operands. - -Ulrich Weigand ported GMP to the powerpc64le ABI. +sequences, in particular on a fast AMD64 @code{mpn_mul_basecase}. (This list is chronological, not ordered after significance. If you have contributed to GMP but are not listed above, please tell @@ -10691,11 +10298,8 @@ The development of floating point functions of GNU MP 2, were supported in part by the ESPRIT-BRA (Basic Research Activities) 6846 project POSSO (POlynomial System SOlving). -The development of GMP 2, 3, and 4.0 was supported in part by the IDA Center -for Computing Sciences. - -The development of GMP 4.3, 5.0, and 5.1 was supported in part by the Swedish -Foundation for Strategic Research. +The development of GMP 2, 3, and 4 was supported in part by the IDA Center for +Computing Sciences. Thanks go to Hans Thorsen for donating an SGI system for the GMP test system environment. @@ -10722,7 +10326,7 @@ Analytic Number Theory and Computational Complexity'', Wiley, 1998. @item Richard Crandall and Carl Pomerance, ``Prime Numbers: A Computational Perspective'', 2nd edition, Springer-Verlag, 2005. -@texlinebreak{} @uref{http://www.math.dartmouth.edu/~carlp/} +@texlinebreak{} @uref{http://math.dartmouth.edu/~carlp/} @item Henri Cohen, ``A Course in Computational Algebraic Number Theory'', Graduate @@ -10745,8 +10349,8 @@ Applied Cryptography'', @uref{http://www.cacr.math.uwaterloo.ca/hac/} @item Richard M. Stallman and the GCC Developer Community, ``Using the GNU Compiler Collection'', Free Software Foundation, 2008, available online -@uref{https://gcc.gnu.org/onlinedocs/}, and in the GCC package -@uref{https://ftp.gnu.org/gnu/gcc/} +@uref{http://gcc.gnu.org/onlinedocs/}, and in the GCC package +@uref{ftp://ftp.gnu.org/gnu/gcc/} @end itemize @section Papers @@ -10755,8 +10359,8 @@ Collection'', Free Software Foundation, 2008, available online @item Yves Bertot, Nicolas Magaud and Paul Zimmermann, ``A Proof of GMP Square Root'', Journal of Automated Reasoning, volume 29, 2002, pp.@: 225-252. Also -available online as INRIA Research Report 4475, June 2002, -@uref{http://hal.inria.fr/docs/00/07/21/13/PDF/RR-4475.pdf} +available online as INRIA Research Report 4475, June 2001, +@uref{http://www.inria.fr/rrrt/rr-4475.html} @item Christoph Burnikel and Joachim Ziegler, ``Fast Recursive Division'', @@ -10766,15 +10370,15 @@ Max-Planck-Institut fuer Informatik Research Report MPI-I-98-1-022, @item Torbj@"orn Granlund and Peter L. Montgomery, ``Division by Invariant Integers using Multiplication'', in Proceedings of the SIGPLAN PLDI'94 Conference, June -1994. Also available @uref{https://gmplib.org/~tege/divcnst-pldi94.pdf}. +1994. Also available @uref{ftp://ftp.cwi.nl/pub/pmontgom/divcnst.psa4.gz} +(and .psl.gz). @item -Niels M@"oller and Torbj@"orn Granlund, ``Improved division by invariant -integers'', IEEE Transactions on Computers, 11 June 2010. -@uref{https://gmplib.org/~tege/division-paper.pdf} +Niels M"oller and Torbj@"orn Granlund, ``Improved division by invariant +integers'', to appear. @item -Torbj@"orn Granlund and Niels M@"oller, ``Division of integers large and +Torbj@"orn Granlund and Niels M"oller, ``Division of integers large and small'', to appear. @item @@ -10846,7 +10450,7 @@ volume 21, number 1, March 1995, pp.@: 111-122. @item Paul Zimmermann, ``Karatsuba Square Root'', INRIA Research Report 3805, -November 1999, @uref{http://hal.inria.fr/inria-00072854/PDF/RR-3805.pdf} +November 1999, @uref{http://www.inria.fr/rrrt/rr-3805.html} @item Paul Zimmermann, ``A Proof of GMP Fast Division and Square Root |