diff options
Diffstat (limited to 'gnu/lib/libgmp/gmp.texi')
| -rw-r--r-- | gnu/lib/libgmp/gmp.texi | 2697 |
1 files changed, 2697 insertions, 0 deletions
diff --git a/gnu/lib/libgmp/gmp.texi b/gnu/lib/libgmp/gmp.texi new file mode 100644 index 00000000000..97bab692f3b --- /dev/null +++ b/gnu/lib/libgmp/gmp.texi @@ -0,0 +1,2697 @@ +\input texinfo @c -*-texinfo-*- +@c %**start of header +@setfilename gmp.info +@settitle GNU MP 2.0.2 +@synindex tp fn +@iftex +@afourpaper +@end iftex +@comment %**end of header + +@ifinfo +@format +START-INFO-DIR-ENTRY +* gmp: (gmp). GNU Multiple Precision Arithmetic Library. +END-INFO-DIR-ENTRY +@end format +@end ifinfo + +@c smallbook + +@iftex +@finalout +@end iftex + +@c Note: the edition number is listed in *three* places; please update +@c all three. Also, update the month and year where appropriate. + +@c ==> Update edition number for settitle and subtitle, and in the +@c ==> following paragraph; update date, too. + + +@ifinfo +This file documents GNU MP, a library for arbitrary-precision arithmetic. + +Copyright (C) 1991, 1993, 1994, 1995, 1996 Free Software Foundation, Inc. + +Permission is granted to make and distribute verbatim copies of +this manual provided the copyright notice and this permission notice +are preserved on all copies. + +@ignore +Permission is granted to process this file through TeX and print the +results, provided the printed document carries copying permission +notice identical to this one except for the removal of this paragraph +(this paragraph not being relevant to the printed manual). + +@end ignore +Permission is granted to copy and distribute modified versions of this +manual under the conditions for verbatim copying, provided that the entire +resulting derived work is distributed under the terms of a permission +notice identical to this one. + +Permission is granted to copy and distribute translations of this manual +into another language, under the above conditions for modified versions, +except that this permission notice may be stated in a translation approved +by the Foundation. +@end ifinfo + +@setchapternewpage on +@titlepage +@c use the new format for titles + +@title GNU MP +@subtitle The GNU Multiple Precision Arithmetic Library +@subtitle Edition 2.0.2 +@subtitle June 1996 + +@author by Torbj@"orn Granlund, TMG Datakonsult + +@c Include the Distribution inside the titlepage so +@c that headings are turned off. + +@tex +\global\parindent=0pt +\global\parskip=8pt +\global\baselineskip=13pt +@end tex + +@page +@vskip 0pt plus 1filll +Copyright @copyright{} 1991, 1993, 1994, 1995, 1996 Free Software Foundation, Inc. + +@sp 2 + +Published by the Free Software Foundation @* +59 Temple Place - Suite 330 @* +Boston, MA 02111-1307, USA @* + +Permission is granted to make and distribute verbatim copies of +this manual provided the copyright notice and this permission notice +are preserved on all copies. + +Permission is granted to copy and distribute modified versions of this +manual under the conditions for verbatim copying, provided that the entire +resulting derived work is distributed under the terms of a permission +notice identical to this one. + +Permission is granted to copy and distribute translations of this manual +into another language, under the above conditions for modified versions, +except that this permission notice may be stated in a translation approved +by the Foundation. +@end titlepage +@headings double + +@ifinfo +@node Top, Copying, (dir), (dir) + +@top GNU MP + +This manual documents how to install and use the GNU multiple precision +arithmetic library, version 2.0.2. + +@end ifinfo + +@menu +* Copying:: GMP Copying Conditions (LGPL). +* Introduction to MP:: Brief introduction to GNU MP. +* Installing MP:: How to configure and compile the MP library. +* MP Basics:: What every MP user should now. +* Reporting Bugs:: How to usefully report bugs. +* Integer Functions:: Functions for arithmetic on signed integers. +* Rational Number Functions:: Functions for arithmetic on rational numbers. +* Floating-point Functions:: Functions for arithmetic on floats. +* Low-level Functions:: Fast functions for natural numbers. +* BSD Compatible Functions:: All functions found in BSD MP. +* Custom Allocation:: How to customize the internal allocation. + +* Contributors:: +* References:: +* Concept Index:: +* Function Index:: +@end menu + +@node Copying, Introduction to MP, Top, Top +@comment node-name, next, previous, up +@unnumbered GNU MP Copying Conditions +@cindex Copying conditions +@cindex Conditions for copying GNU MP + +This library is @dfn{free}; this means that everyone is free to use it and +free to redistribute it on a free basis. The library is not in the public +domain; it is copyrighted and there are restrictions on its distribution, but +these restrictions are designed to permit everything that a good cooperating +citizen would want to do. What is not allowed is to try to prevent others +from further sharing any version of this library that they might get from +you.@refill + +Specifically, we want to make sure that you have the right to give away copies +of the library, that you receive source code or else can get it if you want +it, that you can change this library or use pieces of it in new free programs, +and that you know you can do these things.@refill + +To make sure that everyone has such rights, we have to forbid you to deprive +anyone else of these rights. For example, if you distribute copies of the GNU +MP library, you must give the recipients all the rights that you have. You +must make sure that they, too, receive or can get the source code. And you +must tell them their rights.@refill + +Also, for our own protection, we must make certain that everyone finds out +that there is no warranty for the GNU MP library. If it is modified by +someone else and passed on, we want their recipients to know that what they +have is not what we distributed, so that any problems introduced by others +will not reflect on our reputation.@refill + +The precise conditions of the license for the GNU MP library are found in the +Library General Public License that accompany the source code.@refill + +@node Introduction to MP, Installing MP, Copying, Top +@comment node-name, next, previous, up +@chapter Introduction to GNU MP + + +GNU MP is a portable library written in C for arbitrary precision arithmetic +on integers, rational numbers, and floating-point numbers. It aims to provide +the fastest possible arithmetic for all applications that need higher +precision than is directly supported by the basic C types. + +Many applications use just a few hundred bits of precision; but some +applications may need thousands or even millions of bits. MP is designed to +give good performance for both, by choosing algorithms based on the sizes of +the operands, and by carefully keeping the overhead at a minimum. + +The speed of MP is achieved by using fullwords as the basic arithmetic type, +by using sophisticated algorithms, by including carefully optimized assembly +code for the most common inner loops for many different CPUs, and by a general +emphasis on speed (as opposed to simplicity or elegance). + +There is carefully optimized assembly code for these CPUs: DEC Alpha, Amd +29000, HPPA 1.0 and 1.1, Intel Pentium and generic x86, Intel i960, Motorola +MC68000, MC68020, MC88100, and MC88110, Motorola/IBM PowerPC, National +NS32000, IBM POWER, MIPS R3000, R4000, SPARCv7, SuperSPARC, generic SPARCv8, +and DEC VAX. Some optimizations also for ARM, Clipper, IBM ROMP (RT), and +Pyramid AP/XP. + +This version of MP is released under a more liberal license than previous +versions. It is now permitted to link MP to non-free programs, as long as MP +source code is provided when distributing the non-free program. + + +@section How to use this Manual + +Everyone should read @ref{MP Basics}. If you need to install the library +yourself, you need to read @ref{Installing MP}, too. + +The rest of the manual can be used for later reference, although it is +probably a good idea to glance through it. + + +@node Installing MP, MP Basics, Introduction to MP, Top +@comment node-name, next, previous, up +@chapter Installing MP +@cindex Installation + +To build MP, you first have to configure it for your CPU and operating system. +You need a C compiler, preferably GCC, but any reasonable compiler should +work. And you need a standard Unix @samp{make} program, plus some other +standard Unix utility programs. + +(If you're on an MS-DOS machine, your can build MP using @file{make.bat}. It +requires that djgpp is installed. It does not require configuration, nor is +@samp{make} needed; @file{make.bat} both configures and builds the library.) + +Here are the steps needed to install the library on Unix systems: + +@enumerate +@item +In most cases, @samp{./configure --target=cpu-vendor-os}, should work both for +native and cross-compilation. If you get error messages, your machine might +not be supported. + +If you want to compile in a separate object directory, cd to that directory, +and prefix the configure command with the path to the MP source directory. +Not all @samp{make} programs have the necessary features to support this. In +particular, SunOS and Slowaris @samp{make} have bugs that makes them unable to +build from a separate object directory. Use GNU @samp{make} instead. + +In addition to the standard cpu-vendor-os tuples, MP recognizes sparc8 and +supersparc as valid CPU names. Specifying these CPU names for relevant +systems will improve performance significantly. + +In general, if you want a library that runs as fast as possible, you should +make sure you configure MP for the exact CPU type your system uses. + +If you have @code{gcc} in your @code{PATH}, it will be used by default. To +override this, pass @samp{-with-gcc=no} to @file{configure}. + +@item +@samp{make} + +This will compile MP, and create a library archive file @file{libgmp.a} in the +working directory. + +@item +@samp{make check} + +This will make sure MP was built correctly. If you get error messages, please +report this to @samp{bug-gmp@@prep.ai.mit.edu}. (@xref{Reporting Bugs}, for +information on what to include in useful bug reports.) + +@item +@samp{make install} + +This will copy the file @file{gmp.h} and @file{libgmp.a}, as well as the info +files, to @file{/usr/local} (or if you passed the @samp{--prefix} option to +@file{configure}, to the directory given as argument to @samp{--prefix}). +@end enumerate + +@noindent +If you wish to build and install the BSD MP compatible functions, use +@samp{make libmp.a} and @samp{make install-bsdmp}. + +There are some other useful make targets: + +@itemize @bullet +@item +@samp{doc} + +Create a DVI version of the manual, in @file{gmp.dvi} and a set of info files, +in @file{gmp.info}, @file{gmp.info-1}, @file{gmp.info-2}, etc. + +@item +@samp{ps} + +Create a Postscript version of the manual, in @file{gmp.ps}. + +@item +@samp{html} + +Create a HTML version of the manual, in @file{gmp.html}. + +@item +@samp{clean} + +Delete all object files and archive files, but not the configuration files. + +@item +@samp{distclean} + +Delete all files not included in the distribution. + +@item +@samp{uninstall} + +Delete all files copied by @samp{make install}. +@end itemize + + +@section Known Build Problems + +GCC 2.7.2 (as well as 2.6.3) for the RS/6000 and PowerPC can not be used to +compile MP, due to a bug in GCC. If you want to use GCC for these machines, +you need to apply the patch below to GCC, or use a later version of the +compiler. + +If you are on a Sequent Symmetry, use the GNU assembler instead of the +system's assembler, since the latter has serious bugs. + +The system compiler on NeXT is a massacred and old gcc, even if the compiler +calls itself @file{cc}. This compiler cannot be used to build MP. You need +to get a real gcc, and install that before you compile MP. (NeXT might have +fixed this in newer releases of their system.) + +The system C compiler under SunOS 4 has a bug that makes it miscompile +mpq/get_d.c. This will make @samp{make check} fail. + +Please report other problems to @samp{bug-gmp@@prep.ai.mit.edu}. +@xref{Reporting Bugs}. + + +Patch to apply to GCC 2.6.3 and 2.7.2: + +@example +*** config/rs6000/rs6000.md Sun Feb 11 08:22:11 1996 +--- config/rs6000/rs6000.md.new Sun Feb 18 03:33:37 1996 +*************** +*** 920,926 **** + (set (match_operand:SI 0 "gpc_reg_operand" "=r") + (not:SI (match_dup 1)))] + "" +! "nor. %0,%2,%1" + [(set_attr "type" "compare")]) + + (define_insn "" +--- 920,926 ---- + (set (match_operand:SI 0 "gpc_reg_operand" "=r") + (not:SI (match_dup 1)))] + "" +! "nor. %0,%1,%1" + [(set_attr "type" "compare")]) + + (define_insn "" +@end example + +@node MP Basics, Reporting Bugs, Installing MP, Top +@comment node-name, next, previous, up +@chapter MP Basics + + +@cindex @file{gmp.h} +All declarations needed to use MP are collected in the include file +@file{gmp.h}. It is designed to work with both C and C++ compilers. + + +@section Nomenclature and Types + +@cindex Integer +@tindex @code{mpz_t} +@noindent +In this manual, @dfn{integer} usually means a multiple precision integer, as +defined by the MP library. The C data type for such integers is @code{mpz_t}. +Here are some examples of how to declare such integers: + +@example +mpz_t sum; + +struct foo @{ mpz_t x, y; @}; + +mpz_t vec[20]; +@end example + +@cindex Rational number +@tindex @code{mpq_t} +@noindent +@dfn{Rational number} means a multiple precision fraction. The C data type +for these fractions is @code{mpq_t}. For example: + +@example +mpq_t quotient; +@end example + +@cindex Floating-point number +@tindex @code{mpf_t} +@noindent +@dfn{Floating point number} or @dfn{Float} for short, is an arbitrary precision +mantissa with an limited precision exponent. The C data type for such objects +is @code{mpf_t}. + +@cindex Limb +@tindex @code{mp_limb_t} +@noindent +A @dfn{limb} means the part of a multi-precision number that fits in a single +word. (We chose this word because a limb of the human body is analogous to a +digit, only larger, and containing several digits.) Normally a limb contains +32 or 64 bits. The C data type for a limb is @code{mp_limb_t}. + + +@section Function Classes + +There are six classes of functions in the MP library: + +@enumerate +@item +Functions for signed integer arithmetic, with names beginning with +@code{mpz_}. The associated type is @code{mpz_t}. There are about 100 +functions in this class. + +@item +Functions for rational number arithmetic, with names beginning with +@code{mpq_}. The associated type is @code{mpq_t}. There are about 20 +functions in this class, but the functions in the previous class can be used +for performing arithmetic on the numerator and denominator separately. + +@item +Functions for floating-point arithmetic, with names beginning with +@code{mpf_}. The associated type is @code{mpf_t}. There are about 50 +functions is this class. + +@item +Functions compatible with Berkeley MP, such as @code{itom}, @code{madd}, and +@code{mult}. The associated type is @code{MINT}. + +@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_}. There are about 30 (hard-to-use) functions in this class. + +The associated type is array of @code{mp_limb_t}. + +@item +Miscellaneous functions. Functions for setting up custom allocation. +@end enumerate + + +@section MP Variable Conventions + +As a general rule, all MP functions expect output arguments before input +arguments. This notation is based on an analogy with the assignment operator. +(The BSD MP compatibility functions disobey this rule, having the output +argument(s) last.) + +MP allows you to use the same variable for both input and output in the same +expression. For example, the main function for integer multiplication, +@code{mpz_mul}, can be used like this: @code{mpz_mul (x, x, x)}. This +computes the square of @var{x} and puts the result back in @var{x}. + +Before you can assign to an MP variable, you need to initialize it by calling +one of the special initialization functions. When you're done with a +variable, you need to clear it out, using one of the functions for that +purpose. Which function to use depends on the type of variable. See the +chapters on integer functions, rational number functions, and floating-point +functions for details. + +A variable should only be initialized once, or at least cleared out between +each initialization. After a variable has been initialized, it may be +assigned to any number of times. + +For efficiency reasons, avoid to initialize and clear out a variable in loops. +Instead, initialize it before entering the loop, and clear it out after the +loop has exited. + +You don't need to be concerned about allocating additional space for MP +variables. All functions in MP automatically allocate additional space when a +variable does not already have enough space. They do not, however, reduce the +space when a smaller number is stored in the object. Most of the time, this +policy is best, since it avoids frequent re-allocation. + + +@section Useful Macros and Constants + +@deftypevr {Global Constant} {const int} mp_bits_per_limb +The number of bits per limb. +@end deftypevr + +@defmac __GNU_MP_VERSION +@defmacx __GNU_MP_VERSION_MINOR +The major and minor MP version, respectively, as integers. +@end defmac + +@section Compatibility with Version 1.x + +This version of MP is upward compatible with previous versions of MP, with a +few exceptions. + +@enumerate +@item Integer division functions round the result differently. The old +functions (@code{mpz_div}, @code{mpz_divmod}, @code{mpz_mdiv}, +@code{mpz_mdivmod}, etc) now all use floor rounding (i.e., they round the +quotient to @minus{}infinity). There are a lot of new functions for integer +division, giving the user better control over the rounding. + +@item The function @code{mpz_mod} now compute the true @strong{mod} function. + +@item The functions @code{mpz_powm} and @code{mpz_powm_ui} now use +@strong{mod} for reduction. + +@item The assignment functions for rational numbers do no longer canonicalize +their results. In the case a non-canonical result could arise from an +assignment, the user need to insert an explicit call to +@code{mpq_canonicalize}. This change was made for efficiency. + +@item Output generated by @code{mpz_out_raw} in this release cannot be read +by @code{mpz_inp_raw} in previous releases. This change was made for making +the file format truly portable between machines with different word sizes. + +@item Several @code{mpn} functions have changed. But they were intentionally +undocumented in previous releases. + +@item The functions @code{mpz_cmp_ui}, @code{mpz_cmp_si}, and @code{mpq_cmp_ui} +are now implementated as macros, and thereby sometimes evaluate their +arguments multiple times. + +@item The functions @code{mpz_pow_ui} and @code{mpz_ui_pow_ui} now yield 1 +for 0^0. (In version 1, they yielded 0.) + +@end enumerate + + +@section Getting the Latest Version of MP + +The latest version of the MP library is available by anonymous ftp from +from @samp{prep.ai.mit.edu}. The file name is +@file{/pub/gnu/gmp-M.N.tar.gz}. Many sites around the world mirror +@samp{prep}; please use a mirror site near you. + +@node Reporting Bugs, Integer Functions, MP Basics, Top +@comment node-name, next, previous, up +@chapter Reporting Bugs +@cindex Reporting bugs + +If you think you have found a bug in the MP library, please investigate it and +report it. We have made this library available to you, and it is not to ask +too much from you, to ask you to report the bugs that you find. + +There are a few things you should think about when you put your bug report +together. + +You have to send us a test case that makes it possible for us to reproduce the +bug. Include instructions on how to run the test case. + +You also have to explain what is wrong; if you get a crash, or if the results +printed are incorrect and in that case, in what way. + +It is not uncommon that an observed problem is actually due to a bug in the +compiler used when building MP; the MP code tends to explore interesting +corners in compilers. Therefore, please include compiler version information +in your bug report. This can be extracted using @samp{what `which cc`}, or, +if you're using gcc, @samp{gcc -v}. Also, include the output from @samp{uname +-a}. + +If your bug report is good, we will do our best to help you to get a corrected +version of the library; if the bug report is poor, we won't do anything about +it (aside of chiding you to send better bug reports). + +Send your bug report to: @samp{bug-gmp@@prep.ai.mit.edu}. + +If you think something in this manual is unclear, or downright incorrect, or if +the language needs to be improved, please send a note to the same address. + + +@node Integer Functions, Rational Number Functions, Reporting Bugs, Top +@comment node-name, next, previous, up +@chapter Integer Functions +@cindex Integer functions + +This chapter describes the MP functions for performing integer arithmetic. +These functions start with the prefix @code{mpz_}. + +Arbitrary precision integers are stored in objects of type @code{mpz_t}. + +@menu +* Initializing Integers:: +* Assigning Integers:: +* Simultaneous Integer Init & Assign:: +* Converting Integers:: +* Integer Arithmetic:: +* Comparison Functions:: +* Integer Logic and Bit Fiddling:: +* I/O of Integers:: +* Miscellaneous Integer Functions:: +@end menu + +@node Initializing Integers, Assigning Integers, , Integer Functions +@comment node-name, next, previous, up +@section Initialization and Assignment Functions + +The functions for integer arithmetic assume that all integer objects are +initialized. You do that by calling the function @code{mpz_init}. + +@deftypefun void mpz_init (mpz_t @var{integer}) +Initialize @var{integer} with limb space and set the initial numeric value to +0. Each variable should normally only be initialized once, or at least cleared +out (using @code{mpz_clear}) between each initialization. +@end deftypefun + +Here is an example of using @code{mpz_init}: + +@example +@{ + mpz_t integ; + mpz_init (integ); + @dots{} + mpz_add (integ, @dots{}); + @dots{} + mpz_sub (integ, @dots{}); + + /* Unless the program is about to exit, do ... */ + mpz_clear (integ); +@} +@end example + +@noindent +As you can see, you can store new values any number of times, once an +object is initialized. + +@deftypefun void mpz_clear (mpz_t @var{integer}) +Free the limb space occupied by @var{integer}. Make sure to call this +function for all @code{mpz_t} variables when you are done with them. +@end deftypefun + +@deftypefun {void *} _mpz_realloc (mpz_t @var{integer}, mp_size_t @var{new_alloc}) +Change the limb space allocation to @var{new_alloc} limbs. This function is +not normally called from user code, but it can be used to give memory back to +the heap, or to increase the space of a variable to avoid repeated automatic +re-allocation. +@end deftypefun + +@deftypefun void mpz_array_init (mpz_t @var{integer_array}[], size_t @var{array_size}, mp_size_t @var{fixed_num_bits}) +Allocate @strong{fixed} limb space for all @var{array_size} integers in +@var{integer_array}. The fixed allocation for each integer in the array is +enough to store @var{fixed_num_bits}. If the fixed space will be insufficient +for storing the result of a subsequent calculation, the result is +unpredictable. + +This function is useful for decreasing the working set for some algorithms +that use large integer arrays. + +There is no way to de-allocate the storage allocated by this function. +Don't call @code{mpz_clear}! +@end deftypefun + + +@node Assigning Integers, Simultaneous Integer Init & Assign, Initializing Integers, Integer Functions +@comment node-name, next, previous, up +@subsection Assignment Functions +@cindex Integer assignment functions + +These functions assign new values to already initialized integers +(@pxref{Initializing Integers}). + +@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}, 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}. +@end deftypefun + +@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 '\0'-terminated C string in base +@var{base}. White space is allowed in the string, and is simply ignored. The +base may vary from 2 to 36. If @var{base} is 0, the actual base is determined +from the leading characters: if the first two characters are `0x' or `0X', +hexadecimal is assumed, otherwise if the first character is `0', octal is +assumed, otherwise decimal is assumed. + +This function returns 0 if the entire string up to the '\0' is a valid +number in base @var{base}. Otherwise it returns @minus{}1. +@end deftypefun + + +@node Simultaneous Integer Init & Assign, Converting Integers, Assigning Integers, Integer Functions +@comment node-name, next, previous, up +@subsection Combined Initialization and Assignment Functions +@cindex Initialization and assignment functions + +For convenience, MP provides a parallel series of initialize-and-set functions +which initialize the output and then store the value there. These functions' +names have the form @code{mpz_init_set@dots{}} + +Here is an example of using one: + +@example +@{ + mpz_t pie; + mpz_init_set_str (pie, "3141592653589793238462643383279502884", 10); + @dots{} + mpz_sub (pie, @dots{}); + @dots{} + mpz_clear (pie); +@} +@end example + +@noindent +Once the integer has been initialized by any of the @code{mpz_init_set@dots{}} +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}, 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}) +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}, char *@var{str}, int @var{base}) +Initialize @var{rop} and set its value like @code{mpz_set_str} (see its +documentation above for details). + +If the string is a correct base @var{base} number, the function returns 0; +if an error occurs it returns @minus{}1. @var{rop} is initialized even if +an error occurs. (I.e., you have to call @code{mpz_clear} for it.) +@end deftypefun + + +@node Converting Integers, Integer Arithmetic, Simultaneous Integer Init & Assign, Integer Functions +@comment node-name, next, previous, up +@section Conversion Functions +@cindex Integer conversion functions +@cindex Conversion functions + +This section describes functions for converting arbitrary precision integers +to standard C types. Functions for converting @emph{to} arbitrary +precision integers are described in @ref{Assigning Integers} and @ref{I/O of +Integers}. + +@deftypefun {unsigned long int} mpz_get_ui (mpz_t @var{op}) +Return the least significant part from @var{op}. This function combined +with @* @code{mpz_tdiv_q_2exp(@dots{}, @var{op}, CHAR_BIT*sizeof(unsigned +long int))} can be used to extract the limbs of an integer. +@end deftypefun + +@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}. + +If @var{op} is too large to fit in a @code{signed long int}, the returned +result is probably not very useful. @c To find out if the value will fit, use +@c the function @code{mpz_fits_si}. +@end deftypefun + +@deftypefun double mpz_get_d (mpz_t @var{op}) +Convert @var{op} to a double. +@end deftypefun + +@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 may vary +from 2 to 36. + +If @var{str} is NULL, space for the result string is allocated using the +default allocation function, and a pointer to the string is returned. + +If @var{str} is not NULL, it should point to a block of storage enough large +for the result. To find out the right amount of space to provide for +@var{str}, use @code{mpz_sizeinbase (@var{op}, @var{base}) + 2}. The two +extra bytes are for a possible minus sign, and for the terminating null +character. +@end deftypefun + + +@node Integer Arithmetic, Comparison Functions, Converting Integers, Integer Functions +@comment node-name, next, previous, up +@section Arithmetic Functions +@cindex Integer arithmetic functions +@cindex Arithmetic functions + +@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}) +@ifinfo +Set @var{rop} to @var{op1} + @var{op2}. +@end ifinfo +@iftex +@tex +Set @var{rop} to $@var{op1} + @var{op2}$. +@end tex +@end iftex +@end deftypefun + +@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}) +Set @var{rop} to @var{op1} @minus{} @var{op2}. +@end deftypefun + +@deftypefun void mpz_mul (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx void mpz_mul_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +@ifinfo +Set @var{rop} to @var{op1} times @var{op2}. +@end ifinfo +@iftex +@tex +Set @var{rop} to $@var{op1} \times @var{op2}$. +@end tex +@end iftex +@end deftypefun + +@deftypefun void mpz_mul_2exp (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +@ifinfo +Set @var{rop} to @var{op1} times 2 raised to @var{op2}. This operation can +also be defined as a left shift, @var{op2} steps. +@end ifinfo +@iftex +@tex +Set @var{rop} to $@var{op1} \times 2^{op2}$. This operation can also be +defined as a left shift, @var{op2} steps. +@end tex +@end iftex +@end deftypefun + +@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}, mpz_t @var{op}) +Set @var{rop} to the absolute value of @var{op}. +@end deftypefun + +@deftypefun void mpz_fac_ui (mpz_t @var{rop}, unsigned long int @var{op}) +Set @var{rop} to @var{op}!, the factorial of @var{op}. +@end deftypefun + +@subsection Division functions + +Division is undefined if the divisor is zero, and passing a zero divisor to +the divide or modulo functions, as well passing a zero mod argument to the +@code{mpz_powm} and @code{mpz_powm_ui} functions, will make these functions +intentionally divide by zero. This gives the user the possibility to handle +arithmetic exceptions in these functions in the same manner as other +arithmetic exceptions. + +There are three main groups of division functions: +@itemize @bullet +@item +Functions that truncate the quotient towards 0. The names of these +functions start with @code{mpz_tdiv}. The @samp{t} in the name is short for +@samp{truncate}. +@item +Functions that round the quotient towards @minus{}infinity. The names of +these routines start with @code{mpz_fdiv}. The @samp{f} in the name is +short for @samp{floor}. +@item +Functions that round the quotient towards +infinity. The names of +these routines start with @code{mpz_cdiv}. The @samp{c} in the name is +short for @samp{ceil}. +@end itemize + +For each rounding mode, there are a couple of variants. Here @samp{q} means +that the quotient is computed, while @samp{r} means that the remainder is +computed. Functions that compute both the quotient and remainder have +@samp{qr} in the name. + +@deftypefun void mpz_tdiv_q (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx void mpz_tdiv_q_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +Set @var{rop} to [@var{op1}/@var{op2}]. The quotient is truncated towards +0. +@end deftypefun + +@deftypefun void mpz_tdiv_r (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx void mpz_tdiv_r_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +Set @var{rop} to (@var{op1} - [@var{op1}/@var{op2}] * @var{op2}). +Unless the remainder is zero, it has the same sign as the dividend. +@end deftypefun + +@deftypefun void mpz_tdiv_qr (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx void mpz_tdiv_qr_ui (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op1}, unsigned long int @var{op2}) +Divide @var{op1} by @var{op2} and put the quotient in @var{rop1} and the +remainder in @var{rop2}. The quotient is rounded towards 0. Unless the +remainder is zero, it has the same sign as the dividend. + +If @var{rop1} and @var{rop2} are the same variable, the results are +undefined. +@end deftypefun + +@deftypefun void mpz_fdiv_q (mpz_t @var{rop1}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx void mpz_fdiv_q_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +@ifinfo +Set @var{rop} to @var{op1}/@var{op2}. The quotient is rounded towards +@minus{}infinity. +@end ifinfo +@iftex +@tex +Set @var{rop} to $\lfloor@var{op1}/@var{op2}\rfloor$. (I.e., round +the quotient towards $-\infty$.) +@end tex +@end iftex +@end deftypefun + +@deftypefun void mpz_fdiv_r (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx {unsigned long int} mpz_fdiv_r_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +Divide @var{op1} by @var{op2} and put the remainder in @var{rop}. Unless +the remainder is zero, it has the same sign as the divisor. + +For @code{mpz_fdiv_r_ui} the remainder is small enough to fit in an +@code{unsigned long int}, and is therefore returned. +@end deftypefun + +@deftypefun void mpz_fdiv_qr (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx {unsigned long int} mpz_fdiv_qr_ui (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op1}, unsigned long int @var{op2}) +Divide @var{op1} by @var{op2} and put the quotient in @var{rop1} and the +remainder in @var{rop2}. The quotient is rounded towards @minus{}infinity. +Unless the remainder is zero, it has the same sign as the divisor. + +For @code{mpz_fdiv_qr_ui} the remainder is small enough to fit in an +@code{unsigned long int}, and is therefore returned. + +If @var{rop1} and @var{rop2} are the same variable, the results are +undefined. +@end deftypefun + +@deftypefun {unsigned long int} mpz_fdiv_ui (mpz_t @var{op1}, unsigned long int @var{op2}) +This function is similar to @code{mpz_fdiv_r_ui}, but the remainder is only +returned; it is not stored anywhere. +@end deftypefun + +@deftypefun void mpz_cdiv_q (mpz_t @var{rop1}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx void mpz_cdiv_q_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +@ifinfo +Set @var{rop} to @var{op1}/@var{op2}. The quotient is rounded towards ++infinity. +@end ifinfo +@iftex +@tex +Set @var{rop} to $\lceil@var{op1}/@var{op2}\rceil$. (I.e., round the +quotient towards $+\infty$.) +@end tex +@end iftex +@end deftypefun + +@deftypefun void mpz_cdiv_r (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx {unsigned long int} mpz_cdiv_r_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +Divide @var{op1} by @var{op2} and put the remainder in @var{rop}. Unless +the remainder is zero, it has the opposite sign as the divisor. + +For @code{mpz_cdiv_r_ui} the negated remainder is small enough to fit in an +@code{unsigned long int}, and it is therefore returned. +@end deftypefun + +@deftypefun void mpz_cdiv_qr (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx {unsigned long int} mpz_cdiv_qr_ui (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op1}, unsigned long int @var{op2}) +Divide @var{op1} by @var{op2} and put the quotient in @var{rop1} and the +remainder in @var{rop2}. The quotient is rounded towards +infinity. Unless +the remainder is zero, it has the opposite sign as the divisor. + +For @code{mpz_cdiv_qr_ui} the negated remainder is small enough to fit in an +@code{unsigned long int}, and it is therefore returned. + +If @var{rop1} and @var{rop2} are the same variable, the results are +undefined. +@end deftypefun + +@deftypefun {unsigned long int} mpz_cdiv_ui (mpz_t @var{op1}, unsigned long int @var{op2}) +Return the negated remainder, similar to @code{mpz_cdiv_r_ui}. (The +difference is that this function doesn't store the remainder anywhere.) +@end deftypefun + +@deftypefun void mpz_mod (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx {unsigned long int} mpz_mod_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +Set @var{rop} to @var{op1} @code{mod} @var{op2}. The sign of the divisor is +ignored, and the result is always non-negative. + +For @code{mpz_mod_ui} the remainder is small enough to fit in an +@code{unsigned long int}, and is therefore returned. +@end deftypefun + +@deftypefun void mpz_divexact (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +Set @var{rop} to @var{op1}/@var{op2}. This function produces correct +results only when it is known in advance that @var{op2} divides +@var{op1}. + +Since mpz_divexact is much faster than any of the other routines that produce +the quotient (@pxref{References} Jebelean), it is the best choice for +instances in which exact division is known to occur, such as reducing a +rational to lowest terms. +@end deftypefun + +@deftypefun void mpz_tdiv_q_2exp (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +@ifinfo +Set @var{rop} to @var{op1} divided by 2 raised to @var{op2}. The quotient is +rounded towards 0. +@end ifinfo +@iftex +@tex +Set @var{rop} to $@var{op1}/2^{op2}$. The quotient is rounded towards 0. +@end tex +@end iftex +@end deftypefun + +@deftypefun void mpz_tdiv_r_2exp (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +@ifinfo +Divide @var{op1} by (2 raised to @var{op2}) and put the remainder in +@var{rop}. Unless it is zero, @var{rop} will have the same sign as @var{op1}. +@end ifinfo +@iftex +@tex +Divide @var{op1} by $2^{op2}$ and put the remainder in @var{rop}. Unless it is +zero, @var{rop} will have the same sign as @var{op1}. +@end tex +@end iftex +@end deftypefun + +@deftypefun void mpz_fdiv_q_2exp (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +@ifinfo +Set @var{rop} to @var{op1} divided by 2 raised to @var{op2}. The quotient is +rounded towards @minus{}infinity. +@end ifinfo +@iftex +@tex +Set @var{rop} to $\lfloor@var{op1}/2^{op2}\rfloor$. The quotient is rounded +towards $-\infty$. +@end tex +@end iftex +@end deftypefun + +@deftypefun void mpz_fdiv_r_2exp (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2}) +@ifinfo +Divide @var{op1} by (2 raised to @var{op2}) and put the remainder in +@var{rop}. The sign of @var{rop} will always be positive. +@end ifinfo +@iftex +@tex +Divide @var{op1} by $2^{op2}$ and put the remainder in @var{rop}. The sign of +@var{rop} will always be positive. +@end tex +@end iftex + +This operation can also be defined as masking of the @var{op2} least +significant bits. +@end deftypefun + +@subsection Exponentialization Functions + +@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 (@var{base} raised to @var{exp}) @code{mod} @var{mod}. If +@var{exp} is negative, the result is undefined. +@end deftypefun + +@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 @var{base} raised to @var{exp}. +@ifinfo +The case of 0^0 yields 1. +@end ifinfo +@iftex +@tex +The case of $0^0$ yields 1. +@end tex +@end iftex +@end deftypefun + +@subsection Square Root Functions + +@deftypefun void mpz_sqrt (mpz_t @var{rop}, mpz_t @var{op}) +@ifinfo +Set @var{rop} to the truncated integer part of the square root of +@var{op}. +@end ifinfo +@iftex +@tex +Set @var{rop} to $\lfloor\sqrt{@var{op}}\rfloor$, the truncated integer +part of the square root of @var{op}. +@end tex +@end iftex +@end deftypefun + +@deftypefun void mpz_sqrtrem (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op}) +@ifinfo +Set @var{rop1} to the truncated integer part of the square root of @var{op}, +like @code{mpz_sqrt}. Set @var{rop2} to +@var{op}@minus{}@var{rop1}*@var{rop1}, +@end ifinfo +@iftex +@tex +Set @var{rop1} to $\lfloor\sqrt{@var{op}}\rfloor$, like @code{mpz_sqrt}. +Set @var{rop2} to $(@var{op} - @var{rop1}^2)$, +@end tex +@end iftex +(i.e., zero if @var{op} is a perfect square). + +If @var{rop1} and @var{rop2} are the same variable, the results are +undefined. +@end deftypefun + +@deftypefun int mpz_perfect_square_p (mpz_t @var{op}) +Return non-zero if @var{op} is a perfect square, i.e., if the square root of +@var{op} is an integer. Return zero otherwise. +@end deftypefun + +@subsection Number Theoretic Functions + +@deftypefun int mpz_probab_prime_p (mpz_t @var{op}, int @var{reps}) +@ifinfo +If this function returns 0, @var{op} is definitely not prime. If it returns +1, then @var{op} is `probably' prime. The probability of a false positive is +(1/4)**@var{reps}. +@end ifinfo +@iftex +@tex +If this function returns 0, @var{op} is definitely not prime. If it returns +1, then @var{op} is `probably' prime. The probability of a false positive is +$(1/4)^{{reps}}$. +@end tex +@end iftex +A reasonable value of reps is 25. + +An implementation of the probabilistic primality test found in Seminumerical +Algorithms (@pxref{References} Knuth). +@end deftypefun + +@deftypefun void mpz_gcd (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +Set @var{rop} to the greatest common divisor of @var{op1} and @var{op2}. +@end deftypefun + +@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 NULL, store the result there. + +If the result is small enough to fit in an @code{unsigned long int}, it is +returned. If the result does not fit, 0 is returned, and the result is equal +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}, mpz_t @var{a}, mpz_t @var{b}) +Compute @var{g}, @var{s}, and @var{t}, such that @var{a}@var{s} + +@var{b}@var{t} = @var{g} = @code{gcd} (@var{a}, @var{b}). If @var{t} is +NULL, that argument is not computed. +@end deftypefun + +@deftypefun int mpz_invert (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +Compute the inverse of @var{op1} modulo @var{op2} and put the result in +@var{rop}. Return non-zero if an inverse exist, zero otherwise. When the +function returns zero, do not assume anything about the value in @var{rop}. +@end deftypefun + +@deftypefun int mpz_jacobi (mpz_t @var{op1}, mpz_t @var{op2}) +@deftypefunx int mpz_legendre (mpz_t @var{op1}, mpz_t @var{op2}) +Compute the Jacobi and Legendre symbols, respectively. +@end deftypefun + +@need 2000 +@node Comparison Functions, Integer Logic and Bit Fiddling, Integer Arithmetic, Integer Functions +@comment node-name, next, previous, up +@section Comparison Functions + +@deftypefun int mpz_cmp (mpz_t @var{op1}, mpz_t @var{op2}) +@ifinfo +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 ifinfo +@iftex +@tex +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 tex +@end iftex +@end deftypefun + +@deftypefn Macro int mpz_cmp_ui (mpz_t @var{op1}, unsigned long int @var{op2}) +@deftypefnx Macro int mpz_cmp_si (mpz_t @var{op1}, signed long int @var{op2}) +@ifinfo +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 ifinfo +@iftex +@tex +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 tex +@end iftex + +These functions are actually implemented as macros. They evaluate their +arguments multiple times. +@end deftypefn + +@deftypefn Macro int mpz_sgn (mpz_t @var{op}) +@ifinfo +Return +1 if @var{op} > 0, 0 if @var{op} = 0, and @minus{}1 if @var{op} < 0. +@end ifinfo +@iftex +@tex +Return $+1$ if $@var{op} > 0$, 0 if $@var{op} = 0$, and $-1$ if $@var{op} < 0$. +@end tex +@end iftex + +This function is actually implemented as a macro. It evaluates its +arguments multiple times. +@end deftypefn + +@node Integer Logic and Bit Fiddling, I/O of Integers, Comparison Functions, Integer Functions +@comment node-name, next, previous, up +@section Logical and Bit Manipulation Functions +@cindex Logical functions +@cindex Bit manipulation functions + +These functions behave as if two's complement arithmetic were used (although +sign-magnitude is used by the actual implementation). + +@deftypefun void mpz_and (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +Set @var{rop} to @var{op1} logical-and @var{op2}. +@end deftypefun + +@deftypefun void mpz_ior (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +Set @var{rop} to @var{op1} inclusive-or @var{op2}. +@end deftypefun + +@c @deftypefun void mpz_xor (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2}) +@c Set @var{rop} to @var{op1} exclusive-or @var{op2}. +@c @end deftypefun + +@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 {unsigned long int} mpz_popcount (mpz_t @var{op}) +For non-negative numbers, return the population count of @var{op}. For +negative numbers, return the largest possible value (@var{MAX_ULONG}). +@end deftypefun + +@deftypefun {unsigned long int} mpz_hamdist (mpz_t @var{op1}, mpz_t @var{op2}) +If @var{op1} and @var{op2} are both non-negative, return the hamming distance +between the two operands. Otherwise, return the largest possible value +(@var{MAX_ULONG}). + +It is possible to extend this function to return a useful value when the +operands are both negative, but the current implementation returns +@var{MAX_ULONG} in this case. @strong{Do not depend on this behavior, since +it will change in future versions of the library.} +@end deftypefun + +@deftypefun {unsigned long int} mpz_scan0 (mpz_t @var{op}, unsigned long int @var{starting_bit}) +Scan @var{op}, starting with bit @var{starting_bit}, towards more significant +bits, until the first clear bit is found. Return the index of the found bit. +@end deftypefun + +@deftypefun {unsigned long int} mpz_scan1 (mpz_t @var{op}, unsigned long int @var{starting_bit}) +Scan @var{op}, starting with bit @var{starting_bit}, towards more significant +bits, until the first set bit is found. Return the index of the found bit. +@end deftypefun + +@deftypefun void mpz_setbit (mpz_t @var{rop}, unsigned long int @var{bit_index}) +Set bit @var{bit_index} in @var{op1}. +@end deftypefun + +@deftypefun void mpz_clrbit (mpz_t @var{rop}, unsigned long int @var{bit_index}) +Clear bit @var{bit_index} in @var{op1}. +@end deftypefun + +@node I/O of Integers, Miscellaneous Integer Functions, Integer Logic and Bit Fiddling, Integer Functions +@comment node-name, next, previous, up +@section Input and Output Functions +@cindex Integer input and output functions +@cindex Input functions +@cindex Output functions +@cindex I/O functions + +Functions that perform input from a stdio stream, and functions that output to +a stdio stream. Passing a 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. + +@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 may vary from 2 to 36. + +Return the number of bytes written, or if an error occurred, return 0. +@end deftypefun + +@deftypefun size_t mpz_inp_str (mpz_t @var{rop}, FILE *@var{stream}, int @var{base}) +Input a possibly white-space preceded string in base @var{base} from stdio +stream @var{stream}, and put the read integer in @var{rop}. The base may vary +from 2 to 36. If @var{base} is 0, the actual base is determined from the +leading characters: if the first two characters are `0x' or `0X', hexadecimal +is assumed, otherwise if the first character is `0', octal is assumed, +otherwise decimal is assumed. + +Return the number of bytes read, or if an error occurred, return 0. +@end deftypefun + +@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 +decreasing significance order (i.e., in big-endian). + +The output can be read with @code{mpz_inp_raw}. + +Return the number of bytes written, or if an error occurred, return 0. + +The output of this can not be read by @code{mpz_inp_raw} from GMP 1, because +of changes necessary for compatibility between 32-bit and 64-bit machines. +@end deftypefun + +@deftypefun size_t mpz_inp_raw (mpz_t @var{rop}, FILE *@var{stream}) +Input from stdio stream @var{stream} in the format written by +@code{mpz_out_raw}, and put the result in @var{rop}. Return the number of +bytes read, or if an error occurred, return 0. + +This routine can read the output from @code{mpz_out_raw} also from GMP 1, in +spite of changes necessary for compatibility between 32-bit and 64-bit +machines. +@end deftypefun + + +@need 2000 +@node Miscellaneous Integer Functions,, I/O of Integers, Integer Functions +@comment node-name, next, previous, up +@section Miscellaneous Functions +@cindex Miscellaneous integer functions + +@deftypefun void mpz_random (mpz_t @var{rop}, mp_size_t @var{max_size}) +Generate a random integer of at most @var{max_size} limbs. The generated +random number doesn't satisfy any particular requirements of randomness. +Negative random numbers are generated when @var{max_size} is negative. +@end deftypefun + +@deftypefun void mpz_random2 (mpz_t @var{rop}, mp_size_t @var{max_size}) +Generate a random integer of at most @var{max_size} limbs, with long strings +of zeros and ones in the binary representation. Useful for testing functions +and algorithms, since this kind of random numbers have proven to be more +likely to trigger corner-case bugs. Negative random numbers are generated +when @var{max_size} is negative. +@end deftypefun + +@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}.) + +@strong{This function is obsolete. It will disappear from future MP +releases.} +@end deftypefun + +@deftypefun size_t mpz_sizeinbase (mpz_t @var{op}, int @var{base}) +Return the size of @var{op} measured in number of digits in base @var{base}. +The base may vary from 2 to 36. The returned value will be exact or 1 too +big. If @var{base} is a power of 2, the returned value will always be exact. + +This function is useful in order to allocate the right amount of space before +converting @var{op} to a string. The right amount of allocation is normally +two more than the value returned by @code{mpz_sizeinbase} (one extra for a +minus sign and one for the terminating '\0'). +@end deftypefun + + +@node Rational Number Functions, Floating-point Functions, Integer Functions, Top +@comment node-name, next, previous, up +@chapter Rational Number Functions +@cindex Rational number functions + +This chapter describes the MP functions for performing arithmetic on rational +numbers. These functions start with the prefix @code{mpq_}. + +Rational numbers are stored in objects of type @code{mpq_t}. + +All rational arithmetic functions assume operands have a canonical form, and +canonicalize their result. The canonical from means that the denominator and +the numerator have no common factors, and that the denominator is positive. +Zero has the unique representation 0/1. + +Pure assignment functions do not canonicalize the assigned variable. It is +the responsibility of the user to canonicalize the assigned variable before +any arithmetic operations are performed on that variable. @strong{Note that +this is an incompatible change from version 1 of the library.} + +@deftypefun void mpq_canonicalize (mpq_t @var{op}) +Remove any factors that are common to the numerator and denominator of +@var{op}, and make the denominator positive. +@end deftypefun + +@menu +* Initializing Rationals:: +* Assigning Rationals:: +* Simultaneous Integer Init & Assign:: +* Comparing Rationals:: +* Applying Integer Functions:: +* Miscellaneous Rational Functions:: +@end menu + +@node Initializing Rationals, Assigning Rationals, Rational Number Functions, Rational Number Functions +@comment node-name, next, previous, up +@section Initialization and Assignment Functions + +@deftypefun void mpq_init (mpq_t @var{dest_rational}) +Initialize @var{dest_rational} and set it to 0/1. Each variable should +normally only be initialized once, or at least cleared out (using the function +@code{mpq_clear}) between each initialization. +@end deftypefun + +@deftypefun void mpq_clear (mpq_t @var{rational_number}) +Free the space occupied by @var{rational_number}. Make sure to call this +function for all @code{mpq_t} variables when you are done with them. +@end deftypefun + +@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 + +@deftypefun void mpq_set_ui (mpq_t @var{rop}, unsigned long int @var{op1}, unsigned long int @var{op2}) +@deftypefunx void mpq_set_si (mpq_t @var{rop}, signed long int @var{op1}, unsigned long int @var{op2}) +Set the value of @var{rop} to @var{op1}/@var{op2}. Note that if @var{op1} and +@var{op2} have common factors, @var{rop} has to be passed to +@code{mpq_canonicalize} before any operations are performed on @var{rop}. +@end deftypefun + +@node Assigning Rationals, Comparing Rationals, Initializing Rationals, Rational Number Functions +@comment node-name, next, previous, up +@section Arithmetic Functions + +@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}, 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}, mpq_t @var{multiplier}, mpq_t @var{multiplicand}) +@ifinfo +Set @var{product} to @var{multiplier} times @var{multiplicand}. +@end ifinfo +@iftex +@tex +Set @var{product} to $@var{multiplier} \times @var{multiplicand}$. +@end tex +@end iftex +@end deftypefun + +@deftypefun void mpq_div (mpq_t @var{quotient}, mpq_t @var{dividend}, mpq_t @var{divisor}) +Set @var{quotient} to @var{dividend}/@var{divisor}. +@end deftypefun + +@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_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 + +@node Comparing Rationals, Applying Integer Functions, Assigning Rationals, Rational Number Functions +@comment node-name, next, previous, up +@section Comparison Functions + +@deftypefun int mpq_cmp (mpq_t @var{op1}, mpq_t @var{op2}) +@ifinfo +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 ifinfo +@iftex +@tex +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 tex +@end iftex + +To determine if two rationals are equal, @code{mpq_equal} is faster than +@code{mpq_cmp}. +@end deftypefun + +@deftypefn Macro int mpq_cmp_ui (mpq_t @var{op1}, unsigned long int @var{num2}, unsigned long int @var{den2}) +@ifinfo +Compare @var{op1} and @var{num2}/@var{den2}. Return a positive value if +@var{op1} > @var{num2}/@var{den2}, zero if @var{op1} = @var{num2}/@var{den2}, +and a negative value if @var{op1} < @var{num2}/@var{den2}. +@end ifinfo +@iftex +@tex +Compare @var{op1} and @var{num2}/@var{den2}. Return a positive value if +$@var{op1} > @var{num2}/@var{den2}$, zero if $@var{op1} = +@var{num2}/@var{den2}$, and a negative value if $@var{op1} < +@var{num2}/@var{den2}$. +@end tex +@end iftex + +This routine allows that @var{num2} and @var{den2} have common factors. + +This function is actually implemented as a macro. It evaluates its +arguments multiple times. +@end deftypefn + +@deftypefn Macro int mpq_sgn (mpq_t @var{op}) +@ifinfo +Return +1 if @var{op} > 0, 0 if @var{op} = 0, and @minus{}1 if @var{op} < 0. +@end ifinfo +@iftex +@tex +Return $+1$ if $@var{op} > 0$, 0 if $@var{op} = 0$, and $-1$ if $@var{op} < 0$. +@end tex +@end iftex + +This function is actually implemented as a macro. It evaluates its +arguments multiple times. +@end deftypefn + +@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. +@end deftypefun + +@node Applying Integer Functions, Miscellaneous Rational Functions, Comparing Rationals, Rational Number Functions +@comment node-name, next, previous, up +@section Applying Integer Functions to Rationals + +The set of @code{mpq} functions is quite small. In particular, there are no +functions for either input or output. But there are two macros that allow us +to apply any @code{mpz} function on the numerator or denominator of a rational +number. If these macros are used to assign to the rational number, +@code{mpq_canonicalize} normally need to be called afterwards. + +@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 + +@need 2000 +@node Miscellaneous Rational Functions, , Applying Integer Functions, Rational Number Functions +@comment node-name, next, previous, up +@section Miscellaneous Functions + +@deftypefun double mpq_get_d (mpq_t @var{op}) +Convert @var{op} to a double. +@end deftypefun + +These functions assign between either the numerator or denominator of a +rational, and an integer. Instead of using these functions, it is preferable +to use the more general mechanisms @code{mpq_numref} and @code{mpq_denref}, +together with @code{mpz_set}. + +@deftypefun void mpq_set_num (mpq_t @var{rational}, mpz_t @var{numerator}) +Copy @var{numerator} to the numerator of @var{rational}. When this risks to +make the numerator and denominator of @var{rational} have common factors, you +have to pass @var{rational} to @code{mpq_canonicalize} before any operations +are performed on @var{rational}. + +This function is equivalent to +@code{mpz_set (mpq_numref (@var{rational}), @var{numerator})}. +@end deftypefun + +@deftypefun void mpq_set_den (mpq_t @var{rational}, mpz_t @var{denominator}) +Copy @var{denominator} to the denominator of @var{rational}. When this risks +to make the numerator and denominator of @var{rational} have common factors, +or if the denominator might be negative, you have to pass @var{rational} to +@code{mpq_canonicalize} before any operations are performed on @var{rational}. + +@strong{In version 1 of the library, negative denominators were handled by +copying the sign to the numerator. That is no longer done.} + +This function is equivalent to +@code{mpz_set (mpq_denref (@var{rational}), @var{denominators})}. +@end deftypefun + +@deftypefun void mpq_get_num (mpz_t @var{numerator}, mpq_t @var{rational}) +Copy the numerator of @var{rational} to the integer @var{numerator}, to +prepare for integer operations on the numerator. + +This function is equivalent to +@code{mpz_set (@var{numerator}, mpq_numref (@var{rational}))}. +@end deftypefun + +@deftypefun void mpq_get_den (mpz_t @var{denominator}, mpq_t @var{rational}) +Copy the denominator of @var{rational} to the integer @var{denominator}, to +prepare for integer operations on the denominator. + +This function is equivalent to +@code{mpz_set (@var{denominator}, mpq_denref (@var{rational}))}. +@end deftypefun + + +@node Floating-point Functions, Low-level Functions, Rational Number Functions, Top +@comment node-name, next, previous, up +@chapter Floating-point Functions +@cindex Floating-point functions +@cindex Float functions + +This is a description of the @emph{preliminary} interface for floating-point +arithmetic in GNU MP 2. + +The floating-point functions expect arguments of type @code{mpf_t}. + +The MP floating-point functions have an interface that is similar to the MP +integer functions. The function prefix for floating-point operations is +@code{mpf_}. + +There is one significant characteristic of floating-point numbers that has +motivated a difference between this function class and other MP function +classes: the inherent inexactness of floating point arithmetic. The user has +to specify the precision of each variable. A computation that assigns a +variable will take place with the precision of the assigned variable; the +precision of variables used as input is ignored. + +@cindex User-defined precision +The precision of a calculation is defined as follows: Compute the requested +operation exactly (with ``infinite precision''), and truncate the result to +the destination variable precision. Even if the user has asked for a very +high precision, MP will not calculate with superfluous digits. For example, +if two low-precision numbers of nearly equal magnitude are added, the +precision of the result will be limited to what is required to represent the +result accurately. + +The MP floating-point functions are @emph{not} intended as a smooth extension +to the IEEE P754 arithmetic. Specifically, the results obtained on one +computer often differs from the results obtained on a computer with a +different word size. + +@menu +* Initializing Floats:: +* Assigning Floats:: +* Simultaneous Float Init & Assign:: +* Converting Floats:: +* Float Arithmetic:: +* Float Comparison:: +* I/O of Floats:: +* Miscellaneous Float Functions:: +@end menu + +@node Initializing Floats, Assigning Floats, , Floating-point Functions +@comment node-name, next, previous, up +@section Initialization and Assignment Functions + +@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 + +An @code{mpf_t} object must be initialized before storing the first value in +it. The functions @code{mpf_init} and @code{mpf_init2} are used for that +purpose. + +@deftypefun void mpf_init (mpf_t @var{x}) +Initialize @var{x} to 0. Normally, a variable should be initialized once only +or at least be cleared, using @code{mpf_clear}, between initializations. The +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}, 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_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 + +@need 2000 +Here is an example on how to initialize floating-point variables: +@example +@{ + mpf_t x, y; + mpf_init (x); /* use default precision */ + mpf_init2 (y, 256); /* precision @emph{at least} 256 bits */ + @dots{} + /* Unless the program is about to exit, do ... */ + mpf_clear (x); + mpf_clear (y); +@} +@end example + +The following three functions are useful for changing the precision during a +calculation. A typical use would be for adjusting the precision gradually in +iterative algorithms like Newton-Raphson, making the computation precision +closely match the actual accurate part of the numbers. + +@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. +Since changing the precision involves calls to @code{realloc}, this routine +should not be called in a tight loop. +@end deftypefun + +@deftypefun {unsigned long int} mpf_get_prec (mpf_t @var{op}) +Return the precision actually used for assignments of @var{op}. +@end deftypefun + +@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. This +is a low-level function that does not change the allocation. The @var{prec} +argument must not be larger that the precision previously returned by +@code{mpf_get_prec}. It is crucial that the precision of @var{rop} is +ultimately reset to exactly the value returned by @code{mpf_get_prec}. +@end deftypefun + + +@node Assigning Floats, Simultaneous Float Init & Assign, Initializing Floats, Floating-point Functions +@comment node-name, next, previous, up +@subsection Assignment Functions +@cindex Float assignment functions + +These functions assign new values to already initialized floats +(@pxref{Initializing Floats}). + +@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}, 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}, 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 +in the specified base. The exponent is either in the specified base or, if +@var{base} is negative, in decimal. + +The argument @var{base} may be in the ranges 2 to 36, or @minus{}36 to +@minus{}2. Negative values are used to specify that the exponent is in +decimal. + +Unlike the corresponding @code{mpz} function, the base will not be determined +from the leading characters of the string if @var{base} is 0. This is so that +numbers like @samp{0.23} are not interpreted as octal. + +White space is allowed in the string, and is simply ignored. + +This function returns 0 if the entire string up to the '\0' is a valid number +in base @var{base}. Otherwise it returns @minus{}1. +@end deftypefun + + +@node Simultaneous Float Init & Assign, Converting Floats, Assigning Floats, Floating-point Functions +@comment node-name, next, previous, up +@subsection Combined Initialization and Assignment Functions +@cindex Initialization and assignment functions + +For convenience, MP provides a parallel series of initialize-and-set functions +which initialize the output and then store the value there. These functions' +names have the form @code{mpf_init_set@dots{}} + +Once the float has been initialized by any of the @code{mpf_init_set@dots{}} +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}, 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}) +Initialize @var{rop} and set its value from @var{op}. + +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}, 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. + +Note that @var{rop} is initialized even if an error occurs. (I.e., you have to +call @code{mpf_clear} for it.) + +The precision of @var{rop} will be taken from the active default precision, as +set by @code{mpf_set_default_prec}. +@end deftypefun + + +@node Converting Floats, Float Arithmetic, Simultaneous Float Init & Assign, Floating-point Functions +@comment node-name, next, previous, up +@section Conversion Functions +@cindex Conversion functions + +@deftypefun double mpf_get_d (mpf_t @var{op}) +Convert @var{op} to a double. +@end deftypefun + +@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 may vary +from 2 to 36. Generate at most @var{n_digits} significant digits, or if +@var{n_digits} is 0, the maximum number of digits accurately representable by +@var{op}. + +If @var{str} is NULL, space for the mantissa is allocated using the default +allocation function, and a pointer to the string is returned. + +If @var{str} is not NULL, it should point to a block of storage enough large +for the mantissa, i.e., @var{n_digits} + 2. The two extra bytes are for a +possible minus sign, and for the terminating null character. + +The exponent is written through the pointer @var{expptr}. + +If @var{n_digits} is 0, the maximum number of digits meaningfully achievable +from the precision of @var{op} will be generated. Note that the space +requirements for @var{str} in this case will be impossible for the user to +predetermine. Therefore, you need to pass NULL for the string argument +whenever @var{n_digits} is 0. + +The generated string is a fraction, with an implicit radix point immediately +to the left of the first digit. For example, the number 3.1416 would be +returned as "31416" in the string and 1 written at @var{expptr}. +@end deftypefun + + +@node Float Arithmetic, Float Comparison, Converting Floats, Floating-point Functions +@comment node-name, next, previous, up +@section Arithmetic Functions +@cindex Float arithmetic functions +@cindex Arithmetic functions + +@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}) +@ifinfo +Set @var{rop} to @var{op1} + @var{op2}. +@end ifinfo +@iftex +@tex +Set @var{rop} to $@var{op1} + @var{op2}$. +@end tex +@end iftex +@end deftypefun + +@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}, 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}) +@ifinfo +Set @var{rop} to @var{op1} times @var{op2}. +@end ifinfo +@iftex +@tex +Set @var{rop} to $@var{op1} \times @var{op2}$. +@end tex +@end iftex +@end deftypefun + +Division is undefined if the divisor is zero, and passing a zero divisor to +the divide functions will make these functions intentionally divide by zero. +This gives the user the possibility to handle arithmetic exceptions in these +functions in the same manner as other arithmetic exceptions. + +@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}) +Set @var{rop} to @var{op1}/@var{op2}. +@end deftypefun + +@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}) +@ifinfo +Set @var{rop} to the square root of @var{op}. +@end ifinfo +@iftex +@tex +Set @var{rop} to $\sqrt{@var{op}}$. +@end tex +@end iftex +@end deftypefun + +@c @deftypefun void mpf_pow_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2}) +@c Set @var{rop} to @var{op1} raised to @var{op2}. +@c @end deftypefun + +@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}, 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}, mpf_t @var{op1}, unsigned long int @var{op2}) +@ifinfo +Set @var{rop} to @var{op1} times 2 raised to @var{op2}. +@end ifinfo +@iftex +@tex +Set @var{rop} to $@var{op1} \times 2^{op2}$. +@end tex +@end iftex +@end deftypefun + +@deftypefun void mpf_div_2exp (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2}) +@ifinfo +Set @var{rop} to @var{op1} divided by 2 raised to @var{op2}. +@end ifinfo +@iftex +@tex +Set @var{rop} to $@var{op1}/2^{op2}$. +@end tex +@end iftex +@end deftypefun + +@node Float Comparison, I/O of Floats, Float Arithmetic, Floating-point Functions +@comment node-name, next, previous, up +@section Comparison Functions +@cindex Float comparisons functions +@cindex Comparison functions + +@deftypefun int mpf_cmp (mpf_t @var{op1}, mpf_t @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}) +@ifinfo +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 ifinfo +@iftex +@tex +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 tex +@end iftex +@end deftypefun + +@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 of @var{op1} and @var{op2} are +approximately equal. +@end deftypefun + +@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}. +@end deftypefun + +@deftypefn Macro int mpf_sgn (mpf_t @var{op}) +@ifinfo +Return +1 if @var{op} > 0, 0 if @var{op} = 0, and @minus{}1 if @var{op} < 0. +@end ifinfo +@iftex +@tex +Return $+1$ if $@var{op} > 0$, 0 if $@var{op} = 0$, and $-1$ if $@var{op} < 0$. +@end tex +@end iftex + +This function is actually implemented as a macro. It evaluates its +arguments multiple times. +@end deftypefn + +@node I/O of Floats, Miscellaneous Float Functions, Float Comparison, Floating-point Functions +@comment node-name, next, previous, up +@section Input and Output Functions +@cindex Float input and output functions +@cindex Input functions +@cindex Output functions +@cindex I/O functions + +Functions that perform input from a stdio stream, and functions that output to +a stdio stream. Passing a 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. + +@deftypefun size_t mpf_out_str (FILE *@var{stream}, int @var{base}, size_t @var{n_digits}, mpf_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. Print at most +@var{n_digits} significant digits, or if @var{n_digits} is 0, the maximum +number of digits accurately representable by @var{op}. + +In addition to the significant digits, a leading @samp{0.} and a +trailing exponent, in the form @samp{eNNN}, are printed. If @var{base} +is greater than 10, @samp{@@} will be used instead of @samp{e} as +exponent delimiter. + +Return the number of bytes written, or if an error occurred, return 0. +@end deftypefun + +@deftypefun size_t mpf_inp_str (mpf_t @var{rop}, FILE *@var{stream}, int @var{base}) +Input a string in base @var{base} from stdio stream @var{stream}, and put the +read float in @var{rop}. 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 in the specified base. The +exponent is either in the specified base or, if @var{base} is negative, in +decimal. + +The argument @var{base} may be in the ranges 2 to 36, or @minus{}36 to +@minus{}2. Negative values are used to specify that the exponent is in +decimal. + +Unlike the corresponding @code{mpz} function, the base will not be determined +from the leading characters of the string if @var{base} is 0. This is so that +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}, 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 +@c limbs are written in decreasing significance order. +@c @end deftypefun + +@c @deftypefun void mpf_inp_raw (mpf_t @var{float}, FILE *@var{stream}) +@c Input from stdio stream @var{stream} in the format written by +@c @code{mpf_out_raw}, and put the result in @var{float}. +@c @end deftypefun + + +@node Miscellaneous Float Functions, , I/O of Floats, Floating-point Functions +@comment node-name, next, previous, up +@section Miscellaneous Functions +@cindex Miscellaneous float functions + +@deftypefun void mpf_random2 (mpf_t @var{rop}, mp_size_t @var{max_size}, mp_exp_t @var{max_exp}) +Generate a random float of at most @var{max_size} limbs, with long strings of +zeros and ones in the binary representation. The exponent of the number is in +the interval @minus{}@var{exp} to @var{exp}. This function is useful for +testing functions and algorithms, since this kind of random numbers have +proven to be more likely to trigger corner-case bugs. Negative random numbers +are generated when @var{max_size} is negative. +@end deftypefun + +@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}.) +@c +@c @strong{This function is obsolete. It will disappear from future MP +@c releases.} +@c @end deftypefun + +@node Low-level Functions, BSD Compatible Functions, Floating-point Functions, Top +@comment node-name, next, previous, up +@chapter Low-level Functions +@cindex Low-level functions + +This chapter describes low-level MP functions, used to implement the high-level +MP functions, but also intended for time-critical user code. + +These functions start with the prefix @code{mpn_}. + +@c 1. Some of these function clobber input operands. +@c + +The @code{mpn} functions are designed to be as fast as possible, @strong{not} +to provide a coherent calling interface. The different functions have somewhat +similar interfaces, but there are variations that make them hard to use. These +functions do as little as possible apart from the real multiple precision +computation, so that no time is spent on things that not all callers need. + +A source operand is specified by a pointer to the least significant limb and a +limb count. A destination operand is specified by just a pointer. It is the +responsibility of the caller to ensure that the destination has enough space +for storing the result. + +With this way of specifying operands, it is possible to perform computations +on subranges of an argument, and store the result into a subrange of a +destination. + +A common requirement for all functions is that each source area needs at least +one limb. No size argument may be zero. + +The @code{mpn} functions is the base for the implementation of the @code{mpz_}, +@code{mpf_}, and @code{mpq_} functions. + +This example adds the number beginning at @var{src1_ptr} and the number +beginning at @var{src2_ptr} and writes the sum at @var{dest_ptr}. All areas +have @var{size} limbs. + +@example +cy = mpn_add_n (dest_ptr, src1_ptr, src2_ptr, size) +@end example + +@noindent +In the notation used here, a source operand is identified by the pointer to +the least significant limb, and the limb count in braces. For example, +@{s1_ptr, s1_size@}. + +@deftypefun mp_limb_t mpn_add_n (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{size}) +Add @{@var{src1_ptr}, @var{size}@} and @{@var{src2_ptr}, @var{size}@}, and +write the @var{size} least significant limbs of the result to @var{dest_ptr}. +Return carry, either 0 or 1. + +This is the lowest-level function for addition. It is the preferred function +for addition, since it is written in assembly for most targets. For addition +of a variable to itself (i.e., @var{src1_ptr} equals @var{src2_ptr}, use +@code{mpn_lshift} with a count of 1 for optimal speed. +@end deftypefun + +@deftypefun mp_limb_t mpn_add_1 (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{size}, mp_limb_t @var{src2_limb}) +Add @{@var{src1_ptr}, @var{size}@} and @var{src2_limb}, and write the +@var{size} least significant limbs of the result to @var{dest_ptr}. Return +carry, either 0 or 1. +@end deftypefun + +@deftypefun mp_limb_t mpn_add (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{src1_size}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{src2_size}) +Add @{@var{src1_ptr}, @var{src1_size}@} and @{@var{src2_ptr}, +@var{src2_size}@}, and write the @var{src1_size} least significant limbs of +the result to @var{dest_ptr}. Return carry, either 0 or 1. + +This function requires that @var{src1_size} is greater than or equal to +@var{src2_size}. +@end deftypefun + +@deftypefun mp_limb_t mpn_sub_n (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{size}) +Subtract @{@var{src2_ptr}, @var{src2_size}@} from @{@var{src1_ptr}, +@var{size}@}, and write the @var{size} least significant limbs of the result +to @var{dest_ptr}. Return borrow, either 0 or 1. + +This is the lowest-level function for subtraction. It is the preferred +function for subtraction, since it is written in assembly for most targets. +@end deftypefun + +@deftypefun mp_limb_t mpn_sub_1 (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{size}, mp_limb_t @var{src2_limb}) +Subtract @var{src2_limb} from @{@var{src1_ptr}, @var{size}@}, and write the +@var{size} least significant limbs of the result to @var{dest_ptr}. Return +borrow, either 0 or 1. +@end deftypefun + +@deftypefun mp_limb_t mpn_sub (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{src1_size}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{src2_size}) +Subtract @{@var{src2_ptr}, @var{src2_size}@} from @{@var{src1_ptr}, +@var{src1_size}@}, and write the @var{src1_size} least significant limbs of +the result to @var{dest_ptr}. Return borrow, either 0 or 1. + +This function requires that @var{src1_size} is greater than or equal to +@var{src2_size}. +@end deftypefun + +@deftypefun void mpn_mul_n (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{size}) +Multiply @{@var{src1_ptr}, @var{size}@} and @{@var{src2_ptr}, @var{size}@}, +and write the @strong{entire} result to @var{dest_ptr}. + +The destination has to have space for 2@var{size} limbs, even if the +significant result might be one limb smaller. +@end deftypefun + +@deftypefun mp_limb_t mpn_mul_1 (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{size}, mp_limb_t @var{src2_limb}) +Multiply @{@var{src1_ptr}, @var{size}@} and @var{src2_limb}, and write the +@var{size} least significant limbs of the product to @var{dest_ptr}. Return +the most significant limb of the product. + +This is a low-level function that is a building block for general +multiplication as well as other operations in MP. It is written in assembly +for most targets. + +Don't call this function if @var{src2_limb} is a power of 2; use +@code{mpn_lshift} with a count equal to the logarithm of @var{src2_limb} +instead, for optimal speed. +@end deftypefun + +@deftypefun mp_limb_t mpn_addmul_1 (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{size}, mp_limb_t @var{src2_limb}) +Multiply @{@var{src1_ptr}, @var{size}@} and @var{src2_limb}, and add the +@var{size} least significant limbs of the product to @{@var{dest_ptr}, +@var{size}@} and write the result to @var{dest_ptr} @var{dest_ptr}. Return +the most significant limb of the product, plus carry-out from the addition. + +This is a low-level function that is a building block for general +multiplication as well as other operations in MP. It is written in assembly +for most targets. +@end deftypefun + +@deftypefun mp_limb_t mpn_submul_1 (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{size}, mp_limb_t @var{src2_limb}) +Multiply @{@var{src1_ptr}, @var{size}@} and @var{src2_limb}, and subtract the +@var{size} least significant limbs of the product from @{@var{dest_ptr}, +@var{size}@} and write the result to @var{dest_ptr}. Return the most +significant limb of the product, minus borrow-out from the subtraction. + +This is a low-level function that is a building block for general +multiplication and division as well as other operations in MP. It is written +in assembly for most targets. +@end deftypefun + +@deftypefun mp_limb_t mpn_mul (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{src1_size}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{src2_size}) +Multiply @{@var{src1_ptr}, @var{src1_size}@} and @{@var{src2_ptr}, +@var{src2_size}@}, and write the result to @var{dest_ptr}. Return the most +significant limb of the result. + +The destination has to have space for @var{src1_size} + @var{src1_size} +limbs, even if the result might be one limb smaller. + +This function requires that @var{src1_size} is greater than or equal to +@var{src2_size}. The destination must be distinct from either input operands. +@end deftypefun + +@deftypefun mp_size_t mpn_divrem (mp_limb_t * @var{r1p}, mp_size_t @var{xsize}, mp_limb_t * @var{rs2p}, mp_size_t @var{rs2size}, const mp_limb_t * @var{s3p}, mp_size_t @var{s3size}) +Divide @{@var{rs2p}, @var{rs2size}@} by @{@var{s3p}, @var{s3size}@}, and +write the quotient at @var{r1p}, with the exception of the most significant +limb, which is returned. The remainder replaces the dividend at @var{rs2p}. + +In addition to an integer quotient, @var{xsize} fraction limbs are developed, +and stored after the integral limbs. For most usages, @var{xsize} will be +zero. + +It is required that @var{rs2size} is greater than or equal to @var{s3size}. +It is required that the most significant bit of the divisor is set. + +If the quotient is not needed, pass @var{rs2p} + @var{s3size} as @var{r1p}. +Aside from that special case, no overlap between arguments is permitted. + +Return the most significant limb of the quotient, either 0 or 1. + +The area at @var{r1p} needs to be @var{rs2size} @minus{} @var{s3size} + +@var{xsize} limbs large. +@end deftypefun + +@deftypefun mp_limb_t mpn_divrem_1 (mp_limb_t * @var{r1p}, mp_size_t @var{xsize}, mp_limb_t * @var{s2p}, mp_size_t @var{s2size}, mp_limb_t @var{s3limb}) +Divide @{@var{s2p}, @var{s2size}@} by @var{s3limb}, and write the quotient +at @var{r1p}. Return the remainder. + +In addition to an integer quotient, @var{xsize} fraction limbs are developed, +and stored after the integral limbs. For most usages, @var{xsize} will be +zero. + +The areas at @var{r1p} and @var{s2p} have to be identical or completely +separate, not partially overlapping. +@end deftypefun + +@deftypefun mp_size_t mpn_divmod (mp_limb_t * @var{r1p}, mp_limb_t * @var{rs2p}, mp_size_t @var{rs2size}, const mp_limb_t * @var{s3p}, mp_size_t @var{s3size}) +@strong{This interface is obsolete. It will disappear from future releases. +Use @code{mpn_divrem} in its stead.} +@end deftypefun + +@deftypefun mp_limb_t mpn_divmod_1 (mp_limb_t * @var{r1p}, mp_limb_t * @var{s2p}, mp_size_t @var{s2size}, mp_limb_t @var{s3limb}) +@strong{This interface is obsolete. It will disappear from future releases. +Use @code{mpn_divrem_1} in its stead.} +@end deftypefun + +@deftypefun mp_limb_t mpn_mod_1 (mp_limb_t * @var{s1p}, mp_size_t @var{s1size}, mp_limb_t @var{s2limb}) +Divide @{@var{s1p}, @var{s1size}@} by @var{s2limb}, and return the remainder. +@end deftypefun + +@deftypefun mp_limb_t mpn_preinv_mod_1 (mp_limb_t * @var{s1p}, mp_size_t @var{s1size}, mp_limb_t @var{s2limb}, mp_limb_t @var{s3limb}) +@strong{This interface is obsolete. It will disappear from future releases. +Use @code{mpn_mod_1} in its stead.} +@end deftypefun + +@deftypefun mp_limb_t mpn_bdivmod (mp_limb_t * @var{dest_ptr}, mp_limb_t * @var{s1p}, mp_size_t @var{s1size}, const mp_limb_t * @var{s2p}, mp_size_t @var{s2size}, unsigned long int @var{d}) +The function puts the low [@var{d}/@var{BITS_PER_MP_LIMB}] limbs of +@var{q} = +@{@var{s1p}, @var{s1size}@}/@{@var{s2p}, @var{s2size}@} +mod 2^@var{d} +at @var{dest_ptr}, +and returns the high @var{d} mod @var{BITS_PER_MP_LIMB} bits of @var{q}. + +@{@var{s1p}, @var{s1size}@} - @var{q} * @{@var{s2p}, @var{s2size}@} +mod 2^(@var{s1size}*@var{BITS_PER_MP_LIMB}) +is placed at @var{s1p}. +Since the low [@var{d}/@var{BITS_PER_MP_LIMB}] limbs of +this difference are zero, it is possible to overwrite the low limbs at +@var{s1p} with this difference, +provided @var{dest_ptr} <= @var{s1p}. + +This function requires that @var{s1size} * @var{BITS_PER_MP_LIMB} >= @var{D}, +and that @{@var{s2p}, @var{s2size}@} 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{dest_ptr}, const mp_limb_t * @var{src_ptr}, mp_size_t @var{src_size}, unsigned long int @var{count}) +Shift @{@var{src_ptr}, @var{src_size}@} @var{count} bits to the left, and +write the @var{src_size} least significant limbs of the result to +@var{dest_ptr}. @var{count} might be in the range 1 to n @minus{} 1, on an +n-bit machine. The bits shifted out to the left are returned. + +Overlapping of the destination space and the source space is allowed in this +function, provided @var{dest_ptr} >= @var{src_ptr}. + +This function is written in assembly for most targets. +@end deftypefun + +@deftypefun mp_limp_t mpn_rshift (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src_ptr}, mp_size_t @var{src_size}, unsigned long int @var{count}) +Shift @{@var{src_ptr}, @var{src_size}@} @var{count} bits to the right, and +write the @var{src_size} most significant limbs of the result to +@var{dest_ptr}. @var{count} might be in the range 1 to n @minus{} 1, on an +n-bit machine. The bits shifted out to the right are returned. + +Overlapping of the destination space and the source space is allowed in this +function, provided @var{dest_ptr} <= @var{src_ptr}. + +This function is written in assembly for most targets. +@end deftypefun + +@deftypefun int mpn_cmp (const mp_limb_t * @var{src1_ptr}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{size}) +Compare @{@var{src1_ptr}, @var{size}@} and @{@var{src2_ptr}, @var{size}@} and +return a positive value if src1 > src2, 0 of they are equal, and a negative +value if src1 < src2. +@end deftypefun + +@deftypefun mp_size_t mpn_gcd (mp_limb_t * @var{dest_ptr}, mp_limb_t * @var{src1_ptr}, mp_size_t @var{src1_size}, mp_limb_t * @var{src2_ptr}, mp_size_t @var{src2_size}) +Puts at @var{dest_ptr} the greatest common divisor of @{@var{src1_ptr}, +@var{src1_size}@} and @{@var{src2_ptr}, @var{src2_size}@}; both source +operands are destroyed by the operation. The size in limbs of the greatest +common divisor is returned. + +@{@var{src1_ptr}, @var{src1_size}@} must be odd, and @{@var{src2_ptr}, +@var{src2_size}@} must have at least as many bits as @{@var{src1_ptr}, +@var{src1_size}@}. + +@strong{This interface is preliminary. It might change incompatibly in +future revisions.} +@end deftypefun + +@deftypefun mp_limb_t mpn_gcd_1 (const mp_limb_t * @var{src1_ptr}, mp_size_t @var{src1_size}, mp_limb_t @var{src2_limb}) +Return the greatest common divisor of @{@var{src1_ptr}, @var{src1_size}@} +and @var{src2_limb}, where @var{src2_limb} (as well as @var{src1_size}) +must be different from 0. +@end deftypefun + +@deftypefun mp_size_t mpn_gcdext (mp_limb_t * @var{r1p}, mp_limb_t * @var{r2p}, mp_limb_t * @var{s1p}, mp_size_t @var{s1size}, mp_limb_t * @var{s2p}, mp_size_t @var{s2size}) +Puts at @var{r1p} the greatest common divisor of @{@var{s1p}, @var{s1size}@} +and @{@var{s2p}, @var{s2size}@}. The first cofactor is written at +@var{r2p}. Both source operands are destroyed by the operation. The size +in limbs of the greatest common divisor is returned. + +@strong{This interface is preliminary. It might change incompatibly in +future revisions.} +@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{size}) +Compute the square root of @{@var{sp}, @var{size}@} and put the result at +@var{r1p}. Write the remainder at @var{r2p}, unless @var{r2p} is NULL. + +Return the size of the remainder, whether @var{r2p} was NULL or non-NULL. +Iff the operand was a perfect square, the return value will be 0. + +The areas at @var{r1p} and @var{sp} have to be distinct. The areas at +@var{r2p} and @var{sp} have to be identical or completely separate, not +partially overlapping. + +@ifinfo +The area at @var{r1p} needs to have space for ceil(@var{size}/2) limbs. +@end ifinfo +@iftex +@tex +The area at @var{r1p} needs to have space for $\lceil@var{size}/2\rceil$ limbs. +@end tex +@end iftex +The area at @var{r2p} needs to be @var{size} limbs large. + +@strong{This interface is preliminary. It might change incompatibly in +future revisions.} +@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{s1size}) +Convert @{@var{s1p}, @var{s1size}@} to a raw unsigned char array in base +@var{base}. The string is not in ASCII; to convert it to printable format, +add the ASCII codes for @samp{0} or @samp{A}, depending on the base and +range. There may be leading zeros in the string. + +The area at @var{s1p} is clobbered. + +Return the number of characters in @var{str}. + +The area at @var{str} has to have space for the largest possible number +represented by a @var{s1size} long limb array, plus one extra character. +@end deftypefun + +@deftypefun mp_size_t mpn_set_str (mp_limb_t * @var{r1p}, const char *@var{str}, size_t {strsize}, int @var{base}) +Convert the raw unsigned char array at @var{str} of length @var{strsize} to +a limb array @{@var{s1p}, @var{s1size}@}. The base of @var{str} is +@var{base}. + +Return the number of limbs stored in @var{r1p}. +@end deftypefun + +@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. + +@strong{This interface is preliminary. It might change incompatibly in +future revisions.} +@end deftypefun + +@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 +beyond bit position @var{bit}, so that the function has something to return. + +@strong{This interface is preliminary. It might change incompatibly in +future revisions.} +@end deftypefun + +@deftypefun void mpn_random2 (mp_limb_t * @var{r1p}, mp_size_t @var{r1size}) +Generate a random number of length @var{r1size} with long strings of zeros +and ones in the binary representation, and store it at @var{r1p}. + +The generated random numbers are intended for testing the correctness of the +implementation of the @code{mpn} routines. +@end deftypefun + +@deftypefun {unsigned long int} mpn_popcount (const mp_limb_t * @var{s1p}, unsigned long int @var{size}) +Count the number of set bits in @{@var{s1p}, @var{size}@}. +@end deftypefun + +@deftypefun {unsigned long int} mpn_hamdist (const mp_limb_t * @var{s1p}, const mp_limb_t * @var{s2p}, unsigned long int @var{size}) +Compute the hamming distance between @{@var{s1p}, @var{size}@} and +@{@var{s2p}, @var{size}@}. +@end deftypefun + +@deftypefun int mpn_perfect_square_p (const mp_limb_t * @var{s1p}, mp_size_t @var{size}) +Return non-zero iff @{@var{s1p}, @var{size}@} is a perfect square. +@end deftypefun + + +@node BSD Compatible Functions, Custom Allocation, Low-level Functions, Top +@comment node-name, next, previous, up +@chapter Berkeley MP Compatible Functions +@cindex BSD MP compatible functions + +These functions are intended to be fully compatible with the Berkeley MP +library which is available on many BSD derived U*ix systems. + +The original Berkeley MP library has a usage restriction: you cannot use the +same variable as both source and destination in a single function call. The +compatible functions in GNU MP do not share this restriction---inputs and +outputs may overlap. + +It is not recommended that new programs are written using these functions. +Apart from the incomplete set of functions, the interface for initializing +@code{MINT} objects is more error prone, and the @code{pow} function collides +with @code{pow} in @file{libm.a}. + +@cindex @file{mp.h} +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 you program. +This means that you probably need to give the -I<dir> option to the compiler, +where <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, '\0'-terminate +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{operand}, MINT *@var{root}, MINT *@var{remainder}) +@ifinfo +Set @var{root} to the truncated integer part of the square root of +@var{operand}. Set @var{remainder} to +@var{operand}@minus{}@var{root}*@var{root}, +@end ifinfo +@iftex +@tex +Set @var{root} to $\lfloor\sqrt{@var{operand}}\rfloor$, like +@code{mpz_sqrt}. Set @var{remainder} to $(operand - root^2)$, +@end tex +@end iftex +(i.e., zero if @var{operand} 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}. +@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{operand1}, MINT *@var{operand2}, MINT *@var{res}) +Set @var{res} to the greatest common divisor of @var{operand1} and +@var{operand2}. +@end deftypefun + +@deftypefun int mcmp (MINT *@var{operand1}, MINT *@var{operand2}) +Compare @var{operand1} and @var{operand2}. Return a positive value if +@var{operand1} > @var{operand2}, zero if @var{operand1} = +@var{operand2}, and a negative value if @var{operand1} < @var{operand2}. +@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{operand}) +Convert @var{operand} 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. +@end deftypefun + +@deftypefun void mfree (MINT *@var{operand}) +De-allocate, the space used by @var{operand}. @strong{This function should +only be passed a value returned by @code{itom} or @code{xtom}.} +@end deftypefun + +@node Custom Allocation, Contributors, BSD Compatible Functions, Top +@comment node-name, next, previous, up +@chapter Custom Allocation + +By default, the MP functions use @code{malloc}, @code{realloc}, and +@code{free} for memory allocation. If @code{malloc} or @code{realloc} fails, +the MP library terminates execution after printing a fatal error message to +standard error. + +For some applications, you may wish to allocate memory in other ways, or you +may not want to have a fatal error when there is no more memory available. To +accomplish this, you can specify alternative memory allocation functions. + +@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 NULL, the corresponding default function is retained. + +@strong{Make sure to call this function in such a way that there are no active +MP objects that were allocated using the previously active allocation +function! Usually, that means that you have to call this function before any +other MP function.} +@end deftypefun + +The functions you supply should fit the following declarations: + +@deftypefun {void *} allocate_function (size_t @var{alloc_size}) +This function should return a pointer to newly allocated space with at least +@var{alloc_size} storage units. +@end deftypefun + +@deftypefun {void *} reallocate_function (void *@var{ptr}, size_t @var{old_size}, size_t @var{new_size}) +This function should return a pointer to newly allocated space of at least +@var{new_size} storage units, after copying at least the first @var{old_size} +storage units from @var{ptr}. It should also de-allocate the space at +@var{ptr}. + +You can assume that the space at @var{ptr} was formerly returned from +@code{allocate_function} or @code{reallocate_function}, for a request for +@var{old_size} storage units. +@end deftypefun + +@deftypefun void deallocate_function (void *@var{ptr}, size_t @var{size}) +De-allocate the space pointed to by @var{ptr}. + +You can assume that the space at @var{ptr} was formerly returned from +@code{allocate_function} or @code{reallocate_function}, for a request for +@var{size} storage units. +@end deftypefun + +(A @dfn{storage unit} is the unit in which the @code{sizeof} operator returns +the size of an object, normally an 8 bit byte.) + + +@node Contributors, References, Custom Allocation, Top +@comment node-name, next, previous, up +@unnumbered Contributors + +I would like to thank Gunnar Sjoedin and Hans Riesel for their help with +mathematical problems, Richard Stallman for his help with design issues and +for revising the first version of this manual, Brian Beuning and Doug Lea for +their testing of early versions of the library. + +John Amanatides of York University in Canada contributed the function +@code{mpz_probab_prime_p}. + +Paul Zimmermann of Inria sparked the development of GMP 2, with his +comparisons between bignum packages. + +Ken Weber (Kent State University, Universidade Federal do Rio Grande do Sul) +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 MP to use Cygnus' configure. +He has also made valuable suggestions and tested numerous intermediary +releases. + +Joachim Hollman was involved in the design of the @code{mpf} interface, and in +the @code{mpz} design revisions for version 2. + +Bennet Yee contributed the functions @code{mpz_jacobi} and +@code{mpz_legendre}. + +Andreas Schwab contributed the files @file{mpn/m68k/lshift.S} and +@file{mpn/m68k/rshift.S}. + +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). + +GNU MP 2 was finished and released by TMG Datakonsult, Sodermannagatan 5, 116 +23 STOCKHOLM, SWEDEN, in cooperation with the IDA Center for Computing +Sciences, USA. + + +@node References, , Contributors, Top +@comment node-name, next, previous, up +@unnumbered References + +@itemize @bullet + +@item +Donald E. Knuth, "The Art of Computer Programming", vol 2, +"Seminumerical Algorithms", 2nd edition, Addison-Wesley, 1981. + +@item +John D. Lipson, "Elements of Algebra and Algebraic Computing", +The Benjamin Cummings Publishing Company Inc, 1981. + +@item +Richard M. Stallman, "Using and Porting GCC", Free Software Foundation, +1995. + +@item +Peter L. Montgomery, "Modular Multiplication Without Trial Division", in +Mathematics of Computation, volume 44, number 170, April 1985. + +@item +Torbjorn Granlund and Peter L. Montgomery, "Division by Invariant +Integers using Multiplication", in Proceedings of the SIGPLAN +PLDI'94 Conference, June 1994. + +@item +Tudor Jebelean, +"An algorithm for exact division", +Journal of Symbolic Computation, +v. 15, 1993, pp. 169-180. + +@item +Kenneth Weber, "The accelerated integer GCD algorithm", +ACM Transactions on Mathematical Software, +v. 21 (March), 1995, pp. 111-122. +@end itemize + +@node Concept Index, , , Top +@comment node-name, next, previous, up +@unnumbered Concept Index +@printindex cp + +@node Function Index, , , Top +@comment node-name, next, previous, up +@unnumbered Function and Type Index +@printindex fn + + +@contents +@bye |