Merge branch 'master' into divVerent/crypto2
[xonotic/xonotic.git] / misc / builddeps / dp.linux32 / share / info / gmp.info-1
1 This is ../../gmp/doc/gmp.info, produced by makeinfo version 4.8 from
2 ../../gmp/doc/gmp.texi.
3
4    This manual describes how to install and use the GNU multiple
5 precision arithmetic library, version 5.0.1.
6
7    Copyright 1991, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
8 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 Free
9 Software Foundation, Inc.
10
11    Permission is granted to copy, distribute and/or modify this
12 document under the terms of the GNU Free Documentation License, Version
13 1.3 or any later version published by the Free Software Foundation;
14 with no Invariant Sections, with the Front-Cover Texts being "A GNU
15 Manual", and with the Back-Cover Texts being "You have freedom to copy
16 and modify this GNU Manual, like GNU software".  A copy of the license
17 is included in *Note GNU Free Documentation License::.
18
19 INFO-DIR-SECTION GNU libraries
20 START-INFO-DIR-ENTRY
21 * gmp: (gmp).                   GNU Multiple Precision Arithmetic Library.
22 END-INFO-DIR-ENTRY
23
24 \1f
25 File: gmp.info,  Node: Top,  Next: Copying,  Prev: (dir),  Up: (dir)
26
27 GNU MP
28 ******
29
30    This manual describes how to install and use the GNU multiple
31 precision arithmetic library, version 5.0.1.
32
33    Copyright 1991, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
34 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 Free
35 Software Foundation, Inc.
36
37    Permission is granted to copy, distribute and/or modify this
38 document under the terms of the GNU Free Documentation License, Version
39 1.3 or any later version published by the Free Software Foundation;
40 with no Invariant Sections, with the Front-Cover Texts being "A GNU
41 Manual", and with the Back-Cover Texts being "You have freedom to copy
42 and modify this GNU Manual, like GNU software".  A copy of the license
43 is included in *Note GNU Free Documentation License::.
44
45
46 * Menu:
47
48 * Copying::                    GMP Copying Conditions (LGPL).
49 * Introduction to GMP::        Brief introduction to GNU MP.
50 * Installing GMP::             How to configure and compile the GMP library.
51 * GMP Basics::                 What every GMP user should know.
52 * Reporting Bugs::             How to usefully report bugs.
53 * Integer Functions::          Functions for arithmetic on signed integers.
54 * Rational Number Functions::  Functions for arithmetic on rational numbers.
55 * Floating-point Functions::   Functions for arithmetic on floats.
56 * Low-level Functions::        Fast functions for natural numbers.
57 * Random Number Functions::    Functions for generating random numbers.
58 * Formatted Output::           `printf' style output.
59 * Formatted Input::            `scanf' style input.
60 * C++ Class Interface::        Class wrappers around GMP types.
61 * BSD Compatible Functions::   All functions found in BSD MP.
62 * Custom Allocation::          How to customize the internal allocation.
63 * Language Bindings::          Using GMP from other languages.
64 * Algorithms::                 What happens behind the scenes.
65 * Internals::                  How values are represented behind the scenes.
66
67 * Contributors::               Who brings you this library?
68 * References::                 Some useful papers and books to read.
69 * GNU Free Documentation License::
70 * Concept Index::
71 * Function Index::
72
73 \1f
74 File: gmp.info,  Node: Copying,  Next: Introduction to GMP,  Prev: Top,  Up: Top
75
76 GNU MP Copying Conditions
77 *************************
78
79 This library is "free"; this means that everyone is free to use it and
80 free to redistribute it on a free basis.  The library is not in the
81 public domain; it is copyrighted and there are restrictions on its
82 distribution, but these restrictions are designed to permit everything
83 that a good cooperating citizen would want to do.  What is not allowed
84 is to try to prevent others from further sharing any version of this
85 library that they might get from you.
86
87    Specifically, we want to make sure that you have the right to give
88 away copies of the library, that you receive source code or else can
89 get it if you want it, that you can change this library or use pieces
90 of it in new free programs, and that you know you can do these things.
91
92    To make sure that everyone has such rights, we have to forbid you to
93 deprive anyone else of these rights.  For example, if you distribute
94 copies of the GNU MP library, you must give the recipients all the
95 rights that you have.  You must make sure that they, too, receive or
96 can get the source code.  And you must tell them their rights.
97
98    Also, for our own protection, we must make certain that everyone
99 finds out that there is no warranty for the GNU MP library.  If it is
100 modified by someone else and passed on, we want their recipients to
101 know that what they have is not what we distributed, so that any
102 problems introduced by others will not reflect on our reputation.
103
104    The precise conditions of the license for the GNU MP library are
105 found in the Lesser General Public License version 3 that accompanies
106 the source code, see `COPYING.LIB'.  Certain demonstration programs are
107 provided under the terms of the plain General Public License version 3,
108 see `COPYING'.
109
110 \1f
111 File: gmp.info,  Node: Introduction to GMP,  Next: Installing GMP,  Prev: Copying,  Up: Top
112
113 1 Introduction to GNU MP
114 ************************
115
116 GNU MP is a portable library written in C for arbitrary precision
117 arithmetic on integers, rational numbers, and floating-point numbers.
118 It aims to provide the fastest possible arithmetic for all applications
119 that need higher precision than is directly supported by the basic C
120 types.
121
122    Many applications use just a few hundred bits of precision; but some
123 applications may need thousands or even millions of bits.  GMP is
124 designed to give good performance for both, by choosing algorithms
125 based on the sizes of the operands, and by carefully keeping the
126 overhead at a minimum.
127
128    The speed of GMP is achieved by using fullwords as the basic
129 arithmetic type, by using sophisticated algorithms, by including
130 carefully optimized assembly code for the most common inner loops for
131 many different CPUs, and by a general emphasis on speed (as opposed to
132 simplicity or elegance).
133
134    There is assembly code for these CPUs: ARM, DEC Alpha 21064, 21164,
135 and 21264, AMD 29000, AMD K6, K6-2, Athlon, and Athlon64, Hitachi
136 SuperH and SH-2, HPPA 1.0, 1.1 and 2.0, Intel Pentium, Pentium
137 Pro/II/III, Pentium 4, generic x86, Intel IA-64, i960, Motorola
138 MC68000, MC68020, MC88100, and MC88110, Motorola/IBM PowerPC 32 and 64,
139 National NS32000, IBM POWER, MIPS R3000, R4000, SPARCv7, SuperSPARC,
140 generic SPARCv8, UltraSPARC, DEC VAX, and Zilog Z8000.  Some
141 optimizations also for Cray vector systems, Clipper, IBM ROMP (RT), and
142 Pyramid AP/XP.
143
144 For up-to-date information on GMP, please see the GMP web pages at
145
146      `http://gmplib.org/'
147
148 The latest version of the library is available at
149
150      `ftp://ftp.gnu.org/gnu/gmp/'
151
152    Many sites around the world mirror `ftp.gnu.org', please use a mirror
153 near you, see `http://www.gnu.org/order/ftp.html' for a full list.
154
155    There are three public mailing lists of interest.  One for release
156 announcements, one for general questions and discussions about usage of
157 the GMP library and one for bug reports.  For more information, see
158
159      `http://gmplib.org/mailman/listinfo/'.
160
161    The proper place for bug reports is <gmp-bugs@gmplib.org>.  See
162 *Note Reporting Bugs:: for information about reporting bugs.
163
164
165 1.1 How to use this Manual
166 ==========================
167
168 Everyone should read *Note GMP Basics::.  If you need to install the
169 library yourself, then read *Note Installing GMP::.  If you have a
170 system with multiple ABIs, then read *Note ABI and ISA::, for the
171 compiler options that must be used on applications.
172
173    The rest of the manual can be used for later reference, although it
174 is probably a good idea to glance through it.
175
176 \1f
177 File: gmp.info,  Node: Installing GMP,  Next: GMP Basics,  Prev: Introduction to GMP,  Up: Top
178
179 2 Installing GMP
180 ****************
181
182 GMP has an autoconf/automake/libtool based configuration system.  On a
183 Unix-like system a basic build can be done with
184
185      ./configure
186      make
187
188 Some self-tests can be run with
189
190      make check
191
192 And you can install (under `/usr/local' by default) with
193
194      make install
195
196    If you experience problems, please report them to
197 <gmp-bugs@gmplib.org>.  See *Note Reporting Bugs::, for information on
198 what to include in useful bug reports.
199
200 * Menu:
201
202 * Build Options::
203 * ABI and ISA::
204 * Notes for Package Builds::
205 * Notes for Particular Systems::
206 * Known Build Problems::
207 * Performance optimization::
208
209 \1f
210 File: gmp.info,  Node: Build Options,  Next: ABI and ISA,  Prev: Installing GMP,  Up: Installing GMP
211
212 2.1 Build Options
213 =================
214
215 All the usual autoconf configure options are available, run `./configure
216 --help' for a summary.  The file `INSTALL.autoconf' has some generic
217 installation information too.
218
219 Tools
220      `configure' requires various Unix-like tools.  See *Note Notes for
221      Particular Systems::, for some options on non-Unix systems.
222
223      It might be possible to build without the help of `configure',
224      certainly all the code is there, but unfortunately you'll be on
225      your own.
226
227 Build Directory
228      To compile in a separate build directory, `cd' to that directory,
229      and prefix the configure command with the path to the GMP source
230      directory.  For example
231
232           cd /my/build/dir
233           /my/sources/gmp-5.0.1/configure
234
235      Not all `make' programs have the necessary features (`VPATH') to
236      support this.  In particular, SunOS and Slowaris `make' have bugs
237      that make them unable to build in a separate directory.  Use GNU
238      `make' instead.
239
240 `--prefix' and `--exec-prefix'
241      The `--prefix' option can be used in the normal way to direct GMP
242      to install under a particular tree.  The default is `/usr/local'.
243
244      `--exec-prefix' can be used to direct architecture-dependent files
245      like `libgmp.a' to a different location.  This can be used to share
246      architecture-independent parts like the documentation, but
247      separate the dependent parts.  Note however that `gmp.h' and
248      `mp.h' are architecture-dependent since they encode certain
249      aspects of `libgmp', so it will be necessary to ensure both
250      `$prefix/include' and `$exec_prefix/include' are available to the
251      compiler.
252
253 `--disable-shared', `--disable-static'
254      By default both shared and static libraries are built (where
255      possible), but one or other can be disabled.  Shared libraries
256      result in smaller executables and permit code sharing between
257      separate running processes, but on some CPUs are slightly slower,
258      having a small cost on each function call.
259
260 Native Compilation, `--build=CPU-VENDOR-OS'
261      For normal native compilation, the system can be specified with
262      `--build'.  By default `./configure' uses the output from running
263      `./config.guess'.  On some systems `./config.guess' can determine
264      the exact CPU type, on others it will be necessary to give it
265      explicitly.  For example,
266
267           ./configure --build=ultrasparc-sun-solaris2.7
268
269      In all cases the `OS' part is important, since it controls how
270      libtool generates shared libraries.  Running `./config.guess' is
271      the simplest way to see what it should be, if you don't know
272      already.
273
274 Cross Compilation, `--host=CPU-VENDOR-OS'
275      When cross-compiling, the system used for compiling is given by
276      `--build' and the system where the library will run is given by
277      `--host'.  For example when using a FreeBSD Athlon system to build
278      GNU/Linux m68k binaries,
279
280           ./configure --build=athlon-pc-freebsd3.5 --host=m68k-mac-linux-gnu
281
282      Compiler tools are sought first with the host system type as a
283      prefix.  For example `m68k-mac-linux-gnu-ranlib' is tried, then
284      plain `ranlib'.  This makes it possible for a set of
285      cross-compiling tools to co-exist with native tools.  The prefix
286      is the argument to `--host', and this can be an alias, such as
287      `m68k-linux'.  But note that tools don't have to be setup this
288      way, it's enough to just have a `PATH' with a suitable
289      cross-compiling `cc' etc.
290
291      Compiling for a different CPU in the same family as the build
292      system is a form of cross-compilation, though very possibly this
293      would merely be special options on a native compiler.  In any case
294      `./configure' avoids depending on being able to run code on the
295      build system, which is important when creating binaries for a
296      newer CPU since they very possibly won't run on the build system.
297
298      In all cases the compiler must be able to produce an executable
299      (of whatever format) from a standard C `main'.  Although only
300      object files will go to make up `libgmp', `./configure' uses
301      linking tests for various purposes, such as determining what
302      functions are available on the host system.
303
304      Currently a warning is given unless an explicit `--build' is used
305      when cross-compiling, because it may not be possible to correctly
306      guess the build system type if the `PATH' has only a
307      cross-compiling `cc'.
308
309      Note that the `--target' option is not appropriate for GMP.  It's
310      for use when building compiler tools, with `--host' being where
311      they will run, and `--target' what they'll produce code for.
312      Ordinary programs or libraries like GMP are only interested in the
313      `--host' part, being where they'll run.  (Some past versions of
314      GMP used `--target' incorrectly.)
315
316 CPU types
317      In general, if you want a library that runs as fast as possible,
318      you should configure GMP for the exact CPU type your system uses.
319      However, this may mean the binaries won't run on older members of
320      the family, and might run slower on other members, older or newer.
321      The best idea is always to build GMP for the exact machine type
322      you intend to run it on.
323
324      The following CPUs have specific support.  See `configure.in' for
325      details of what code and compiler options they select.
326
327         * Alpha: alpha, alphaev5, alphaev56, alphapca56, alphapca57,
328           alphaev6, alphaev67, alphaev68 alphaev7
329
330         * Cray: c90, j90, t90, sv1
331
332         * HPPA: hppa1.0, hppa1.1, hppa2.0, hppa2.0n, hppa2.0w, hppa64
333
334         * IA-64: ia64, itanium, itanium2
335
336         * MIPS: mips, mips3, mips64
337
338         * Motorola: m68k, m68000, m68010, m68020, m68030, m68040,
339           m68060, m68302, m68360, m88k, m88110
340
341         * POWER: power, power1, power2, power2sc
342
343         * PowerPC: powerpc, powerpc64, powerpc401, powerpc403,
344           powerpc405, powerpc505, powerpc601, powerpc602, powerpc603,
345           powerpc603e, powerpc604, powerpc604e, powerpc620, powerpc630,
346           powerpc740, powerpc7400, powerpc7450, powerpc750, powerpc801,
347           powerpc821, powerpc823, powerpc860, powerpc970
348
349         * SPARC: sparc, sparcv8, microsparc, supersparc, sparcv9,
350           ultrasparc, ultrasparc2, ultrasparc2i, ultrasparc3, sparc64
351
352         * x86 family: i386, i486, i586, pentium, pentiummmx, pentiumpro,
353           pentium2, pentium3, pentium4, k6, k62, k63, athlon, amd64,
354           viac3, viac32
355
356         * Other: a29k, arm, clipper, i960, ns32k, pyramid, sh, sh2, vax,
357           z8k
358
359      CPUs not listed will use generic C code.
360
361 Generic C Build
362      If some of the assembly code causes problems, or if otherwise
363      desired, the generic C code can be selected with CPU `none'.  For
364      example,
365
366           ./configure --host=none-unknown-freebsd3.5
367
368      Note that this will run quite slowly, but it should be portable
369      and should at least make it possible to get something running if
370      all else fails.
371
372 Fat binary, `--enable-fat'
373      Using `--enable-fat' selects a "fat binary" build on x86, where
374      optimized low level subroutines are chosen at runtime according to
375      the CPU detected.  This means more code, but gives good
376      performance on all x86 chips.  (This option might become available
377      for more architectures in the future.)
378
379 `ABI'
380      On some systems GMP supports multiple ABIs (application binary
381      interfaces), meaning data type sizes and calling conventions.  By
382      default GMP chooses the best ABI available, but a particular ABI
383      can be selected.  For example
384
385           ./configure --host=mips64-sgi-irix6 ABI=n32
386
387      See *Note ABI and ISA::, for the available choices on relevant
388      CPUs, and what applications need to do.
389
390 `CC', `CFLAGS'
391      By default the C compiler used is chosen from among some likely
392      candidates, with `gcc' normally preferred if it's present.  The
393      usual `CC=whatever' can be passed to `./configure' to choose
394      something different.
395
396      For various systems, default compiler flags are set based on the
397      CPU and compiler.  The usual `CFLAGS="-whatever"' can be passed to
398      `./configure' to use something different or to set good flags for
399      systems GMP doesn't otherwise know.
400
401      The `CC' and `CFLAGS' used are printed during `./configure', and
402      can be found in each generated `Makefile'.  This is the easiest way
403      to check the defaults when considering changing or adding
404      something.
405
406      Note that when `CC' and `CFLAGS' are specified on a system
407      supporting multiple ABIs it's important to give an explicit
408      `ABI=whatever', since GMP can't determine the ABI just from the
409      flags and won't be able to select the correct assembly code.
410
411      If just `CC' is selected then normal default `CFLAGS' for that
412      compiler will be used (if GMP recognises it).  For example
413      `CC=gcc' can be used to force the use of GCC, with default flags
414      (and default ABI).
415
416 `CPPFLAGS'
417      Any flags like `-D' defines or `-I' includes required by the
418      preprocessor should be set in `CPPFLAGS' rather than `CFLAGS'.
419      Compiling is done with both `CPPFLAGS' and `CFLAGS', but
420      preprocessing uses just `CPPFLAGS'.  This distinction is because
421      most preprocessors won't accept all the flags the compiler does.
422      Preprocessing is done separately in some configure tests, and in
423      the `ansi2knr' support for K&R compilers.
424
425 `CC_FOR_BUILD'
426      Some build-time programs are compiled and run to generate
427      host-specific data tables.  `CC_FOR_BUILD' is the compiler used
428      for this.  It doesn't need to be in any particular ABI or mode, it
429      merely needs to generate executables that can run.  The default is
430      to try the selected `CC' and some likely candidates such as `cc'
431      and `gcc', looking for something that works.
432
433      No flags are used with `CC_FOR_BUILD' because a simple invocation
434      like `cc foo.c' should be enough.  If some particular options are
435      required they can be included as for instance `CC_FOR_BUILD="cc
436      -whatever"'.
437
438 C++ Support, `--enable-cxx'
439      C++ support in GMP can be enabled with `--enable-cxx', in which
440      case a C++ compiler will be required.  As a convenience
441      `--enable-cxx=detect' can be used to enable C++ support only if a
442      compiler can be found.  The C++ support consists of a library
443      `libgmpxx.la' and header file `gmpxx.h' (*note Headers and
444      Libraries::).
445
446      A separate `libgmpxx.la' has been adopted rather than having C++
447      objects within `libgmp.la' in order to ensure dynamic linked C
448      programs aren't bloated by a dependency on the C++ standard
449      library, and to avoid any chance that the C++ compiler could be
450      required when linking plain C programs.
451
452      `libgmpxx.la' will use certain internals from `libgmp.la' and can
453      only be expected to work with `libgmp.la' from the same GMP
454      version.  Future changes to the relevant internals will be
455      accompanied by renaming, so a mismatch will cause unresolved
456      symbols rather than perhaps mysterious misbehaviour.
457
458      In general `libgmpxx.la' will be usable only with the C++ compiler
459      that built it, since name mangling and runtime support are usually
460      incompatible between different compilers.
461
462 `CXX', `CXXFLAGS'
463      When C++ support is enabled, the C++ compiler and its flags can be
464      set with variables `CXX' and `CXXFLAGS' in the usual way.  The
465      default for `CXX' is the first compiler that works from a list of
466      likely candidates, with `g++' normally preferred when available.
467      The default for `CXXFLAGS' is to try `CFLAGS', `CFLAGS' without
468      `-g', then for `g++' either `-g -O2' or `-O2', or for other
469      compilers `-g' or nothing.  Trying `CFLAGS' this way is convenient
470      when using `gcc' and `g++' together, since the flags for `gcc' will
471      usually suit `g++'.
472
473      It's important that the C and C++ compilers match, meaning their
474      startup and runtime support routines are compatible and that they
475      generate code in the same ABI (if there's a choice of ABIs on the
476      system).  `./configure' isn't currently able to check these things
477      very well itself, so for that reason `--disable-cxx' is the
478      default, to avoid a build failure due to a compiler mismatch.
479      Perhaps this will change in the future.
480
481      Incidentally, it's normally not good enough to set `CXX' to the
482      same as `CC'.  Although `gcc' for instance recognises `foo.cc' as
483      C++ code, only `g++' will invoke the linker the right way when
484      building an executable or shared library from C++ object files.
485
486 Temporary Memory, `--enable-alloca=<choice>'
487      GMP allocates temporary workspace using one of the following three
488      methods, which can be selected with for instance
489      `--enable-alloca=malloc-reentrant'.
490
491         * `alloca' - C library or compiler builtin.
492
493         * `malloc-reentrant' - the heap, in a re-entrant fashion.
494
495         * `malloc-notreentrant' - the heap, with global variables.
496
497      For convenience, the following choices are also available.
498      `--disable-alloca' is the same as `no'.
499
500         * `yes' - a synonym for `alloca'.
501
502         * `no' - a synonym for `malloc-reentrant'.
503
504         * `reentrant' - `alloca' if available, otherwise
505           `malloc-reentrant'.  This is the default.
506
507         * `notreentrant' - `alloca' if available, otherwise
508           `malloc-notreentrant'.
509
510      `alloca' is reentrant and fast, and is recommended.  It actually
511      allocates just small blocks on the stack; larger ones use
512      malloc-reentrant.
513
514      `malloc-reentrant' is, as the name suggests, reentrant and thread
515      safe, but `malloc-notreentrant' is faster and should be used if
516      reentrancy is not required.
517
518      The two malloc methods in fact use the memory allocation functions
519      selected by `mp_set_memory_functions', these being `malloc' and
520      friends by default.  *Note Custom Allocation::.
521
522      An additional choice `--enable-alloca=debug' is available, to help
523      when debugging memory related problems (*note Debugging::).
524
525 FFT Multiplication, `--disable-fft'
526      By default multiplications are done using Karatsuba, 3-way Toom,
527      and Fermat FFT.  The FFT is only used on large to very large
528      operands and can be disabled to save code size if desired.
529
530 Berkeley MP, `--enable-mpbsd'
531      The Berkeley MP compatibility library (`libmp') and header file
532      (`mp.h') are built and installed only if `--enable-mpbsd' is used.
533      *Note BSD Compatible Functions::.
534
535 Assertion Checking, `--enable-assert'
536      This option enables some consistency checking within the library.
537      This can be of use while debugging, *note Debugging::.
538
539 Execution Profiling, `--enable-profiling=prof/gprof/instrument'
540      Enable profiling support, in one of various styles, *note
541      Profiling::.
542
543 `MPN_PATH'
544      Various assembly versions of each mpn subroutines are provided.
545      For a given CPU, a search is made though a path to choose a
546      version of each.  For example `sparcv8' has
547
548           MPN_PATH="sparc32/v8 sparc32 generic"
549
550      which means look first for v8 code, then plain sparc32 (which is
551      v7), and finally fall back on generic C.  Knowledgeable users with
552      special requirements can specify a different path.  Normally this
553      is completely unnecessary.
554
555 Documentation
556      The source for the document you're now reading is `doc/gmp.texi',
557      in Texinfo format, see *Note Texinfo: (texinfo)Top.
558
559      Info format `doc/gmp.info' is included in the distribution.  The
560      usual automake targets are available to make PostScript, DVI, PDF
561      and HTML (these will require various TeX and Texinfo tools).
562
563      DocBook and XML can be generated by the Texinfo `makeinfo' program
564      too, see *Note Options for `makeinfo': (texinfo)makeinfo options.
565
566      Some supplementary notes can also be found in the `doc'
567      subdirectory.
568
569
570 \1f
571 File: gmp.info,  Node: ABI and ISA,  Next: Notes for Package Builds,  Prev: Build Options,  Up: Installing GMP
572
573 2.2 ABI and ISA
574 ===============
575
576 ABI (Application Binary Interface) refers to the calling conventions
577 between functions, meaning what registers are used and what sizes the
578 various C data types are.  ISA (Instruction Set Architecture) refers to
579 the instructions and registers a CPU has available.
580
581    Some 64-bit ISA CPUs have both a 64-bit ABI and a 32-bit ABI
582 defined, the latter for compatibility with older CPUs in the family.
583 GMP supports some CPUs like this in both ABIs.  In fact within GMP
584 `ABI' means a combination of chip ABI, plus how GMP chooses to use it.
585 For example in some 32-bit ABIs, GMP may support a limb as either a
586 32-bit `long' or a 64-bit `long long'.
587
588    By default GMP chooses the best ABI available for a given system,
589 and this generally gives significantly greater speed.  But an ABI can
590 be chosen explicitly to make GMP compatible with other libraries, or
591 particular application requirements.  For example,
592
593      ./configure ABI=32
594
595    In all cases it's vital that all object code used in a given program
596 is compiled for the same ABI.
597
598    Usually a limb is implemented as a `long'.  When a `long long' limb
599 is used this is encoded in the generated `gmp.h'.  This is convenient
600 for applications, but it does mean that `gmp.h' will vary, and can't be
601 just copied around.  `gmp.h' remains compiler independent though, since
602 all compilers for a particular ABI will be expected to use the same
603 limb type.
604
605    Currently no attempt is made to follow whatever conventions a system
606 has for installing library or header files built for a particular ABI.
607 This will probably only matter when installing multiple builds of GMP,
608 and it might be as simple as configuring with a special `libdir', or it
609 might require more than that.  Note that builds for different ABIs need
610 to done separately, with a fresh `./configure' and `make' each.
611
612
613 AMD64 (`x86_64')
614      On AMD64 systems supporting both 32-bit and 64-bit modes for
615      applications, the following ABI choices are available.
616
617     `ABI=64'
618           The 64-bit ABI uses 64-bit limbs and pointers and makes full
619           use of the chip architecture.  This is the default.
620           Applications will usually not need special compiler flags,
621           but for reference the option is
622
623                gcc  -m64
624
625     `ABI=32'
626           The 32-bit ABI is the usual i386 conventions.  This will be
627           slower, and is not recommended except for inter-operating
628           with other code not yet 64-bit capable.  Applications must be
629           compiled with
630
631                gcc  -m32
632
633           (In GCC 2.95 and earlier there's no `-m32' option, it's the
634           only mode.)
635
636
637 HPPA 2.0 (`hppa2.0*', `hppa64')
638
639     `ABI=2.0w'
640           The 2.0w ABI uses 64-bit limbs and pointers and is available
641           on HP-UX 11 or up.  Applications must be compiled with
642
643                gcc [built for 2.0w]
644                cc  +DD64
645
646     `ABI=2.0n'
647           The 2.0n ABI means the 32-bit HPPA 1.0 ABI and all its normal
648           calling conventions, but with 64-bit instructions permitted
649           within functions.  GMP uses a 64-bit `long long' for a limb.
650           This ABI is available on hppa64 GNU/Linux and on HP-UX 10 or
651           higher.  Applications must be compiled with
652
653                gcc [built for 2.0n]
654                cc  +DA2.0 +e
655
656           Note that current versions of GCC (eg. 3.2) don't generate
657           64-bit instructions for `long long' operations and so may be
658           slower than for 2.0w.  (The GMP assembly code is the same
659           though.)
660
661     `ABI=1.0'
662           HPPA 2.0 CPUs can run all HPPA 1.0 and 1.1 code in the 32-bit
663           HPPA 1.0 ABI.  No special compiler options are needed for
664           applications.
665
666      All three ABIs are available for CPU types `hppa2.0w', `hppa2.0'
667      and `hppa64', but for CPU type `hppa2.0n' only 2.0n or 1.0 are
668      considered.
669
670      Note that GCC on HP-UX has no options to choose between 2.0n and
671      2.0w modes, unlike HP `cc'.  Instead it must be built for one or
672      the other ABI.  GMP will detect how it was built, and skip to the
673      corresponding `ABI'.
674
675
676 IA-64 under HP-UX (`ia64*-*-hpux*', `itanium*-*-hpux*')
677      HP-UX supports two ABIs for IA-64.  GMP performance is the same in
678      both.
679
680     `ABI=32'
681           In the 32-bit ABI, pointers, `int's and `long's are 32 bits
682           and GMP uses a 64 bit `long long' for a limb.  Applications
683           can be compiled without any special flags since this ABI is
684           the default in both HP C and GCC, but for reference the flags
685           are
686
687                gcc  -milp32
688                cc   +DD32
689
690     `ABI=64'
691           In the 64-bit ABI, `long's and pointers are 64 bits and GMP
692           uses a `long' for a limb.  Applications must be compiled with
693
694                gcc  -mlp64
695                cc   +DD64
696
697      On other IA-64 systems, GNU/Linux for instance, `ABI=64' is the
698      only choice.
699
700
701 MIPS under IRIX 6 (`mips*-*-irix[6789]')
702      IRIX 6 always has a 64-bit MIPS 3 or better CPU, and supports ABIs
703      o32, n32, and 64.  n32 or 64 are recommended, and GMP performance
704      will be the same in each.  The default is n32.
705
706     `ABI=o32'
707           The o32 ABI is 32-bit pointers and integers, and no 64-bit
708           operations.  GMP will be slower than in n32 or 64, this
709           option only exists to support old compilers, eg. GCC 2.7.2.
710           Applications can be compiled with no special flags on an old
711           compiler, or on a newer compiler with
712
713                gcc  -mabi=32
714                cc   -32
715
716     `ABI=n32'
717           The n32 ABI is 32-bit pointers and integers, but with a
718           64-bit limb using a `long long'.  Applications must be
719           compiled with
720
721                gcc  -mabi=n32
722                cc   -n32
723
724     `ABI=64'
725           The 64-bit ABI is 64-bit pointers and integers.  Applications
726           must be compiled with
727
728                gcc  -mabi=64
729                cc   -64
730
731      Note that MIPS GNU/Linux, as of kernel version 2.2, doesn't have
732      the necessary support for n32 or 64 and so only gets a 32-bit limb
733      and the MIPS 2 code.
734
735
736 PowerPC 64 (`powerpc64', `powerpc620', `powerpc630', `powerpc970', `power4', `power5')
737
738     `ABI=aix64'
739           The AIX 64 ABI uses 64-bit limbs and pointers and is the
740           default on PowerPC 64 `*-*-aix*' systems.  Applications must
741           be compiled with
742
743                gcc  -maix64
744                xlc  -q64
745
746     `ABI=mode64'
747           The `mode64' ABI uses 64-bit limbs and pointers, and is the
748           default on 64-bit GNU/Linux, BSD, and Mac OS X/Darwin
749           systems.  Applications must be compiled with
750
751                gcc  -m64
752
753     `ABI=mode32'
754           The `mode32' ABI uses a 64-bit `long long' limb but with the
755           chip still in 32-bit mode and using 32-bit calling
756           conventions.  This is the default on for systems where the
757           true 64-bit ABIs are unavailable.  No special compiler
758           options are needed for applications.
759
760     `ABI=32'
761           This is the basic 32-bit PowerPC ABI, with a 32-bit limb.  No
762           special compiler options are needed for applications.
763
764      GMP speed is greatest in `aix64' and `mode32'.  In `ABI=32' only
765      the 32-bit ISA is used and this doesn't make full use of a 64-bit
766      chip.  On a suitable system we could perhaps use more of the ISA,
767      but there are no plans to do so.
768
769
770 Sparc V9 (`sparc64', `sparcv9', `ultrasparc*')
771
772     `ABI=64'
773           The 64-bit V9 ABI is available on the various BSD sparc64
774           ports, recent versions of Sparc64 GNU/Linux, and Solaris 2.7
775           and up (when the kernel is in 64-bit mode).  GCC 3.2 or
776           higher, or Sun `cc' is required.  On GNU/Linux, depending on
777           the default `gcc' mode, applications must be compiled with
778
779                gcc  -m64
780
781           On Solaris applications must be compiled with
782
783                gcc  -m64 -mptr64 -Wa,-xarch=v9 -mcpu=v9
784                cc   -xarch=v9
785
786           On the BSD sparc64 systems no special options are required,
787           since 64-bits is the only ABI available.
788
789     `ABI=32'
790           For the basic 32-bit ABI, GMP still uses as much of the V9
791           ISA as it can.  In the Sun documentation this combination is
792           known as "v8plus".  On GNU/Linux, depending on the default
793           `gcc' mode, applications may need to be compiled with
794
795                gcc  -m32
796
797           On Solaris, no special compiler options are required for
798           applications, though using something like the following is
799           recommended.  (`gcc' 2.8 and earlier only support `-mv8'
800           though.)
801
802                gcc  -mv8plus
803                cc   -xarch=v8plus
804
805      GMP speed is greatest in `ABI=64', so it's the default where
806      available.  The speed is partly because there are extra registers
807      available and partly because 64-bits is considered the more
808      important case and has therefore had better code written for it.
809
810      Don't be confused by the names of the `-m' and `-x' compiler
811      options, they're called `arch' but effectively control both ABI
812      and ISA.
813
814      On Solaris 2.6 and earlier, only `ABI=32' is available since the
815      kernel doesn't save all registers.
816
817      On Solaris 2.7 with the kernel in 32-bit mode, a normal native
818      build will reject `ABI=64' because the resulting executables won't
819      run.  `ABI=64' can still be built if desired by making it look
820      like a cross-compile, for example
821
822           ./configure --build=none --host=sparcv9-sun-solaris2.7 ABI=64
823
824 \1f
825 File: gmp.info,  Node: Notes for Package Builds,  Next: Notes for Particular Systems,  Prev: ABI and ISA,  Up: Installing GMP
826
827 2.3 Notes for Package Builds
828 ============================
829
830 GMP should present no great difficulties for packaging in a binary
831 distribution.
832
833    Libtool is used to build the library and `-version-info' is set
834 appropriately, having started from `3:0:0' in GMP 3.0 (*note Library
835 interface versions: (libtool)Versioning.).
836
837    The GMP 4 series will be upwardly binary compatible in each release
838 and will be upwardly binary compatible with all of the GMP 3 series.
839 Additional function interfaces may be added in each release, so on
840 systems where libtool versioning is not fully checked by the loader an
841 auxiliary mechanism may be needed to express that a dynamic linked
842 application depends on a new enough GMP.
843
844    An auxiliary mechanism may also be needed to express that
845 `libgmpxx.la' (from `--enable-cxx', *note Build Options::) requires
846 `libgmp.la' from the same GMP version, since this is not done by the
847 libtool versioning, nor otherwise.  A mismatch will result in
848 unresolved symbols from the linker, or perhaps the loader.
849
850    When building a package for a CPU family, care should be taken to use
851 `--host' (or `--build') to choose the least common denominator among
852 the CPUs which might use the package.  For example this might mean plain
853 `sparc' (meaning V7) for SPARCs.
854
855    For x86s, `--enable-fat' sets things up for a fat binary build,
856 making a runtime selection of optimized low level routines.  This is a
857 good choice for packaging to run on a range of x86 chips.
858
859    Users who care about speed will want GMP built for their exact CPU
860 type, to make best use of the available optimizations.  Providing a way
861 to suitably rebuild a package may be useful.  This could be as simple
862 as making it possible for a user to omit `--build' (and `--host') so
863 `./config.guess' will detect the CPU.  But a way to manually specify a
864 `--build' will be wanted for systems where `./config.guess' is inexact.
865
866    On systems with multiple ABIs, a packaged build will need to decide
867 which among the choices is to be provided, see *Note ABI and ISA::.  A
868 given run of `./configure' etc will only build one ABI.  If a second
869 ABI is also required then a second run of `./configure' etc must be
870 made, starting from a clean directory tree (`make distclean').
871
872    As noted under "ABI and ISA", currently no attempt is made to follow
873 system conventions for install locations that vary with ABI, such as
874 `/usr/lib/sparcv9' for `ABI=64' as opposed to `/usr/lib' for `ABI=32'.
875 A package build can override `libdir' and other standard variables as
876 necessary.
877
878    Note that `gmp.h' is a generated file, and will be architecture and
879 ABI dependent.  When attempting to install two ABIs simultaneously it
880 will be important that an application compile gets the correct `gmp.h'
881 for its desired ABI.  If compiler include paths don't vary with ABI
882 options then it might be necessary to create a `/usr/include/gmp.h'
883 which tests preprocessor symbols and chooses the correct actual `gmp.h'.
884
885 \1f
886 File: gmp.info,  Node: Notes for Particular Systems,  Next: Known Build Problems,  Prev: Notes for Package Builds,  Up: Installing GMP
887
888 2.4 Notes for Particular Systems
889 ================================
890
891 AIX 3 and 4
892      On systems `*-*-aix[34]*' shared libraries are disabled by
893      default, since some versions of the native `ar' fail on the
894      convenience libraries used.  A shared build can be attempted with
895
896           ./configure --enable-shared --disable-static
897
898      Note that the `--disable-static' is necessary because in a shared
899      build libtool makes `libgmp.a' a symlink to `libgmp.so',
900      apparently for the benefit of old versions of `ld' which only
901      recognise `.a', but unfortunately this is done even if a fully
902      functional `ld' is available.
903
904 ARM
905      On systems `arm*-*-*', versions of GCC up to and including 2.95.3
906      have a bug in unsigned division, giving wrong results for some
907      operands.  GMP `./configure' will demand GCC 2.95.4 or later.
908
909 Compaq C++
910      Compaq C++ on OSF 5.1 has two flavours of `iostream', a standard
911      one and an old pre-standard one (see `man iostream_intro').  GMP
912      can only use the standard one, which unfortunately is not the
913      default but must be selected by defining `__USE_STD_IOSTREAM'.
914      Configure with for instance
915
916           ./configure --enable-cxx CPPFLAGS=-D__USE_STD_IOSTREAM
917
918 Floating Point Mode
919      On some systems, the hardware floating point has a control mode
920      which can set all operations to be done in a particular precision,
921      for instance single, double or extended on x86 systems (x87
922      floating point).  The GMP functions involving a `double' cannot be
923      expected to operate to their full precision when the hardware is
924      in single precision mode.  Of course this affects all code,
925      including application code, not just GMP.
926
927 MS-DOS and MS Windows
928      On an MS-DOS system DJGPP can be used to build GMP, and on an MS
929      Windows system Cygwin, DJGPP and MINGW can be used.  All three are
930      excellent ports of GCC and the various GNU tools.
931
932           `http://www.cygwin.com/'
933           `http://www.delorie.com/djgpp/'
934           `http://www.mingw.org/'
935
936      Microsoft also publishes an Interix "Services for Unix" which can
937      be used to build GMP on Windows (with a normal `./configure'), but
938      it's not free software.
939
940 MS Windows DLLs
941      On systems `*-*-cygwin*', `*-*-mingw*' and `*-*-pw32*' by default
942      GMP builds only a static library, but a DLL can be built instead
943      using
944
945           ./configure --disable-static --enable-shared
946
947      Static and DLL libraries can't both be built, since certain export
948      directives in `gmp.h' must be different.
949
950      A MINGW DLL build of GMP can be used with Microsoft C.  Libtool
951      doesn't install a `.lib' format import library, but it can be
952      created with MS `lib' as follows, and copied to the install
953      directory.  Similarly for `libmp' and `libgmpxx'.
954
955           cd .libs
956           lib /def:libgmp-3.dll.def /out:libgmp-3.lib
957
958      MINGW uses the C runtime library `msvcrt.dll' for I/O, so
959      applications wanting to use the GMP I/O routines must be compiled
960      with `cl /MD' to do the same.  If one of the other C runtime
961      library choices provided by MS C is desired then the suggestion is
962      to use the GMP string functions and confine I/O to the application.
963
964 Motorola 68k CPU Types
965      `m68k' is taken to mean 68000.  `m68020' or higher will give a
966      performance boost on applicable CPUs.  `m68360' can be used for
967      CPU32 series chips.  `m68302' can be used for "Dragonball" series
968      chips, though this is merely a synonym for `m68000'.
969
970 OpenBSD 2.6
971      `m4' in this release of OpenBSD has a bug in `eval' that makes it
972      unsuitable for `.asm' file processing.  `./configure' will detect
973      the problem and either abort or choose another m4 in the `PATH'.
974      The bug is fixed in OpenBSD 2.7, so either upgrade or use GNU m4.
975
976 Power CPU Types
977      In GMP, CPU types `power*' and `powerpc*' will each use
978      instructions not available on the other, so it's important to
979      choose the right one for the CPU that will be used.  Currently GMP
980      has no assembly code support for using just the common instruction
981      subset.  To get executables that run on both, the current
982      suggestion is to use the generic C code (CPU `none'), possibly
983      with appropriate compiler options (like `-mcpu=common' for `gcc').
984      CPU `rs6000' (which is not a CPU but a family of workstations) is
985      accepted by `config.sub', but is currently equivalent to `none'.
986
987 Sparc CPU Types
988      `sparcv8' or `supersparc' on relevant systems will give a
989      significant performance increase over the V7 code selected by plain
990      `sparc'.
991
992 Sparc App Regs
993      The GMP assembly code for both 32-bit and 64-bit Sparc clobbers the
994      "application registers" `g2', `g3' and `g4', the same way that the
995      GCC default `-mapp-regs' does (*note SPARC Options: (gcc)SPARC
996      Options.).
997
998      This makes that code unsuitable for use with the special V9
999      `-mcmodel=embmedany' (which uses `g4' as a data segment pointer),
1000      and for applications wanting to use those registers for special
1001      purposes.  In these cases the only suggestion currently is to
1002      build GMP with CPU `none' to avoid the assembly code.
1003
1004 SunOS 4
1005      `/usr/bin/m4' lacks various features needed to process `.asm'
1006      files, and instead `./configure' will automatically use
1007      `/usr/5bin/m4', which we believe is always available (if not then
1008      use GNU m4).
1009
1010 x86 CPU Types
1011      `i586', `pentium' or `pentiummmx' code is good for its intended P5
1012      Pentium chips, but quite slow when run on Intel P6 class chips
1013      (PPro, P-II, P-III).  `i386' is a better choice when making
1014      binaries that must run on both.
1015
1016 x86 MMX and SSE2 Code
1017      If the CPU selected has MMX code but the assembler doesn't support
1018      it, a warning is given and non-MMX code is used instead.  This
1019      will be an inferior build, since the MMX code that's present is
1020      there because it's faster than the corresponding plain integer
1021      code.  The same applies to SSE2.
1022
1023      Old versions of `gas' don't support MMX instructions, in particular
1024      version 1.92.3 that comes with FreeBSD 2.2.8 or the more recent
1025      OpenBSD 3.1 doesn't.
1026
1027      Solaris 2.6 and 2.7 `as' generate incorrect object code for
1028      register to register `movq' instructions, and so can't be used for
1029      MMX code.  Install a recent `gas' if MMX code is wanted on these
1030      systems.
1031
1032 \1f
1033 File: gmp.info,  Node: Known Build Problems,  Next: Performance optimization,  Prev: Notes for Particular Systems,  Up: Installing GMP
1034
1035 2.5 Known Build Problems
1036 ========================
1037
1038 You might find more up-to-date information at `http://gmplib.org/'.
1039
1040 Compiler link options
1041      The version of libtool currently in use rather aggressively strips
1042      compiler options when linking a shared library.  This will
1043      hopefully be relaxed in the future, but for now if this is a
1044      problem the suggestion is to create a little script to hide them,
1045      and for instance configure with
1046
1047           ./configure CC=gcc-with-my-options
1048
1049 DJGPP (`*-*-msdosdjgpp*')
1050      The DJGPP port of `bash' 2.03 is unable to run the `configure'
1051      script, it exits silently, having died writing a preamble to
1052      `config.log'.  Use `bash' 2.04 or higher.
1053
1054      `make all' was found to run out of memory during the final
1055      `libgmp.la' link on one system tested, despite having 64Mb
1056      available.  Running `make libgmp.la' directly helped, perhaps
1057      recursing into the various subdirectories uses up memory.
1058
1059 GNU binutils `strip' prior to 2.12
1060      `strip' from GNU binutils 2.11 and earlier should not be used on
1061      the static libraries `libgmp.a' and `libmp.a' since it will
1062      discard all but the last of multiple archive members with the same
1063      name, like the three versions of `init.o' in `libgmp.a'.  Binutils
1064      2.12 or higher can be used successfully.
1065
1066      The shared libraries `libgmp.so' and `libmp.so' are not affected by
1067      this and any version of `strip' can be used on them.
1068
1069 `make' syntax error
1070      On certain versions of SCO OpenServer 5 and IRIX 6.5 the native
1071      `make' is unable to handle the long dependencies list for
1072      `libgmp.la'.  The symptom is a "syntax error" on the following
1073      line of the top-level `Makefile'.
1074
1075           libgmp.la: $(libgmp_la_OBJECTS) $(libgmp_la_DEPENDENCIES)
1076
1077      Either use GNU Make, or as a workaround remove
1078      `$(libgmp_la_DEPENDENCIES)' from that line (which will make the
1079      initial build work, but if any recompiling is done `libgmp.la'
1080      might not be rebuilt).
1081
1082 MacOS X (`*-*-darwin*')
1083      Libtool currently only knows how to create shared libraries on
1084      MacOS X using the native `cc' (which is a modified GCC), not a
1085      plain GCC.  A static-only build should work though
1086      (`--disable-shared').
1087
1088 NeXT prior to 3.3
1089      The system compiler on old versions of NeXT was a massacred and
1090      old GCC, even if it called itself `cc'.  This compiler cannot be
1091      used to build GMP, you need to get a real GCC, and install that.
1092      (NeXT may have fixed this in release 3.3 of their system.)
1093
1094 POWER and PowerPC
1095      Bugs in GCC 2.7.2 (and 2.6.3) mean it can't be used to compile GMP
1096      on POWER or PowerPC.  If you want to use GCC for these machines,
1097      get GCC 2.7.2.1 (or later).
1098
1099 Sequent Symmetry
1100      Use the GNU assembler instead of the system assembler, since the
1101      latter has serious bugs.
1102
1103 Solaris 2.6
1104      The system `sed' prints an error "Output line too long" when
1105      libtool builds `libgmp.la'.  This doesn't seem to cause any
1106      obvious ill effects, but GNU `sed' is recommended, to avoid any
1107      doubt.
1108
1109 Sparc Solaris 2.7 with gcc 2.95.2 in `ABI=32'
1110      A shared library build of GMP seems to fail in this combination,
1111      it builds but then fails the tests, apparently due to some
1112      incorrect data relocations within `gmp_randinit_lc_2exp_size'.
1113      The exact cause is unknown, `--disable-shared' is recommended.
1114
1115 \1f
1116 File: gmp.info,  Node: Performance optimization,  Prev: Known Build Problems,  Up: Installing GMP
1117
1118 2.6 Performance optimization
1119 ============================
1120
1121 For optimal performance, build GMP for the exact CPU type of the target
1122 computer, see *Note Build Options::.
1123
1124    Unlike what is the case for most other programs, the compiler
1125 typically doesn't matter much, since GMP uses assembly language for the
1126 most critical operation.
1127
1128    In particular for long-running GMP applications, and applications
1129 demanding extremely large numbers, building and running the `tuneup'
1130 program in the `tune' subdirectory, can be important.  For example,
1131
1132      cd tune
1133      make tuneup
1134      ./tuneup
1135
1136    will generate better contents for the `gmp-mparam.h' parameter file.
1137
1138    To use the results, put the output in the file file indicated in the
1139 `Parameters for ...' header.  Then recompile from scratch.
1140
1141    The `tuneup' program takes one useful parameter, `-f NNN', which
1142 instructs the program how long to check FFT multiply parameters.  If
1143 you're going to use GMP for extremely large numbers, you may want to
1144 run `tuneup' with a large NNN value.
1145
1146 \1f
1147 File: gmp.info,  Node: GMP Basics,  Next: Reporting Bugs,  Prev: Installing GMP,  Up: Top
1148
1149 3 GMP Basics
1150 ************
1151
1152 *Using functions, macros, data types, etc. not documented in this
1153 manual is strongly discouraged.  If you do so your application is
1154 guaranteed to be incompatible with future versions of GMP.*
1155
1156 * Menu:
1157
1158 * Headers and Libraries::
1159 * Nomenclature and Types::
1160 * Function Classes::
1161 * Variable Conventions::
1162 * Parameter Conventions::
1163 * Memory Management::
1164 * Reentrancy::
1165 * Useful Macros and Constants::
1166 * Compatibility with older versions::
1167 * Demonstration Programs::
1168 * Efficiency::
1169 * Debugging::
1170 * Profiling::
1171 * Autoconf::
1172 * Emacs::
1173
1174 \1f
1175 File: gmp.info,  Node: Headers and Libraries,  Next: Nomenclature and Types,  Prev: GMP Basics,  Up: GMP Basics
1176
1177 3.1 Headers and Libraries
1178 =========================
1179
1180 All declarations needed to use GMP are collected in the include file
1181 `gmp.h'.  It is designed to work with both C and C++ compilers.
1182
1183      #include <gmp.h>
1184
1185    Note however that prototypes for GMP functions with `FILE *'
1186 parameters are only provided if `<stdio.h>' is included too.
1187
1188      #include <stdio.h>
1189      #include <gmp.h>
1190
1191    Likewise `<stdarg.h>' (or `<varargs.h>') is required for prototypes
1192 with `va_list' parameters, such as `gmp_vprintf'.  And `<obstack.h>'
1193 for prototypes with `struct obstack' parameters, such as
1194 `gmp_obstack_printf', when available.
1195
1196    All programs using GMP must link against the `libgmp' library.  On a
1197 typical Unix-like system this can be done with `-lgmp', for example
1198
1199      gcc myprogram.c -lgmp
1200
1201    GMP C++ functions are in a separate `libgmpxx' library.  This is
1202 built and installed if C++ support has been enabled (*note Build
1203 Options::).  For example,
1204
1205      g++ mycxxprog.cc -lgmpxx -lgmp
1206
1207    GMP is built using Libtool and an application can use that to link
1208 if desired, *note GNU Libtool: (libtool)Top.
1209
1210    If GMP has been installed to a non-standard location then it may be
1211 necessary to use `-I' and `-L' compiler options to point to the right
1212 directories, and some sort of run-time path for a shared library.
1213
1214 \1f
1215 File: gmp.info,  Node: Nomenclature and Types,  Next: Function Classes,  Prev: Headers and Libraries,  Up: GMP Basics
1216
1217 3.2 Nomenclature and Types
1218 ==========================
1219
1220 In this manual, "integer" usually means a multiple precision integer, as
1221 defined by the GMP library.  The C data type for such integers is
1222 `mpz_t'.  Here are some examples of how to declare such integers:
1223
1224      mpz_t sum;
1225
1226      struct foo { mpz_t x, y; };
1227
1228      mpz_t vec[20];
1229
1230    "Rational number" means a multiple precision fraction.  The C data
1231 type for these fractions is `mpq_t'.  For example:
1232
1233      mpq_t quotient;
1234
1235    "Floating point number" or "Float" for short, is an arbitrary
1236 precision mantissa with a limited precision exponent.  The C data type
1237 for such objects is `mpf_t'.  For example:
1238
1239      mpf_t fp;
1240
1241    The floating point functions accept and return exponents in the C
1242 type `mp_exp_t'.  Currently this is usually a `long', but on some
1243 systems it's an `int' for efficiency.
1244
1245    A "limb" means the part of a multi-precision number that fits in a
1246 single machine word.  (We chose this word because a limb of the human
1247 body is analogous to a digit, only larger, and containing several
1248 digits.)  Normally a limb is 32 or 64 bits.  The C data type for a limb
1249 is `mp_limb_t'.
1250
1251    Counts of limbs of a multi-precision number represented in the C type
1252 `mp_size_t'.  Currently this is normally a `long', but on some systems
1253 it's an `int' for efficiency, and on some systems it will be `long
1254 long' in the future.
1255
1256    Counts of bits of a multi-precision number are represented in the C
1257 type `mp_bitcnt_t'.  Currently this is always an `unsigned long', but on
1258 some systems it will be an `unsigned long long' in the future .
1259
1260    "Random state" means an algorithm selection and current state data.
1261 The C data type for such objects is `gmp_randstate_t'.  For example:
1262
1263      gmp_randstate_t rstate;
1264
1265    Also, in general `mp_bitcnt_t' is used for bit counts and ranges, and
1266 `size_t' is used for byte or character counts.
1267
1268 \1f
1269 File: gmp.info,  Node: Function Classes,  Next: Variable Conventions,  Prev: Nomenclature and Types,  Up: GMP Basics
1270
1271 3.3 Function Classes
1272 ====================
1273
1274 There are six classes of functions in the GMP library:
1275
1276   1. Functions for signed integer arithmetic, with names beginning with
1277      `mpz_'.  The associated type is `mpz_t'.  There are about 150
1278      functions in this class.  (*note Integer Functions::)
1279
1280   2. Functions for rational number arithmetic, with names beginning with
1281      `mpq_'.  The associated type is `mpq_t'.  There are about 40
1282      functions in this class, but the integer functions can be used for
1283      arithmetic on the numerator and denominator separately.  (*note
1284      Rational Number Functions::)
1285
1286   3. Functions for floating-point arithmetic, with names beginning with
1287      `mpf_'.  The associated type is `mpf_t'.  There are about 60
1288      functions is this class.  (*note Floating-point Functions::)
1289
1290   4. Functions compatible with Berkeley MP, such as `itom', `madd', and
1291      `mult'.  The associated type is `MINT'.  (*note BSD Compatible
1292      Functions::)
1293
1294   5. Fast low-level functions that operate on natural numbers.  These
1295      are used by the functions in the preceding groups, and you can
1296      also call them directly from very time-critical user programs.
1297      These functions' names begin with `mpn_'.  The associated type is
1298      array of `mp_limb_t'.  There are about 30 (hard-to-use) functions
1299      in this class.  (*note Low-level Functions::)
1300
1301   6. Miscellaneous functions.  Functions for setting up custom
1302      allocation and functions for generating random numbers.  (*note
1303      Custom Allocation::, and *note Random Number Functions::)
1304
1305 \1f
1306 File: gmp.info,  Node: Variable Conventions,  Next: Parameter Conventions,  Prev: Function Classes,  Up: GMP Basics
1307
1308 3.4 Variable Conventions
1309 ========================
1310
1311 GMP functions generally have output arguments before input arguments.
1312 This notation is by analogy with the assignment operator.  The BSD MP
1313 compatibility functions are exceptions, having the output arguments
1314 last.
1315
1316    GMP lets you use the same variable for both input and output in one
1317 call.  For example, the main function for integer multiplication,
1318 `mpz_mul', can be used to square `x' and put the result back in `x' with
1319
1320      mpz_mul (x, x, x);
1321
1322    Before you can assign to a GMP variable, you need to initialize it
1323 by calling one of the special initialization functions.  When you're
1324 done with a variable, you need to clear it out, using one of the
1325 functions for that purpose.  Which function to use depends on the type
1326 of variable.  See the chapters on integer functions, rational number
1327 functions, and floating-point functions for details.
1328
1329    A variable should only be initialized once, or at least cleared
1330 between each initialization.  After a variable has been initialized, it
1331 may be assigned to any number of times.
1332
1333    For efficiency reasons, avoid excessive initializing and clearing.
1334 In general, initialize near the start of a function and clear near the
1335 end.  For example,
1336
1337      void
1338      foo (void)
1339      {
1340        mpz_t  n;
1341        int    i;
1342        mpz_init (n);
1343        for (i = 1; i < 100; i++)
1344          {
1345            mpz_mul (n, ...);
1346            mpz_fdiv_q (n, ...);
1347            ...
1348          }
1349        mpz_clear (n);
1350      }
1351
1352 \1f
1353 File: gmp.info,  Node: Parameter Conventions,  Next: Memory Management,  Prev: Variable Conventions,  Up: GMP Basics
1354
1355 3.5 Parameter Conventions
1356 =========================
1357
1358 When a GMP variable is used as a function parameter, it's effectively a
1359 call-by-reference, meaning if the function stores a value there it will
1360 change the original in the caller.  Parameters which are input-only can
1361 be designated `const' to provoke a compiler error or warning on
1362 attempting to modify them.
1363
1364    When a function is going to return a GMP result, it should designate
1365 a parameter that it sets, like the library functions do.  More than one
1366 value can be returned by having more than one output parameter, again
1367 like the library functions.  A `return' of an `mpz_t' etc doesn't
1368 return the object, only a pointer, and this is almost certainly not
1369 what's wanted.
1370
1371    Here's an example accepting an `mpz_t' parameter, doing a
1372 calculation, and storing the result to the indicated parameter.
1373
1374      void
1375      foo (mpz_t result, const mpz_t param, unsigned long n)
1376      {
1377        unsigned long  i;
1378        mpz_mul_ui (result, param, n);
1379        for (i = 1; i < n; i++)
1380          mpz_add_ui (result, result, i*7);
1381      }
1382
1383      int
1384      main (void)
1385      {
1386        mpz_t  r, n;
1387        mpz_init (r);
1388        mpz_init_set_str (n, "123456", 0);
1389        foo (r, n, 20L);
1390        gmp_printf ("%Zd\n", r);
1391        return 0;
1392      }
1393
1394    `foo' works even if the mainline passes the same variable for
1395 `param' and `result', just like the library functions.  But sometimes
1396 it's tricky to make that work, and an application might not want to
1397 bother supporting that sort of thing.
1398
1399    For interest, the GMP types `mpz_t' etc are implemented as
1400 one-element arrays of certain structures.  This is why declaring a
1401 variable creates an object with the fields GMP needs, but then using it
1402 as a parameter passes a pointer to the object.  Note that the actual
1403 fields in each `mpz_t' etc are for internal use only and should not be
1404 accessed directly by code that expects to be compatible with future GMP
1405 releases.
1406
1407 \1f
1408 File: gmp.info,  Node: Memory Management,  Next: Reentrancy,  Prev: Parameter Conventions,  Up: GMP Basics
1409
1410 3.6 Memory Management
1411 =====================
1412
1413 The GMP types like `mpz_t' are small, containing only a couple of sizes,
1414 and pointers to allocated data.  Once a variable is initialized, GMP
1415 takes care of all space allocation.  Additional space is allocated
1416 whenever a variable doesn't have enough.
1417
1418    `mpz_t' and `mpq_t' variables never reduce their allocated space.
1419 Normally this is the best policy, since it avoids frequent reallocation.
1420 Applications that need to return memory to the heap at some particular
1421 point can use `mpz_realloc2', or clear variables no longer needed.
1422
1423    `mpf_t' variables, in the current implementation, use a fixed amount
1424 of space, determined by the chosen precision and allocated at
1425 initialization, so their size doesn't change.
1426
1427    All memory is allocated using `malloc' and friends by default, but
1428 this can be changed, see *Note Custom Allocation::.  Temporary memory
1429 on the stack is also used (via `alloca'), but this can be changed at
1430 build-time if desired, see *Note Build Options::.
1431
1432 \1f
1433 File: gmp.info,  Node: Reentrancy,  Next: Useful Macros and Constants,  Prev: Memory Management,  Up: GMP Basics
1434
1435 3.7 Reentrancy
1436 ==============
1437
1438 GMP is reentrant and thread-safe, with some exceptions:
1439
1440    * If configured with `--enable-alloca=malloc-notreentrant' (or with
1441      `--enable-alloca=notreentrant' when `alloca' is not available),
1442      then naturally GMP is not reentrant.
1443
1444    * `mpf_set_default_prec' and `mpf_init' use a global variable for the
1445      selected precision.  `mpf_init2' can be used instead, and in the
1446      C++ interface an explicit precision to the `mpf_class' constructor.
1447
1448    * `mpz_random' and the other old random number functions use a global
1449      random state and are hence not reentrant.  The newer random number
1450      functions that accept a `gmp_randstate_t' parameter can be used
1451      instead.
1452
1453    * `gmp_randinit' (obsolete) returns an error indication through a
1454      global variable, which is not thread safe.  Applications are
1455      advised to use `gmp_randinit_default' or `gmp_randinit_lc_2exp'
1456      instead.
1457
1458    * `mp_set_memory_functions' uses global variables to store the
1459      selected memory allocation functions.
1460
1461    * If the memory allocation functions set by a call to
1462      `mp_set_memory_functions' (or `malloc' and friends by default) are
1463      not reentrant, then GMP will not be reentrant either.
1464
1465    * If the standard I/O functions such as `fwrite' are not reentrant
1466      then the GMP I/O functions using them will not be reentrant either.
1467
1468    * It's safe for two threads to read from the same GMP variable
1469      simultaneously, but it's not safe for one to read while the
1470      another might be writing, nor for two threads to write
1471      simultaneously.  It's not safe for two threads to generate a
1472      random number from the same `gmp_randstate_t' simultaneously,
1473      since this involves an update of that variable.
1474
1475 \1f
1476 File: gmp.info,  Node: Useful Macros and Constants,  Next: Compatibility with older versions,  Prev: Reentrancy,  Up: GMP Basics
1477
1478 3.8 Useful Macros and Constants
1479 ===============================
1480
1481  -- Global Constant: const int mp_bits_per_limb
1482      The number of bits per limb.
1483
1484  -- Macro: __GNU_MP_VERSION
1485  -- Macro: __GNU_MP_VERSION_MINOR
1486  -- Macro: __GNU_MP_VERSION_PATCHLEVEL
1487      The major and minor GMP version, and patch level, respectively, as
1488      integers.  For GMP i.j, these numbers will be i, j, and 0,
1489      respectively.  For GMP i.j.k, these numbers will be i, j, and k,
1490      respectively.
1491
1492  -- Global Constant: const char * const gmp_version
1493      The GMP version number, as a null-terminated string, in the form
1494      "i.j.k".  This release is "5.0.1".  Note that the format "i.j" was
1495      used when k was zero was used before version 4.3.0.
1496
1497  -- Macro: __GMP_CC
1498  -- Macro: __GMP_CFLAGS
1499      The compiler and compiler flags, respectively, used when compiling
1500      GMP, as strings.
1501
1502 \1f
1503 File: gmp.info,  Node: Compatibility with older versions,  Next: Demonstration Programs,  Prev: Useful Macros and Constants,  Up: GMP Basics
1504
1505 3.9 Compatibility with older versions
1506 =====================================
1507
1508 This version of GMP is upwardly binary compatible with all 4.x and 3.x
1509 versions, and upwardly compatible at the source level with all 2.x
1510 versions, with the following exceptions.
1511
1512    * `mpn_gcd' had its source arguments swapped as of GMP 3.0, for
1513      consistency with other `mpn' functions.
1514
1515    * `mpf_get_prec' counted precision slightly differently in GMP 3.0
1516      and 3.0.1, but in 3.1 reverted to the 2.x style.
1517
1518    There are a number of compatibility issues between GMP 1 and GMP 2
1519 that of course also apply when porting applications from GMP 1 to GMP
1520 4.  Please see the GMP 2 manual for details.
1521
1522    The Berkeley MP compatibility library (*note BSD Compatible
1523 Functions::) is source and binary compatible with the standard `libmp'.
1524
1525 \1f
1526 File: gmp.info,  Node: Demonstration Programs,  Next: Efficiency,  Prev: Compatibility with older versions,  Up: GMP Basics
1527
1528 3.10 Demonstration programs
1529 ===========================
1530
1531 The `demos' subdirectory has some sample programs using GMP.  These
1532 aren't built or installed, but there's a `Makefile' with rules for them.
1533 For instance,
1534
1535      make pexpr
1536      ./pexpr 68^975+10
1537
1538 The following programs are provided
1539
1540    * `pexpr' is an expression evaluator, the program used on the GMP
1541      web page.
1542
1543    * The `calc' subdirectory has a similar but simpler evaluator using
1544      `lex' and `yacc'.
1545
1546    * The `expr' subdirectory is yet another expression evaluator, a
1547      library designed for ease of use within a C program.  See
1548      `demos/expr/README' for more information.
1549
1550    * `factorize' is a Pollard-Rho factorization program.
1551
1552    * `isprime' is a command-line interface to the `mpz_probab_prime_p'
1553      function.
1554
1555    * `primes' counts or lists primes in an interval, using a sieve.
1556
1557    * `qcn' is an example use of `mpz_kronecker_ui' to estimate quadratic
1558      class numbers.
1559
1560    * The `perl' subdirectory is a comprehensive perl interface to GMP.
1561      See `demos/perl/INSTALL' for more information.  Documentation is
1562      in POD format in `demos/perl/GMP.pm'.
1563
1564    As an aside, consideration has been given at various times to some
1565 sort of expression evaluation within the main GMP library.  Going
1566 beyond something minimal quickly leads to matters like user-defined
1567 functions, looping, fixnums for control variables, etc, which are
1568 considered outside the scope of GMP (much closer to language
1569 interpreters or compilers, *Note Language Bindings::.)  Something
1570 simple for program input convenience may yet be a possibility, a
1571 combination of the `expr' demo and the `pexpr' tree back-end perhaps.
1572 But for now the above evaluators are offered as illustrations.
1573
1574 \1f
1575 File: gmp.info,  Node: Efficiency,  Next: Debugging,  Prev: Demonstration Programs,  Up: GMP Basics
1576
1577 3.11 Efficiency
1578 ===============
1579
1580 Small Operands
1581      On small operands, the time for function call overheads and memory
1582      allocation can be significant in comparison to actual calculation.
1583      This is unavoidable in a general purpose variable precision
1584      library, although GMP attempts to be as efficient as it can on
1585      both large and small operands.
1586
1587 Static Linking
1588      On some CPUs, in particular the x86s, the static `libgmp.a' should
1589      be used for maximum speed, since the PIC code in the shared
1590      `libgmp.so' will have a small overhead on each function call and
1591      global data address.  For many programs this will be
1592      insignificant, but for long calculations there's a gain to be had.
1593
1594 Initializing and Clearing
1595      Avoid excessive initializing and clearing of variables, since this
1596      can be quite time consuming, especially in comparison to otherwise
1597      fast operations like addition.
1598
1599      A language interpreter might want to keep a free list or stack of
1600      initialized variables ready for use.  It should be possible to
1601      integrate something like that with a garbage collector too.
1602
1603 Reallocations
1604      An `mpz_t' or `mpq_t' variable used to hold successively increasing
1605      values will have its memory repeatedly `realloc'ed, which could be
1606      quite slow or could fragment memory, depending on the C library.
1607      If an application can estimate the final size then `mpz_init2' or
1608      `mpz_realloc2' can be called to allocate the necessary space from
1609      the beginning (*note Initializing Integers::).
1610
1611      It doesn't matter if a size set with `mpz_init2' or `mpz_realloc2'
1612      is too small, since all functions will do a further reallocation
1613      if necessary.  Badly overestimating memory required will waste
1614      space though.
1615
1616 `2exp' Functions
1617      It's up to an application to call functions like `mpz_mul_2exp'
1618      when appropriate.  General purpose functions like `mpz_mul' make
1619      no attempt to identify powers of two or other special forms,
1620      because such inputs will usually be very rare and testing every
1621      time would be wasteful.
1622
1623 `ui' and `si' Functions
1624      The `ui' functions and the small number of `si' functions exist for
1625      convenience and should be used where applicable.  But if for
1626      example an `mpz_t' contains a value that fits in an `unsigned
1627      long' there's no need extract it and call a `ui' function, just
1628      use the regular `mpz' function.
1629
1630 In-Place Operations
1631      `mpz_abs', `mpq_abs', `mpf_abs', `mpz_neg', `mpq_neg' and
1632      `mpf_neg' are fast when used for in-place operations like
1633      `mpz_abs(x,x)', since in the current implementation only a single
1634      field of `x' needs changing.  On suitable compilers (GCC for
1635      instance) this is inlined too.
1636
1637      `mpz_add_ui', `mpz_sub_ui', `mpf_add_ui' and `mpf_sub_ui' benefit
1638      from an in-place operation like `mpz_add_ui(x,x,y)', since usually
1639      only one or two limbs of `x' will need to be changed.  The same
1640      applies to the full precision `mpz_add' etc if `y' is small.  If
1641      `y' is big then cache locality may be helped, but that's all.
1642
1643      `mpz_mul' is currently the opposite, a separate destination is
1644      slightly better.  A call like `mpz_mul(x,x,y)' will, unless `y' is
1645      only one limb, make a temporary copy of `x' before forming the
1646      result.  Normally that copying will only be a tiny fraction of the
1647      time for the multiply, so this is not a particularly important
1648      consideration.
1649
1650      `mpz_set', `mpq_set', `mpq_set_num', `mpf_set', etc, make no
1651      attempt to recognise a copy of something to itself, so a call like
1652      `mpz_set(x,x)' will be wasteful.  Naturally that would never be
1653      written deliberately, but if it might arise from two pointers to
1654      the same object then a test to avoid it might be desirable.
1655
1656           if (x != y)
1657             mpz_set (x, y);
1658
1659      Note that it's never worth introducing extra `mpz_set' calls just
1660      to get in-place operations.  If a result should go to a particular
1661      variable then just direct it there and let GMP take care of data
1662      movement.
1663
1664 Divisibility Testing (Small Integers)
1665      `mpz_divisible_ui_p' and `mpz_congruent_ui_p' are the best
1666      functions for testing whether an `mpz_t' is divisible by an
1667      individual small integer.  They use an algorithm which is faster
1668      than `mpz_tdiv_ui', but which gives no useful information about
1669      the actual remainder, only whether it's zero (or a particular
1670      value).
1671
1672      However when testing divisibility by several small integers, it's
1673      best to take a remainder modulo their product, to save
1674      multi-precision operations.  For instance to test whether a number
1675      is divisible by any of 23, 29 or 31 take a remainder modulo
1676      23*29*31 = 20677 and then test that.
1677
1678      The division functions like `mpz_tdiv_q_ui' which give a quotient
1679      as well as a remainder are generally a little slower than the
1680      remainder-only functions like `mpz_tdiv_ui'.  If the quotient is
1681      only rarely wanted then it's probably best to just take a
1682      remainder and then go back and calculate the quotient if and when
1683      it's wanted (`mpz_divexact_ui' can be used if the remainder is
1684      zero).
1685
1686 Rational Arithmetic
1687      The `mpq' functions operate on `mpq_t' values with no common
1688      factors in the numerator and denominator.  Common factors are
1689      checked-for and cast out as necessary.  In general, cancelling
1690      factors every time is the best approach since it minimizes the
1691      sizes for subsequent operations.
1692
1693      However, applications that know something about the factorization
1694      of the values they're working with might be able to avoid some of
1695      the GCDs used for canonicalization, or swap them for divisions.
1696      For example when multiplying by a prime it's enough to check for
1697      factors of it in the denominator instead of doing a full GCD.  Or
1698      when forming a big product it might be known that very little
1699      cancellation will be possible, and so canonicalization can be left
1700      to the end.
1701
1702      The `mpq_numref' and `mpq_denref' macros give access to the
1703      numerator and denominator to do things outside the scope of the
1704      supplied `mpq' functions.  *Note Applying Integer Functions::.
1705
1706      The canonical form for rationals allows mixed-type `mpq_t' and
1707      integer additions or subtractions to be done directly with
1708      multiples of the denominator.  This will be somewhat faster than
1709      `mpq_add'.  For example,
1710
1711           /* mpq increment */
1712           mpz_add (mpq_numref(q), mpq_numref(q), mpq_denref(q));
1713
1714           /* mpq += unsigned long */
1715           mpz_addmul_ui (mpq_numref(q), mpq_denref(q), 123UL);
1716
1717           /* mpq -= mpz */
1718           mpz_submul (mpq_numref(q), mpq_denref(q), z);
1719
1720 Number Sequences
1721      Functions like `mpz_fac_ui', `mpz_fib_ui' and `mpz_bin_uiui' are
1722      designed for calculating isolated values.  If a range of values is
1723      wanted it's probably best to call to get a starting point and
1724      iterate from there.
1725
1726 Text Input/Output
1727      Hexadecimal or octal are suggested for input or output in text
1728      form.  Power-of-2 bases like these can be converted much more
1729      efficiently than other bases, like decimal.  For big numbers
1730      there's usually nothing of particular interest to be seen in the
1731      digits, so the base doesn't matter much.
1732
1733      Maybe we can hope octal will one day become the normal base for
1734      everyday use, as proposed by King Charles XII of Sweden and later
1735      reformers.
1736
1737 \1f
1738 File: gmp.info,  Node: Debugging,  Next: Profiling,  Prev: Efficiency,  Up: GMP Basics
1739
1740 3.12 Debugging
1741 ==============
1742
1743 Stack Overflow
1744      Depending on the system, a segmentation violation or bus error
1745      might be the only indication of stack overflow.  See
1746      `--enable-alloca' choices in *Note Build Options::, for how to
1747      address this.
1748
1749      In new enough versions of GCC, `-fstack-check' may be able to
1750      ensure an overflow is recognised by the system before too much
1751      damage is done, or `-fstack-limit-symbol' or
1752      `-fstack-limit-register' may be able to add checking if the system
1753      itself doesn't do any (*note Options for Code Generation:
1754      (gcc)Code Gen Options.).  These options must be added to the
1755      `CFLAGS' used in the GMP build (*note Build Options::), adding
1756      them just to an application will have no effect.  Note also
1757      they're a slowdown, adding overhead to each function call and each
1758      stack allocation.
1759
1760 Heap Problems
1761      The most likely cause of application problems with GMP is heap
1762      corruption.  Failing to `init' GMP variables will have
1763      unpredictable effects, and corruption arising elsewhere in a
1764      program may well affect GMP.  Initializing GMP variables more than
1765      once or failing to clear them will cause memory leaks.
1766
1767      In all such cases a `malloc' debugger is recommended.  On a GNU or
1768      BSD system the standard C library `malloc' has some diagnostic
1769      facilities, see *Note Allocation Debugging: (libc)Allocation
1770      Debugging, or `man 3 malloc'.  Other possibilities, in no
1771      particular order, include
1772
1773           `http://www.inf.ethz.ch/personal/biere/projects/ccmalloc/'
1774           `http://dmalloc.com/'
1775           `http://www.perens.com/FreeSoftware/'  (electric fence)
1776           `http://packages.debian.org/stable/devel/fda'
1777           `http://www.gnupdate.org/components/leakbug/'
1778           `http://people.redhat.com/~otaylor/memprof/'
1779           `http://www.cbmamiga.demon.co.uk/mpatrol/'
1780
1781      The GMP default allocation routines in `memory.c' also have a
1782      simple sentinel scheme which can be enabled with `#define DEBUG'
1783      in that file.  This is mainly designed for detecting buffer
1784      overruns during GMP development, but might find other uses.
1785
1786 Stack Backtraces
1787      On some systems the compiler options GMP uses by default can
1788      interfere with debugging.  In particular on x86 and 68k systems
1789      `-fomit-frame-pointer' is used and this generally inhibits stack
1790      backtracing.  Recompiling without such options may help while
1791      debugging, though the usual caveats about it potentially moving a
1792      memory problem or hiding a compiler bug will apply.
1793
1794 GDB, the GNU Debugger
1795      A sample `.gdbinit' is included in the distribution, showing how
1796      to call some undocumented dump functions to print GMP variables
1797      from within GDB.  Note that these functions shouldn't be used in
1798      final application code since they're undocumented and may be
1799      subject to incompatible changes in future versions of GMP.
1800
1801 Source File Paths
1802      GMP has multiple source files with the same name, in different
1803      directories.  For example `mpz', `mpq' and `mpf' each have an
1804      `init.c'.  If the debugger can't already determine the right one
1805      it may help to build with absolute paths on each C file.  One way
1806      to do that is to use a separate object directory with an absolute
1807      path to the source directory.
1808
1809           cd /my/build/dir
1810           /my/source/dir/gmp-5.0.1/configure
1811
1812      This works via `VPATH', and might require GNU `make'.  Alternately
1813      it might be possible to change the `.c.lo' rules appropriately.
1814
1815 Assertion Checking
1816      The build option `--enable-assert' is available to add some
1817      consistency checks to the library (see *Note Build Options::).
1818      These are likely to be of limited value to most applications.
1819      Assertion failures are just as likely to indicate memory
1820      corruption as a library or compiler bug.
1821
1822      Applications using the low-level `mpn' functions, however, will
1823      benefit from `--enable-assert' since it adds checks on the
1824      parameters of most such functions, many of which have subtle
1825      restrictions on their usage.  Note however that only the generic C
1826      code has checks, not the assembly code, so CPU `none' should be
1827      used for maximum checking.
1828
1829 Temporary Memory Checking
1830      The build option `--enable-alloca=debug' arranges that each block
1831      of temporary memory in GMP is allocated with a separate call to
1832      `malloc' (or the allocation function set with
1833      `mp_set_memory_functions').
1834
1835      This can help a malloc debugger detect accesses outside the
1836      intended bounds, or detect memory not released.  In a normal
1837      build, on the other hand, temporary memory is allocated in blocks
1838      which GMP divides up for its own use, or may be allocated with a
1839      compiler builtin `alloca' which will go nowhere near any malloc
1840      debugger hooks.
1841
1842 Maximum Debuggability
1843      To summarize the above, a GMP build for maximum debuggability
1844      would be
1845
1846           ./configure --disable-shared --enable-assert \
1847             --enable-alloca=debug --host=none CFLAGS=-g
1848
1849      For C++, add `--enable-cxx CXXFLAGS=-g'.
1850
1851 Checker
1852      The GCC checker (`http://savannah.nongnu.org/projects/checker/')
1853      can be used with GMP.  It contains a stub library which means GMP
1854      applications compiled with checker can use a normal GMP build.
1855
1856      A build of GMP with checking within GMP itself can be made.  This
1857      will run very very slowly.  On GNU/Linux for example,
1858
1859           ./configure --host=none-pc-linux-gnu CC=checkergcc
1860
1861      `--host=none' must be used, since the GMP assembly code doesn't
1862      support the checking scheme.  The GMP C++ features cannot be used,
1863      since current versions of checker (0.9.9.1) don't yet support the
1864      standard C++ library.
1865
1866 Valgrind
1867      The valgrind program (`http://valgrind.org/') is a memory checker
1868      for x86s.  It translates and emulates machine instructions to do
1869      strong checks for uninitialized data (at the level of individual
1870      bits), memory accesses through bad pointers, and memory leaks.
1871
1872      Recent versions of Valgrind are getting support for MMX and
1873      SSE/SSE2 instructions, for past versions GMP will need to be
1874      configured not to use those, ie. for an x86 without them (for
1875      instance plain `i486').
1876
1877 Other Problems
1878      Any suspected bug in GMP itself should be isolated to make sure
1879      it's not an application problem, see *Note Reporting Bugs::.
1880
1881 \1f
1882 File: gmp.info,  Node: Profiling,  Next: Autoconf,  Prev: Debugging,  Up: GMP Basics
1883
1884 3.13 Profiling
1885 ==============
1886
1887 Running a program under a profiler is a good way to find where it's
1888 spending most time and where improvements can be best sought.  The
1889 profiling choices for a GMP build are as follows.
1890
1891 `--disable-profiling'
1892      The default is to add nothing special for profiling.
1893
1894      It should be possible to just compile the mainline of a program
1895      with `-p' and use `prof' to get a profile consisting of
1896      timer-based sampling of the program counter.  Most of the GMP
1897      assembly code has the necessary symbol information.
1898
1899      This approach has the advantage of minimizing interference with
1900      normal program operation, but on most systems the resolution of
1901      the sampling is quite low (10 milliseconds for instance),
1902      requiring long runs to get accurate information.
1903
1904 `--enable-profiling=prof'
1905      Build with support for the system `prof', which means `-p' added
1906      to the `CFLAGS'.
1907
1908      This provides call counting in addition to program counter
1909      sampling, which allows the most frequently called routines to be
1910      identified, and an average time spent in each routine to be
1911      determined.
1912
1913      The x86 assembly code has support for this option, but on other
1914      processors the assembly routines will be as if compiled without
1915      `-p' and therefore won't appear in the call counts.
1916
1917      On some systems, such as GNU/Linux, `-p' in fact means `-pg' and in
1918      this case `--enable-profiling=gprof' described below should be used
1919      instead.
1920
1921 `--enable-profiling=gprof'
1922      Build with support for `gprof', which means `-pg' added to the
1923      `CFLAGS'.
1924
1925      This provides call graph construction in addition to call counting
1926      and program counter sampling, which makes it possible to count
1927      calls coming from different locations.  For example the number of
1928      calls to `mpn_mul' from `mpz_mul' versus the number from
1929      `mpf_mul'.  The program counter sampling is still flat though, so
1930      only a total time in `mpn_mul' would be accumulated, not a
1931      separate amount for each call site.
1932
1933      The x86 assembly code has support for this option, but on other
1934      processors the assembly routines will be as if compiled without
1935      `-pg' and therefore not be included in the call counts.
1936
1937      On x86 and m68k systems `-pg' and `-fomit-frame-pointer' are
1938      incompatible, so the latter is omitted from the default flags in
1939      that case, which might result in poorer code generation.
1940
1941      Incidentally, it should be possible to use the `gprof' program
1942      with a plain `--enable-profiling=prof' build.  But in that case
1943      only the `gprof -p' flat profile and call counts can be expected
1944      to be valid, not the `gprof -q' call graph.
1945
1946 `--enable-profiling=instrument'
1947      Build with the GCC option `-finstrument-functions' added to the
1948      `CFLAGS' (*note Options for Code Generation: (gcc)Code Gen
1949      Options.).
1950
1951      This inserts special instrumenting calls at the start and end of
1952      each function, allowing exact timing and full call graph
1953      construction.
1954
1955      This instrumenting is not normally a standard system feature and
1956      will require support from an external library, such as
1957
1958           `http://sourceforge.net/projects/fnccheck/'
1959
1960      This should be included in `LIBS' during the GMP configure so that
1961      test programs will link.  For example,
1962
1963           ./configure --enable-profiling=instrument LIBS=-lfc
1964
1965      On a GNU system the C library provides dummy instrumenting
1966      functions, so programs compiled with this option will link.  In
1967      this case it's only necessary to ensure the correct library is
1968      added when linking an application.
1969
1970      The x86 assembly code supports this option, but on other
1971      processors the assembly routines will be as if compiled without
1972      `-finstrument-functions' meaning time spent in them will
1973      effectively be attributed to their caller.
1974
1975 \1f
1976 File: gmp.info,  Node: Autoconf,  Next: Emacs,  Prev: Profiling,  Up: GMP Basics
1977
1978 3.14 Autoconf
1979 =============
1980
1981 Autoconf based applications can easily check whether GMP is installed.
1982 The only thing to be noted is that GMP library symbols from version 3
1983 onwards have prefixes like `__gmpz'.  The following therefore would be
1984 a simple test,
1985
1986      AC_CHECK_LIB(gmp, __gmpz_init)
1987
1988    This just uses the default `AC_CHECK_LIB' actions for found or not
1989 found, but an application that must have GMP would want to generate an
1990 error if not found.  For example,
1991
1992      AC_CHECK_LIB(gmp, __gmpz_init, ,
1993        [AC_MSG_ERROR([GNU MP not found, see http://gmplib.org/])])
1994
1995    If functions added in some particular version of GMP are required,
1996 then one of those can be used when checking.  For example `mpz_mul_si'
1997 was added in GMP 3.1,
1998
1999      AC_CHECK_LIB(gmp, __gmpz_mul_si, ,
2000        [AC_MSG_ERROR(
2001        [GNU MP not found, or not 3.1 or up, see http://gmplib.org/])])
2002
2003    An alternative would be to test the version number in `gmp.h' using
2004 say `AC_EGREP_CPP'.  That would make it possible to test the exact
2005 version, if some particular sub-minor release is known to be necessary.
2006
2007    In general it's recommended that applications should simply demand a
2008 new enough GMP rather than trying to provide supplements for features
2009 not available in past versions.
2010
2011    Occasionally an application will need or want to know the size of a
2012 type at configuration or preprocessing time, not just with `sizeof' in
2013 the code.  This can be done in the normal way with `mp_limb_t' etc, but
2014 GMP 4.0 or up is best for this, since prior versions needed certain
2015 `-D' defines on systems using a `long long' limb.  The following would
2016 suit Autoconf 2.50 or up,
2017
2018      AC_CHECK_SIZEOF(mp_limb_t, , [#include <gmp.h>])
2019
2020 \1f
2021 File: gmp.info,  Node: Emacs,  Prev: Autoconf,  Up: GMP Basics
2022
2023 3.15 Emacs
2024 ==========
2025
2026 <C-h C-i> (`info-lookup-symbol') is a good way to find documentation on
2027 C functions while editing (*note Info Documentation Lookup: (emacs)Info
2028 Lookup.).
2029
2030    The GMP manual can be included in such lookups by putting the
2031 following in your `.emacs',
2032
2033      (eval-after-load "info-look"
2034        '(let ((mode-value (assoc 'c-mode (assoc 'symbol info-lookup-alist))))
2035           (setcar (nthcdr 3 mode-value)
2036                   (cons '("(gmp)Function Index" nil "^ -.* " "\\>")
2037                         (nth 3 mode-value)))))
2038
2039 \1f
2040 File: gmp.info,  Node: Reporting Bugs,  Next: Integer Functions,  Prev: GMP Basics,  Up: Top
2041
2042 4 Reporting Bugs
2043 ****************
2044
2045 If you think you have found a bug in the GMP library, please
2046 investigate it and report it.  We have made this library available to
2047 you, and it is not too much to ask you to report the bugs you find.
2048
2049    Before you report a bug, check it's not already addressed in *Note
2050 Known Build Problems::, or perhaps *Note Notes for Particular
2051 Systems::.  You may also want to check `http://gmplib.org/' for patches
2052 for this release.
2053
2054    Please include the following in any report,
2055
2056    * The GMP version number, and if pre-packaged or patched then say so.
2057
2058    * A test program that makes it possible for us to reproduce the bug.
2059      Include instructions on how to run the program.
2060
2061    * A description of what is wrong.  If the results are incorrect, in
2062      what way.  If you get a crash, say so.
2063
2064    * If you get a crash, include a stack backtrace from the debugger if
2065      it's informative (`where' in `gdb', or `$C' in `adb').
2066
2067    * Please do not send core dumps, executables or `strace's.
2068
2069    * The configuration options you used when building GMP, if any.
2070
2071    * The name of the compiler and its version.  For `gcc', get the
2072      version with `gcc -v', otherwise perhaps `what `which cc`', or
2073      similar.
2074
2075    * The output from running `uname -a'.
2076
2077    * The output from running `./config.guess', and from running
2078      `./configfsf.guess' (might be the same).
2079
2080    * If the bug is related to `configure', then the compressed contents
2081      of `config.log'.
2082
2083    * If the bug is related to an `asm' file not assembling, then the
2084      contents of `config.m4' and the offending line or lines from the
2085      temporary `mpn/tmp-<file>.s'.
2086
2087    Please make an effort to produce a self-contained report, with
2088 something definite that can be tested or debugged.  Vague queries or
2089 piecemeal messages are difficult to act on and don't help the
2090 development effort.
2091
2092    It is not uncommon that an observed problem is actually due to a bug
2093 in the compiler; the GMP code tends to explore interesting corners in
2094 compilers.
2095
2096    If your bug report is good, we will do our best to help you get a
2097 corrected version of the library; if the bug report is poor, we won't
2098 do anything about it (except maybe ask you to send a better report).
2099
2100    Send your report to: <gmp-bugs@gmplib.org>.
2101
2102    If you think something in this manual is unclear, or downright
2103 incorrect, or if the language needs to be improved, please send a note
2104 to the same address.
2105
2106 \1f
2107 File: gmp.info,  Node: Integer Functions,  Next: Rational Number Functions,  Prev: Reporting Bugs,  Up: Top
2108
2109 5 Integer Functions
2110 *******************
2111
2112 This chapter describes the GMP functions for performing integer
2113 arithmetic.  These functions start with the prefix `mpz_'.
2114
2115    GMP integers are stored in objects of type `mpz_t'.
2116
2117 * Menu:
2118
2119 * Initializing Integers::
2120 * Assigning Integers::
2121 * Simultaneous Integer Init & Assign::
2122 * Converting Integers::
2123 * Integer Arithmetic::
2124 * Integer Division::
2125 * Integer Exponentiation::
2126 * Integer Roots::
2127 * Number Theoretic Functions::
2128 * Integer Comparisons::
2129 * Integer Logic and Bit Fiddling::
2130 * I/O of Integers::
2131 * Integer Random Numbers::
2132 * Integer Import and Export::
2133 * Miscellaneous Integer Functions::
2134 * Integer Special Functions::
2135
2136 \1f
2137 File: gmp.info,  Node: Initializing Integers,  Next: Assigning Integers,  Prev: Integer Functions,  Up: Integer Functions
2138
2139 5.1 Initialization Functions
2140 ============================
2141
2142 The functions for integer arithmetic assume that all integer objects are
2143 initialized.  You do that by calling the function `mpz_init'.  For
2144 example,
2145
2146      {
2147        mpz_t integ;
2148        mpz_init (integ);
2149        ...
2150        mpz_add (integ, ...);
2151        ...
2152        mpz_sub (integ, ...);
2153
2154        /* Unless the program is about to exit, do ... */
2155        mpz_clear (integ);
2156      }
2157
2158    As you can see, you can store new values any number of times, once an
2159 object is initialized.
2160
2161  -- Function: void mpz_init (mpz_t X)
2162      Initialize X, and set its value to 0.
2163
2164  -- Function: void mpz_inits (mpz_t X, ...)
2165      Initialize a NULL-terminated list of `mpz_t' variables, and set
2166      their values to 0.
2167
2168  -- Function: void mpz_init2 (mpz_t X, mp_bitcnt_t N)
2169      Initialize X, with space for N-bit numbers, and set its value to 0.
2170      Calling this function instead of `mpz_init' or `mpz_inits' is never
2171      necessary; reallocation is handled automatically by GMP when
2172      needed.
2173
2174      N is only the initial space, X will grow automatically in the
2175      normal way, if necessary, for subsequent values stored.
2176      `mpz_init2' makes it possible to avoid such reallocations if a
2177      maximum size is known in advance.
2178
2179  -- Function: void mpz_clear (mpz_t X)
2180      Free the space occupied by X.  Call this function for all `mpz_t'
2181      variables when you are done with them.
2182
2183  -- Function: void mpz_clears (mpz_t X, ...)
2184      Free the space occupied by a NULL-terminated list of `mpz_t'
2185      variables.
2186
2187  -- Function: void mpz_realloc2 (mpz_t X, mp_bitcnt_t N)
2188      Change the space allocated for X to N bits.  The value in X is
2189      preserved if it fits, or is set to 0 if not.
2190
2191      Calling this function is never necessary; reallocation is handled
2192      automatically by GMP when needed.  But this function can be used
2193      to increase the space for a variable in order to avoid repeated
2194      automatic reallocations, or to decrease it to give memory back to
2195      the heap.
2196
2197 \1f
2198 File: gmp.info,  Node: Assigning Integers,  Next: Simultaneous Integer Init & Assign,  Prev: Initializing Integers,  Up: Integer Functions
2199
2200 5.2 Assignment Functions
2201 ========================
2202
2203 These functions assign new values to already initialized integers
2204 (*note Initializing Integers::).
2205
2206  -- Function: void mpz_set (mpz_t ROP, mpz_t OP)
2207  -- Function: void mpz_set_ui (mpz_t ROP, unsigned long int OP)
2208  -- Function: void mpz_set_si (mpz_t ROP, signed long int OP)
2209  -- Function: void mpz_set_d (mpz_t ROP, double OP)
2210  -- Function: void mpz_set_q (mpz_t ROP, mpq_t OP)
2211  -- Function: void mpz_set_f (mpz_t ROP, mpf_t OP)
2212      Set the value of ROP from OP.
2213
2214      `mpz_set_d', `mpz_set_q' and `mpz_set_f' truncate OP to make it an
2215      integer.
2216
2217  -- Function: int mpz_set_str (mpz_t ROP, char *STR, int BASE)
2218      Set the value of ROP from STR, a null-terminated C string in base
2219      BASE.  White space is allowed in the string, and is simply ignored.
2220
2221      The BASE may vary from 2 to 62, or if BASE is 0, then the leading
2222      characters are used: `0x' and `0X' for hexadecimal, `0b' and `0B'
2223      for binary, `0' for octal, or decimal otherwise.
2224
2225      For bases up to 36, case is ignored; upper-case and lower-case
2226      letters have the same value.  For bases 37 to 62, upper-case
2227      letter represent the usual 10..35 while lower-case letter
2228      represent 36..61.
2229
2230      This function returns 0 if the entire string is a valid number in
2231      base BASE.  Otherwise it returns -1.
2232
2233  -- Function: void mpz_swap (mpz_t ROP1, mpz_t ROP2)
2234      Swap the values ROP1 and ROP2 efficiently.
2235
2236 \1f
2237 File: gmp.info,  Node: Simultaneous Integer Init & Assign,  Next: Converting Integers,  Prev: Assigning Integers,  Up: Integer Functions
2238
2239 5.3 Combined Initialization and Assignment Functions
2240 ====================================================
2241
2242 For convenience, GMP provides a parallel series of initialize-and-set
2243 functions which initialize the output and then store the value there.
2244 These functions' names have the form `mpz_init_set...'
2245
2246    Here is an example of using one:
2247
2248      {
2249        mpz_t pie;
2250        mpz_init_set_str (pie, "3141592653589793238462643383279502884", 10);
2251        ...
2252        mpz_sub (pie, ...);
2253        ...
2254        mpz_clear (pie);
2255      }
2256
2257 Once the integer has been initialized by any of the `mpz_init_set...'
2258 functions, it can be used as the source or destination operand for the
2259 ordinary integer functions.  Don't use an initialize-and-set function
2260 on a variable already initialized!
2261
2262  -- Function: void mpz_init_set (mpz_t ROP, mpz_t OP)
2263  -- Function: void mpz_init_set_ui (mpz_t ROP, unsigned long int OP)
2264  -- Function: void mpz_init_set_si (mpz_t ROP, signed long int OP)
2265  -- Function: void mpz_init_set_d (mpz_t ROP, double OP)
2266      Initialize ROP with limb space and set the initial numeric value
2267      from OP.
2268
2269  -- Function: int mpz_init_set_str (mpz_t ROP, char *STR, int BASE)
2270      Initialize ROP and set its value like `mpz_set_str' (see its
2271      documentation above for details).
2272
2273      If the string is a correct base BASE number, the function returns
2274      0; if an error occurs it returns -1.  ROP is initialized even if
2275      an error occurs.  (I.e., you have to call `mpz_clear' for it.)
2276
2277 \1f
2278 File: gmp.info,  Node: Converting Integers,  Next: Integer Arithmetic,  Prev: Simultaneous Integer Init & Assign,  Up: Integer Functions
2279
2280 5.4 Conversion Functions
2281 ========================
2282
2283 This section describes functions for converting GMP integers to
2284 standard C types.  Functions for converting _to_ GMP integers are
2285 described in *Note Assigning Integers:: and *Note I/O of Integers::.
2286
2287  -- Function: unsigned long int mpz_get_ui (mpz_t OP)
2288      Return the value of OP as an `unsigned long'.
2289
2290      If OP is too big to fit an `unsigned long' then just the least
2291      significant bits that do fit are returned.  The sign of OP is
2292      ignored, only the absolute value is used.
2293
2294  -- Function: signed long int mpz_get_si (mpz_t OP)
2295      If OP fits into a `signed long int' return the value of OP.
2296      Otherwise return the least significant part of OP, with the same
2297      sign as OP.
2298
2299      If OP is too big to fit in a `signed long int', the returned
2300      result is probably not very useful.  To find out if the value will
2301      fit, use the function `mpz_fits_slong_p'.
2302
2303  -- Function: double mpz_get_d (mpz_t OP)
2304      Convert OP to a `double', truncating if necessary (ie. rounding
2305      towards zero).
2306
2307      If the exponent from the conversion is too big, the result is
2308      system dependent.  An infinity is returned where available.  A
2309      hardware overflow trap may or may not occur.
2310
2311  -- Function: double mpz_get_d_2exp (signed long int *EXP, mpz_t OP)
2312      Convert OP to a `double', truncating if necessary (ie. rounding
2313      towards zero), and returning the exponent separately.
2314
2315      The return value is in the range 0.5<=abs(D)<1 and the exponent is
2316      stored to `*EXP'.  D * 2^EXP is the (truncated) OP value.  If OP
2317      is zero, the return is 0.0 and 0 is stored to `*EXP'.
2318
2319      This is similar to the standard C `frexp' function (*note
2320      Normalization Functions: (libc)Normalization Functions.).
2321
2322  -- Function: char * mpz_get_str (char *STR, int BASE, mpz_t OP)
2323      Convert OP to a string of digits in base BASE.  The base argument
2324      may vary from 2 to 62 or from -2 to -36.
2325
2326      For BASE in the range 2..36, digits and lower-case letters are
2327      used; for -2..-36, digits and upper-case letters are used; for
2328      37..62, digits, upper-case letters, and lower-case letters (in
2329      that significance order) are used.
2330
2331      If STR is `NULL', the result string is allocated using the current
2332      allocation function (*note Custom Allocation::).  The block will be
2333      `strlen(str)+1' bytes, that being exactly enough for the string and
2334      null-terminator.
2335
2336      If STR is not `NULL', it should point to a block of storage large
2337      enough for the result, that being `mpz_sizeinbase (OP, BASE) + 2'.
2338      The two extra bytes are for a possible minus sign, and the
2339      null-terminator.
2340
2341      A pointer to the result string is returned, being either the
2342      allocated block, or the given STR.
2343
2344 \1f
2345 File: gmp.info,  Node: Integer Arithmetic,  Next: Integer Division,  Prev: Converting Integers,  Up: Integer Functions
2346
2347 5.5 Arithmetic Functions
2348 ========================
2349
2350  -- Function: void mpz_add (mpz_t ROP, mpz_t OP1, mpz_t OP2)
2351  -- Function: void mpz_add_ui (mpz_t ROP, mpz_t OP1, unsigned long int
2352           OP2)
2353      Set ROP to OP1 + OP2.
2354
2355  -- Function: void mpz_sub (mpz_t ROP, mpz_t OP1, mpz_t OP2)
2356  -- Function: void mpz_sub_ui (mpz_t ROP, mpz_t OP1, unsigned long int
2357           OP2)
2358  -- Function: void mpz_ui_sub (mpz_t ROP, unsigned long int OP1, mpz_t
2359           OP2)
2360      Set ROP to OP1 - OP2.
2361
2362  -- Function: void mpz_mul (mpz_t ROP, mpz_t OP1, mpz_t OP2)
2363  -- Function: void mpz_mul_si (mpz_t ROP, mpz_t OP1, long int OP2)
2364  -- Function: void mpz_mul_ui (mpz_t ROP, mpz_t OP1, unsigned long int
2365           OP2)
2366      Set ROP to OP1 times OP2.
2367
2368  -- Function: void mpz_addmul (mpz_t ROP, mpz_t OP1, mpz_t OP2)
2369  -- Function: void mpz_addmul_ui (mpz_t ROP, mpz_t OP1, unsigned long
2370           int OP2)
2371      Set ROP to ROP + OP1 times OP2.
2372
2373  -- Function: void mpz_submul (mpz_t ROP, mpz_t OP1, mpz_t OP2)
2374  -- Function: void mpz_submul_ui (mpz_t ROP, mpz_t OP1, unsigned long
2375           int OP2)
2376      Set ROP to ROP - OP1 times OP2.
2377
2378  -- Function: void mpz_mul_2exp (mpz_t ROP, mpz_t OP1, mp_bitcnt_t OP2)
2379      Set ROP to OP1 times 2 raised to OP2.  This operation can also be
2380      defined as a left shift by OP2 bits.
2381
2382  -- Function: void mpz_neg (mpz_t ROP, mpz_t OP)
2383      Set ROP to -OP.
2384
2385  -- Function: void mpz_abs (mpz_t ROP, mpz_t OP)
2386      Set ROP to the absolute value of OP.
2387
2388 \1f
2389 File: gmp.info,  Node: Integer Division,  Next: Integer Exponentiation,  Prev: Integer Arithmetic,  Up: Integer Functions
2390
2391 5.6 Division Functions
2392 ======================
2393
2394 Division is undefined if the divisor is zero.  Passing a zero divisor
2395 to the division or modulo functions (including the modular powering
2396 functions `mpz_powm' and `mpz_powm_ui'), will cause an intentional
2397 division by zero.  This lets a program handle arithmetic exceptions in
2398 these functions the same way as for normal C `int' arithmetic.
2399
2400  -- Function: void mpz_cdiv_q (mpz_t Q, mpz_t N, mpz_t D)
2401  -- Function: void mpz_cdiv_r (mpz_t R, mpz_t N, mpz_t D)
2402  -- Function: void mpz_cdiv_qr (mpz_t Q, mpz_t R, mpz_t N, mpz_t D)
2403  -- Function: unsigned long int mpz_cdiv_q_ui (mpz_t Q, mpz_t N,
2404           unsigned long int D)
2405  -- Function: unsigned long int mpz_cdiv_r_ui (mpz_t R, mpz_t N,
2406           unsigned long int D)
2407  -- Function: unsigned long int mpz_cdiv_qr_ui (mpz_t Q, mpz_t R,
2408           mpz_t N, unsigned long int D)
2409  -- Function: unsigned long int mpz_cdiv_ui (mpz_t N,
2410           unsigned long int D)
2411  -- Function: void mpz_cdiv_q_2exp (mpz_t Q, mpz_t N, mp_bitcnt_t B)
2412  -- Function: void mpz_cdiv_r_2exp (mpz_t R, mpz_t N, mp_bitcnt_t B)
2413
2414  -- Function: void mpz_fdiv_q (mpz_t Q, mpz_t N, mpz_t D)
2415  -- Function: void mpz_fdiv_r (mpz_t R, mpz_t N, mpz_t D)
2416  -- Function: void mpz_fdiv_qr (mpz_t Q, mpz_t R, mpz_t N, mpz_t D)
2417  -- Function: unsigned long int mpz_fdiv_q_ui (mpz_t Q, mpz_t N,
2418           unsigned long int D)
2419  -- Function: unsigned long int mpz_fdiv_r_ui (mpz_t R, mpz_t N,
2420           unsigned long int D)
2421  -- Function: unsigned long int mpz_fdiv_qr_ui (mpz_t Q, mpz_t R,
2422           mpz_t N, unsigned long int D)
2423  -- Function: unsigned long int mpz_fdiv_ui (mpz_t N,
2424           unsigned long int D)
2425  -- Function: void mpz_fdiv_q_2exp (mpz_t Q, mpz_t N, mp_bitcnt_t B)
2426  -- Function: void mpz_fdiv_r_2exp (mpz_t R, mpz_t N, mp_bitcnt_t B)
2427
2428  -- Function: void mpz_tdiv_q (mpz_t Q, mpz_t N, mpz_t D)
2429  -- Function: void mpz_tdiv_r (mpz_t R, mpz_t N, mpz_t D)
2430  -- Function: void mpz_tdiv_qr (mpz_t Q, mpz_t R, mpz_t N, mpz_t D)
2431  -- Function: unsigned long int mpz_tdiv_q_ui (mpz_t Q, mpz_t N,
2432           unsigned long int D)
2433  -- Function: unsigned long int mpz_tdiv_r_ui (mpz_t R, mpz_t N,
2434           unsigned long int D)
2435  -- Function: unsigned long int mpz_tdiv_qr_ui (mpz_t Q, mpz_t R,
2436           mpz_t N, unsigned long int D)
2437  -- Function: unsigned long int mpz_tdiv_ui (mpz_t N,
2438           unsigned long int D)
2439  -- Function: void mpz_tdiv_q_2exp (mpz_t Q, mpz_t N, mp_bitcnt_t B)
2440  -- Function: void mpz_tdiv_r_2exp (mpz_t R, mpz_t N, mp_bitcnt_t B)
2441
2442      Divide N by D, forming a quotient Q and/or remainder R.  For the
2443      `2exp' functions, D=2^B.  The rounding is in three styles, each
2444      suiting different applications.
2445
2446         * `cdiv' rounds Q up towards +infinity, and R will have the
2447           opposite sign to D.  The `c' stands for "ceil".
2448
2449         * `fdiv' rounds Q down towards -infinity, and R will have the
2450           same sign as D.  The `f' stands for "floor".
2451
2452         * `tdiv' rounds Q towards zero, and R will have the same sign
2453           as N.  The `t' stands for "truncate".
2454
2455      In all cases Q and R will satisfy N=Q*D+R, and R will satisfy
2456      0<=abs(R)<abs(D).
2457
2458      The `q' functions calculate only the quotient, the `r' functions
2459      only the remainder, and the `qr' functions calculate both.  Note
2460      that for `qr' the same variable cannot be passed for both Q and R,
2461      or results will be unpredictable.
2462
2463      For the `ui' variants the return value is the remainder, and in
2464      fact returning the remainder is all the `div_ui' functions do.  For
2465      `tdiv' and `cdiv' the remainder can be negative, so for those the
2466      return value is the absolute value of the remainder.
2467
2468      For the `2exp' variants the divisor is 2^B.  These functions are
2469      implemented as right shifts and bit masks, but of course they
2470      round the same as the other functions.
2471
2472      For positive N both `mpz_fdiv_q_2exp' and `mpz_tdiv_q_2exp' are
2473      simple bitwise right shifts.  For negative N, `mpz_fdiv_q_2exp' is
2474      effectively an arithmetic right shift treating N as twos complement
2475      the same as the bitwise logical functions do, whereas
2476      `mpz_tdiv_q_2exp' effectively treats N as sign and magnitude.
2477
2478  -- Function: void mpz_mod (mpz_t R, mpz_t N, mpz_t D)
2479  -- Function: unsigned long int mpz_mod_ui (mpz_t R, mpz_t N,
2480           unsigned long int D)
2481      Set R to N `mod' D.  The sign of the divisor is ignored; the
2482      result is always non-negative.
2483
2484      `mpz_mod_ui' is identical to `mpz_fdiv_r_ui' above, returning the
2485      remainder as well as setting R.  See `mpz_fdiv_ui' above if only
2486      the return value is wanted.
2487
2488  -- Function: void mpz_divexact (mpz_t Q, mpz_t N, mpz_t D)
2489  -- Function: void mpz_divexact_ui (mpz_t Q, mpz_t N, unsigned long D)
2490      Set Q to N/D.  These functions produce correct results only when
2491      it is known in advance that D divides N.
2492
2493      These routines are much faster than the other division functions,
2494      and are the best choice when exact division is known to occur, for
2495      example reducing a rational to lowest terms.
2496
2497  -- Function: int mpz_divisible_p (mpz_t N, mpz_t D)
2498  -- Function: int mpz_divisible_ui_p (mpz_t N, unsigned long int D)
2499  -- Function: int mpz_divisible_2exp_p (mpz_t N, mp_bitcnt_t B)
2500      Return non-zero if N is exactly divisible by D, or in the case of
2501      `mpz_divisible_2exp_p' by 2^B.
2502
2503      N is divisible by D if there exists an integer Q satisfying N =
2504      Q*D.  Unlike the other division functions, D=0 is accepted and
2505      following the rule it can be seen that only 0 is considered
2506      divisible by 0.
2507
2508  -- Function: int mpz_congruent_p (mpz_t N, mpz_t C, mpz_t D)
2509  -- Function: int mpz_congruent_ui_p (mpz_t N, unsigned long int C,
2510           unsigned long int D)
2511  -- Function: int mpz_congruent_2exp_p (mpz_t N, mpz_t C, mp_bitcnt_t B)
2512      Return non-zero if N is congruent to C modulo D, or in the case of
2513      `mpz_congruent_2exp_p' modulo 2^B.
2514
2515      N is congruent to C mod D if there exists an integer Q satisfying
2516      N = C + Q*D.  Unlike the other division functions, D=0 is accepted
2517      and following the rule it can be seen that N and C are considered
2518      congruent mod 0 only when exactly equal.
2519
2520 \1f
2521 File: gmp.info,  Node: Integer Exponentiation,  Next: Integer Roots,  Prev: Integer Division,  Up: Integer Functions
2522
2523 5.7 Exponentiation Functions
2524 ============================
2525
2526  -- Function: void mpz_powm (mpz_t ROP, mpz_t BASE, mpz_t EXP, mpz_t
2527           MOD)
2528  -- Function: void mpz_powm_ui (mpz_t ROP, mpz_t BASE, unsigned long
2529           int EXP, mpz_t MOD)
2530      Set ROP to (BASE raised to EXP) modulo MOD.
2531
2532      Negative EXP is supported if an inverse BASE^-1 mod MOD exists
2533      (see `mpz_invert' in *Note Number Theoretic Functions::).  If an
2534      inverse doesn't exist then a divide by zero is raised.
2535
2536  -- Function: void mpz_powm_sec (mpz_t ROP, mpz_t BASE, mpz_t EXP,
2537           mpz_t MOD)
2538      Set ROP to (BASE raised to EXP) modulo MOD.
2539
2540      It is required that EXP > 0 and that MOD is odd.
2541
2542      This function is designed to take the same time and have the same
2543      cache access patterns for any two same-size arguments, assuming
2544      that function arguments are placed at the same position and that
2545      the machine state is identical upon function entry.  This function
2546      is intended for cryptographic purposes, where resilience to
2547      side-channel attacks is desired.
2548
2549  -- Function: void mpz_pow_ui (mpz_t ROP, mpz_t BASE, unsigned long int
2550           EXP)
2551  -- Function: void mpz_ui_pow_ui (mpz_t ROP, unsigned long int BASE,
2552           unsigned long int EXP)
2553      Set ROP to BASE raised to EXP.  The case 0^0 yields 1.
2554
2555 \1f
2556 File: gmp.info,  Node: Integer Roots,  Next: Number Theoretic Functions,  Prev: Integer Exponentiation,  Up: Integer Functions
2557
2558 5.8 Root Extraction Functions
2559 =============================
2560
2561  -- Function: int mpz_root (mpz_t ROP, mpz_t OP, unsigned long int N)
2562      Set ROP to  the truncated integer part of the Nth root of OP.
2563      Return non-zero if the computation was exact, i.e., if OP is ROP
2564      to the Nth power.
2565
2566  -- Function: void mpz_rootrem (mpz_t ROOT, mpz_t REM, mpz_t U,
2567           unsigned long int N)
2568      Set ROOT to  the truncated integer part of the Nth root of U.  Set
2569      REM to the remainder, U-ROOT**N.
2570
2571  -- Function: void mpz_sqrt (mpz_t ROP, mpz_t OP)
2572      Set ROP to  the truncated integer part of the square root of OP.
2573
2574  -- Function: void mpz_sqrtrem (mpz_t ROP1, mpz_t ROP2, mpz_t OP)
2575      Set ROP1 to the truncated integer part of the square root of OP,
2576      like `mpz_sqrt'.  Set ROP2 to the remainder OP-ROP1*ROP1, which
2577      will be zero if OP is a perfect square.
2578
2579      If ROP1 and ROP2 are the same variable, the results are undefined.
2580
2581  -- Function: int mpz_perfect_power_p (mpz_t OP)
2582      Return non-zero if OP is a perfect power, i.e., if there exist
2583      integers A and B, with B>1, such that OP equals A raised to the
2584      power B.
2585
2586      Under this definition both 0 and 1 are considered to be perfect
2587      powers.  Negative values of OP are accepted, but of course can
2588      only be odd perfect powers.
2589
2590  -- Function: int mpz_perfect_square_p (mpz_t OP)
2591      Return non-zero if OP is a perfect square, i.e., if the square
2592      root of OP is an integer.  Under this definition both 0 and 1 are
2593      considered to be perfect squares.
2594
2595 \1f
2596 File: gmp.info,  Node: Number Theoretic Functions,  Next: Integer Comparisons,  Prev: Integer Roots,  Up: Integer Functions
2597
2598 5.9 Number Theoretic Functions
2599 ==============================
2600
2601  -- Function: int mpz_probab_prime_p (mpz_t N, int REPS)
2602      Determine whether N is prime.  Return 2 if N is definitely prime,
2603      return 1 if N is probably prime (without being certain), or return
2604      0 if N is definitely composite.
2605
2606      This function does some trial divisions, then some Miller-Rabin
2607      probabilistic primality tests.  REPS controls how many such tests
2608      are done, 5 to 10 is a reasonable number, more will reduce the
2609      chances of a composite being returned as "probably prime".
2610
2611      Miller-Rabin and similar tests can be more properly called
2612      compositeness tests.  Numbers which fail are known to be composite
2613      but those which pass might be prime or might be composite.  Only a
2614      few composites pass, hence those which pass are considered
2615      probably prime.
2616
2617  -- Function: void mpz_nextprime (mpz_t ROP, mpz_t OP)
2618      Set ROP to the next prime greater than OP.
2619
2620      This function uses a probabilistic algorithm to identify primes.
2621      For practical purposes it's adequate, the chance of a composite
2622      passing will be extremely small.
2623
2624  -- Function: void mpz_gcd (mpz_t ROP, mpz_t OP1, mpz_t OP2)
2625      Set ROP to the greatest common divisor of OP1 and OP2.  The result
2626      is always positive even if one or both input operands are negative.
2627
2628  -- Function: unsigned long int mpz_gcd_ui (mpz_t ROP, mpz_t OP1,
2629           unsigned long int OP2)
2630      Compute the greatest common divisor of OP1 and OP2.  If ROP is not
2631      `NULL', store the result there.
2632
2633      If the result is small enough to fit in an `unsigned long int', it
2634      is returned.  If the result does not fit, 0 is returned, and the
2635      result is equal to the argument OP1.  Note that the result will
2636      always fit if OP2 is non-zero.
2637
2638  -- Function: void mpz_gcdext (mpz_t G, mpz_t S, mpz_t T, mpz_t A,
2639           mpz_t B)
2640      Set G to the greatest common divisor of A and B, and in addition
2641      set S and T to coefficients satisfying A*S + B*T = G.  The value
2642      in G is always positive, even if one or both of A and B are
2643      negative.  The values in S and T are chosen such that abs(S) <=
2644      abs(B) and abs(T) <= abs(A).
2645
2646      If T is `NULL' then that value is not computed.
2647
2648  -- Function: void mpz_lcm (mpz_t ROP, mpz_t OP1, mpz_t OP2)
2649  -- Function: void mpz_lcm_ui (mpz_t ROP, mpz_t OP1, unsigned long OP2)
2650      Set ROP to the least common multiple of OP1 and OP2.  ROP is
2651      always positive, irrespective of the signs of OP1 and OP2.  ROP
2652      will be zero if either OP1 or OP2 is zero.
2653
2654  -- Function: int mpz_invert (mpz_t ROP, mpz_t OP1, mpz_t OP2)
2655      Compute the inverse of OP1 modulo OP2 and put the result in ROP.
2656      If the inverse exists, the return value is non-zero and ROP will
2657      satisfy 0 <= ROP < OP2.  If an inverse doesn't exist the return
2658      value is zero and ROP is undefined.
2659
2660  -- Function: int mpz_jacobi (mpz_t A, mpz_t B)
2661      Calculate the Jacobi symbol (A/B).  This is defined only for B odd.
2662
2663  -- Function: int mpz_legendre (mpz_t A, mpz_t P)
2664      Calculate the Legendre symbol (A/P).  This is defined only for P
2665      an odd positive prime, and for such P it's identical to the Jacobi
2666      symbol.
2667
2668  -- Function: int mpz_kronecker (mpz_t A, mpz_t B)
2669  -- Function: int mpz_kronecker_si (mpz_t A, long B)
2670  -- Function: int mpz_kronecker_ui (mpz_t A, unsigned long B)
2671  -- Function: int mpz_si_kronecker (long A, mpz_t B)
2672  -- Function: int mpz_ui_kronecker (unsigned long A, mpz_t B)
2673      Calculate the Jacobi symbol (A/B) with the Kronecker extension
2674      (a/2)=(2/a) when a odd, or (a/2)=0 when a even.
2675
2676      When B is odd the Jacobi symbol and Kronecker symbol are
2677      identical, so `mpz_kronecker_ui' etc can be used for mixed
2678      precision Jacobi symbols too.
2679
2680      For more information see Henri Cohen section 1.4.2 (*note
2681      References::), or any number theory textbook.  See also the
2682      example program `demos/qcn.c' which uses `mpz_kronecker_ui'.
2683
2684  -- Function: mp_bitcnt_t mpz_remove (mpz_t ROP, mpz_t OP, mpz_t F)
2685      Remove all occurrences of the factor F from OP and store the
2686      result in ROP.  The return value is how many such occurrences were
2687      removed.
2688
2689  -- Function: void mpz_fac_ui (mpz_t ROP, unsigned long int OP)
2690      Set ROP to OP!, the factorial of OP.
2691
2692  -- Function: void mpz_bin_ui (mpz_t ROP, mpz_t N, unsigned long int K)
2693  -- Function: void mpz_bin_uiui (mpz_t ROP, unsigned long int N,
2694           unsigned long int K)
2695      Compute the binomial coefficient N over K and store the result in
2696      ROP.  Negative values of N are supported by `mpz_bin_ui', using
2697      the identity bin(-n,k) = (-1)^k * bin(n+k-1,k), see Knuth volume 1
2698      section 1.2.6 part G.
2699
2700  -- Function: void mpz_fib_ui (mpz_t FN, unsigned long int N)
2701  -- Function: void mpz_fib2_ui (mpz_t FN, mpz_t FNSUB1, unsigned long
2702           int N)
2703      `mpz_fib_ui' sets FN to to F[n], the N'th Fibonacci number.
2704      `mpz_fib2_ui' sets FN to F[n], and FNSUB1 to F[n-1].
2705
2706      These functions are designed for calculating isolated Fibonacci
2707      numbers.  When a sequence of values is wanted it's best to start
2708      with `mpz_fib2_ui' and iterate the defining F[n+1]=F[n]+F[n-1] or
2709      similar.
2710
2711  -- Function: void mpz_lucnum_ui (mpz_t LN, unsigned long int N)
2712  -- Function: void mpz_lucnum2_ui (mpz_t LN, mpz_t LNSUB1, unsigned
2713           long int N)
2714      `mpz_lucnum_ui' sets LN to to L[n], the N'th Lucas number.
2715      `mpz_lucnum2_ui' sets LN to L[n], and LNSUB1 to L[n-1].
2716
2717      These functions are designed for calculating isolated Lucas
2718      numbers.  When a sequence of values is wanted it's best to start
2719      with `mpz_lucnum2_ui' and iterate the defining L[n+1]=L[n]+L[n-1]
2720      or similar.
2721
2722      The Fibonacci numbers and Lucas numbers are related sequences, so
2723      it's never necessary to call both `mpz_fib2_ui' and
2724      `mpz_lucnum2_ui'.  The formulas for going from Fibonacci to Lucas
2725      can be found in *Note Lucas Numbers Algorithm::, the reverse is
2726      straightforward too.
2727
2728 \1f
2729 File: gmp.info,  Node: Integer Comparisons,  Next: Integer Logic and Bit Fiddling,  Prev: Number Theoretic Functions,  Up: Integer Functions
2730
2731 5.10 Comparison Functions
2732 =========================
2733
2734  -- Function: int mpz_cmp (mpz_t OP1, mpz_t OP2)
2735  -- Function: int mpz_cmp_d (mpz_t OP1, double OP2)
2736  -- Macro: int mpz_cmp_si (mpz_t OP1, signed long int OP2)
2737  -- Macro: int mpz_cmp_ui (mpz_t OP1, unsigned long int OP2)
2738      Compare OP1 and OP2.  Return a positive value if OP1 > OP2, zero
2739      if OP1 = OP2, or a negative value if OP1 < OP2.
2740
2741      `mpz_cmp_ui' and `mpz_cmp_si' are macros and will evaluate their
2742      arguments more than once.  `mpz_cmp_d' can be called with an
2743      infinity, but results are undefined for a NaN.
2744
2745  -- Function: int mpz_cmpabs (mpz_t OP1, mpz_t OP2)
2746  -- Function: int mpz_cmpabs_d (mpz_t OP1, double OP2)
2747  -- Function: int mpz_cmpabs_ui (mpz_t OP1, unsigned long int OP2)
2748      Compare the absolute values of OP1 and OP2.  Return a positive
2749      value if abs(OP1) > abs(OP2), zero if abs(OP1) = abs(OP2), or a
2750      negative value if abs(OP1) < abs(OP2).
2751
2752      `mpz_cmpabs_d' can be called with an infinity, but results are
2753      undefined for a NaN.
2754
2755  -- Macro: int mpz_sgn (mpz_t OP)
2756      Return +1 if OP > 0, 0 if OP = 0, and -1 if OP < 0.
2757
2758      This function is actually implemented as a macro.  It evaluates
2759      its argument multiple times.
2760
2761 \1f
2762 File: gmp.info,  Node: Integer Logic and Bit Fiddling,  Next: I/O of Integers,  Prev: Integer Comparisons,  Up: Integer Functions
2763
2764 5.11 Logical and Bit Manipulation Functions
2765 ===========================================
2766
2767 These functions behave as if twos complement arithmetic were used
2768 (although sign-magnitude is the actual implementation).  The least
2769 significant bit is number 0.
2770
2771  -- Function: void mpz_and (mpz_t ROP, mpz_t OP1, mpz_t OP2)
2772      Set ROP to OP1 bitwise-and OP2.
2773
2774  -- Function: void mpz_ior (mpz_t ROP, mpz_t OP1, mpz_t OP2)
2775      Set ROP to OP1 bitwise inclusive-or OP2.
2776
2777  -- Function: void mpz_xor (mpz_t ROP, mpz_t OP1, mpz_t OP2)
2778      Set ROP to OP1 bitwise exclusive-or OP2.
2779
2780  -- Function: void mpz_com (mpz_t ROP, mpz_t OP)
2781      Set ROP to the one's complement of OP.
2782
2783  -- Function: mp_bitcnt_t mpz_popcount (mpz_t OP)
2784      If OP>=0, return the population count of OP, which is the number
2785      of 1 bits in the binary representation.  If OP<0, the number of 1s
2786      is infinite, and the return value is the largest possible
2787      `mp_bitcnt_t'.
2788
2789  -- Function: mp_bitcnt_t mpz_hamdist (mpz_t OP1, mpz_t OP2)
2790      If OP1 and OP2 are both >=0 or both <0, return the hamming
2791      distance between the two operands, which is the number of bit
2792      positions where OP1 and OP2 have different bit values.  If one
2793      operand is >=0 and the other <0 then the number of bits different
2794      is infinite, and the return value is the largest possible
2795      `mp_bitcnt_t'.
2796
2797  -- Function: mp_bitcnt_t mpz_scan0 (mpz_t OP, mp_bitcnt_t STARTING_BIT)
2798  -- Function: mp_bitcnt_t mpz_scan1 (mpz_t OP, mp_bitcnt_t STARTING_BIT)
2799      Scan OP, starting from bit STARTING_BIT, towards more significant
2800      bits, until the first 0 or 1 bit (respectively) is found.  Return
2801      the index of the found bit.
2802
2803      If the bit at STARTING_BIT is already what's sought, then
2804      STARTING_BIT is returned.
2805
2806      If there's no bit found, then the largest possible `mp_bitcnt_t' is
2807      returned.  This will happen in `mpz_scan0' past the end of a
2808      negative number, or `mpz_scan1' past the end of a nonnegative
2809      number.
2810
2811  -- Function: void mpz_setbit (mpz_t ROP, mp_bitcnt_t BIT_INDEX)
2812      Set bit BIT_INDEX in ROP.
2813
2814  -- Function: void mpz_clrbit (mpz_t ROP, mp_bitcnt_t BIT_INDEX)
2815      Clear bit BIT_INDEX in ROP.
2816
2817  -- Function: void mpz_combit (mpz_t ROP, mp_bitcnt_t BIT_INDEX)
2818      Complement bit BIT_INDEX in ROP.
2819
2820  -- Function: int mpz_tstbit (mpz_t OP, mp_bitcnt_t BIT_INDEX)
2821      Test bit BIT_INDEX in OP and return 0 or 1 accordingly.
2822
2823 \1f
2824 File: gmp.info,  Node: I/O of Integers,  Next: Integer Random Numbers,  Prev: Integer Logic and Bit Fiddling,  Up: Integer Functions
2825
2826 5.12 Input and Output Functions
2827 ===============================
2828
2829 Functions that perform input from a stdio stream, and functions that
2830 output to a stdio stream.  Passing a `NULL' pointer for a STREAM
2831 argument to any of these functions will make them read from `stdin' and
2832 write to `stdout', respectively.
2833
2834    When using any of these functions, it is a good idea to include
2835 `stdio.h' before `gmp.h', since that will allow `gmp.h' to define
2836 prototypes for these functions.
2837
2838  -- Function: size_t mpz_out_str (FILE *STREAM, int BASE, mpz_t OP)
2839      Output OP on stdio stream STREAM, as a string of digits in base
2840      BASE.  The base argument may vary from 2 to 62 or from -2 to -36.
2841
2842      For BASE in the range 2..36, digits and lower-case letters are
2843      used; for -2..-36, digits and upper-case letters are used; for
2844      37..62, digits, upper-case letters, and lower-case letters (in
2845      that significance order) are used.
2846
2847      Return the number of bytes written, or if an error occurred,
2848      return 0.
2849
2850  -- Function: size_t mpz_inp_str (mpz_t ROP, FILE *STREAM, int BASE)
2851      Input a possibly white-space preceded string in base BASE from
2852      stdio stream STREAM, and put the read integer in ROP.
2853
2854      The BASE may vary from 2 to 62, or if BASE is 0, then the leading
2855      characters are used: `0x' and `0X' for hexadecimal, `0b' and `0B'
2856      for binary, `0' for octal, or decimal otherwise.
2857
2858      For bases up to 36, case is ignored; upper-case and lower-case
2859      letters have the same value.  For bases 37 to 62, upper-case
2860      letter represent the usual 10..35 while lower-case letter
2861      represent 36..61.
2862
2863      Return the number of bytes read, or if an error occurred, return 0.
2864
2865  -- Function: size_t mpz_out_raw (FILE *STREAM, mpz_t OP)
2866      Output OP on stdio stream STREAM, in raw binary format.  The
2867      integer is written in a portable format, with 4 bytes of size
2868      information, and that many bytes of limbs.  Both the size and the
2869      limbs are written in decreasing significance order (i.e., in
2870      big-endian).
2871
2872      The output can be read with `mpz_inp_raw'.
2873
2874      Return the number of bytes written, or if an error occurred,
2875      return 0.
2876
2877      The output of this can not be read by `mpz_inp_raw' from GMP 1,
2878      because of changes necessary for compatibility between 32-bit and
2879      64-bit machines.
2880
2881  -- Function: size_t mpz_inp_raw (mpz_t ROP, FILE *STREAM)
2882      Input from stdio stream STREAM in the format written by
2883      `mpz_out_raw', and put the result in ROP.  Return the number of
2884      bytes read, or if an error occurred, return 0.
2885
2886      This routine can read the output from `mpz_out_raw' also from GMP
2887      1, in spite of changes necessary for compatibility between 32-bit
2888      and 64-bit machines.
2889
2890 \1f
2891 File: gmp.info,  Node: Integer Random Numbers,  Next: Integer Import and Export,  Prev: I/O of Integers,  Up: Integer Functions
2892
2893 5.13 Random Number Functions
2894 ============================
2895
2896 The random number functions of GMP come in two groups; older function
2897 that rely on a global state, and newer functions that accept a state
2898 parameter that is read and modified.  Please see the *Note Random
2899 Number Functions:: for more information on how to use and not to use
2900 random number functions.
2901
2902  -- Function: void mpz_urandomb (mpz_t ROP, gmp_randstate_t STATE,
2903           mp_bitcnt_t N)
2904      Generate a uniformly distributed random integer in the range 0 to
2905      2^N-1, inclusive.
2906
2907      The variable STATE must be initialized by calling one of the
2908      `gmp_randinit' functions (*Note Random State Initialization::)
2909      before invoking this function.
2910
2911  -- Function: void mpz_urandomm (mpz_t ROP, gmp_randstate_t STATE,
2912           mpz_t N)
2913      Generate a uniform random integer in the range 0 to N-1, inclusive.
2914
2915      The variable STATE must be initialized by calling one of the
2916      `gmp_randinit' functions (*Note Random State Initialization::)
2917      before invoking this function.
2918
2919  -- Function: void mpz_rrandomb (mpz_t ROP, gmp_randstate_t STATE,
2920           mp_bitcnt_t N)
2921      Generate a random integer with long strings of zeros and ones in
2922      the binary representation.  Useful for testing functions and
2923      algorithms, since this kind of random numbers have proven to be
2924      more likely to trigger corner-case bugs.  The random number will
2925      be in the range 0 to 2^N-1, inclusive.
2926
2927      The variable STATE must be initialized by calling one of the
2928      `gmp_randinit' functions (*Note Random State Initialization::)
2929      before invoking this function.
2930
2931  -- Function: void mpz_random (mpz_t ROP, mp_size_t MAX_SIZE)
2932      Generate a random integer of at most MAX_SIZE limbs.  The generated
2933      random number doesn't satisfy any particular requirements of
2934      randomness.  Negative random numbers are generated when MAX_SIZE
2935      is negative.
2936
2937      This function is obsolete.  Use `mpz_urandomb' or `mpz_urandomm'
2938      instead.
2939
2940  -- Function: void mpz_random2 (mpz_t ROP, mp_size_t MAX_SIZE)
2941      Generate a random integer of at most MAX_SIZE limbs, with long
2942      strings of zeros and ones in the binary representation.  Useful
2943      for testing functions and algorithms, since this kind of random
2944      numbers have proven to be more likely to trigger corner-case bugs.
2945      Negative random numbers are generated when MAX_SIZE is negative.
2946
2947      This function is obsolete.  Use `mpz_rrandomb' instead.
2948
2949 \1f
2950 File: gmp.info,  Node: Integer Import and Export,  Next: Miscellaneous Integer Functions,  Prev: Integer Random Numbers,  Up: Integer Functions
2951
2952 5.14 Integer Import and Export
2953 ==============================
2954
2955 `mpz_t' variables can be converted to and from arbitrary words of binary
2956 data with the following functions.
2957
2958  -- Function: void mpz_import (mpz_t ROP, size_t COUNT, int ORDER,
2959           size_t SIZE, int ENDIAN, size_t NAILS, const void *OP)
2960      Set ROP from an array of word data at OP.
2961
2962      The parameters specify the format of the data.  COUNT many words
2963      are read, each SIZE bytes.  ORDER can be 1 for most significant
2964      word first or -1 for least significant first.  Within each word
2965      ENDIAN can be 1 for most significant byte first, -1 for least
2966      significant first, or 0 for the native endianness of the host CPU.
2967      The most significant NAILS bits of each word are skipped, this
2968      can be 0 to use the full words.
2969
2970      There is no sign taken from the data, ROP will simply be a positive
2971      integer.  An application can handle any sign itself, and apply it
2972      for instance with `mpz_neg'.
2973
2974      There are no data alignment restrictions on OP, any address is
2975      allowed.
2976
2977      Here's an example converting an array of `unsigned long' data, most
2978      significant element first, and host byte order within each value.
2979
2980           unsigned long  a[20];
2981           /* Initialize Z and A */
2982           mpz_import (z, 20, 1, sizeof(a[0]), 0, 0, a);
2983
2984      This example assumes the full `sizeof' bytes are used for data in
2985      the given type, which is usually true, and certainly true for
2986      `unsigned long' everywhere we know of.  However on Cray vector
2987      systems it may be noted that `short' and `int' are always stored
2988      in 8 bytes (and with `sizeof' indicating that) but use only 32 or
2989      46 bits.  The NAILS feature can account for this, by passing for
2990      instance `8*sizeof(int)-INT_BIT'.
2991
2992  -- Function: void * mpz_export (void *ROP, size_t *COUNTP, int ORDER,
2993           size_t SIZE, int ENDIAN, size_t NAILS, mpz_t OP)
2994      Fill ROP with word data from OP.
2995
2996      The parameters specify the format of the data produced.  Each word
2997      will be SIZE bytes and ORDER can be 1 for most significant word
2998      first or -1 for least significant first.  Within each word ENDIAN
2999      can be 1 for most significant byte first, -1 for least significant
3000      first, or 0 for the native endianness of the host CPU.  The most
3001      significant NAILS bits of each word are unused and set to zero,
3002      this can be 0 to produce full words.
3003
3004      The number of words produced is written to `*COUNTP', or COUNTP
3005      can be `NULL' to discard the count.  ROP must have enough space
3006      for the data, or if ROP is `NULL' then a result array of the
3007      necessary size is allocated using the current GMP allocation
3008      function (*note Custom Allocation::).  In either case the return
3009      value is the destination used, either ROP or the allocated block.
3010
3011      If OP is non-zero then the most significant word produced will be
3012      non-zero.  If OP is zero then the count returned will be zero and
3013      nothing written to ROP.  If ROP is `NULL' in this case, no block
3014      is allocated, just `NULL' is returned.
3015
3016      The sign of OP is ignored, just the absolute value is exported.  An
3017      application can use `mpz_sgn' to get the sign and handle it as
3018      desired.  (*note Integer Comparisons::)
3019
3020      There are no data alignment restrictions on ROP, any address is
3021      allowed.
3022
3023      When an application is allocating space itself the required size
3024      can be determined with a calculation like the following.  Since
3025      `mpz_sizeinbase' always returns at least 1, `count' here will be
3026      at least one, which avoids any portability problems with
3027      `malloc(0)', though if `z' is zero no space at all is actually
3028      needed (or written).
3029
3030           numb = 8*size - nail;
3031           count = (mpz_sizeinbase (z, 2) + numb-1) / numb;
3032           p = malloc (count * size);
3033
3034 \1f
3035 File: gmp.info,  Node: Miscellaneous Integer Functions,  Next: Integer Special Functions,  Prev: Integer Import and Export,  Up: Integer Functions
3036
3037 5.15 Miscellaneous Functions
3038 ============================
3039
3040  -- Function: int mpz_fits_ulong_p (mpz_t OP)
3041  -- Function: int mpz_fits_slong_p (mpz_t OP)
3042  -- Function: int mpz_fits_uint_p (mpz_t OP)
3043  -- Function: int mpz_fits_sint_p (mpz_t OP)
3044  -- Function: int mpz_fits_ushort_p (mpz_t OP)
3045  -- Function: int mpz_fits_sshort_p (mpz_t OP)
3046      Return non-zero iff the value of OP fits in an `unsigned long int',
3047      `signed long int', `unsigned int', `signed int', `unsigned short
3048      int', or `signed short int', respectively.  Otherwise, return zero.
3049
3050  -- Macro: int mpz_odd_p (mpz_t OP)
3051  -- Macro: int mpz_even_p (mpz_t OP)
3052      Determine whether OP is odd or even, respectively.  Return
3053      non-zero if yes, zero if no.  These macros evaluate their argument
3054      more than once.
3055
3056  -- Function: size_t mpz_sizeinbase (mpz_t OP, int BASE)
3057      Return the size of OP measured in number of digits in the given
3058      BASE.  BASE can vary from 2 to 62.  The sign of OP is ignored,
3059      just the absolute value is used.  The result will be either exact
3060      or 1 too big.  If BASE is a power of 2, the result is always
3061      exact.  If OP is zero the return value is always 1.
3062
3063      This function can be used to determine the space required when
3064      converting OP to a string.  The right amount of allocation is
3065      normally two more than the value returned by `mpz_sizeinbase', one
3066      extra for a minus sign and one for the null-terminator.
3067
3068      It will be noted that `mpz_sizeinbase(OP,2)' can be used to locate
3069      the most significant 1 bit in OP, counting from 1.  (Unlike the
3070      bitwise functions which start from 0, *Note Logical and Bit
3071      Manipulation Functions: Integer Logic and Bit Fiddling.)
3072
3073 \1f
3074 File: gmp.info,  Node: Integer Special Functions,  Prev: Miscellaneous Integer Functions,  Up: Integer Functions
3075
3076 5.16 Special Functions
3077 ======================
3078
3079 The functions in this section are for various special purposes.  Most
3080 applications will not need them.
3081
3082  -- Function: void mpz_array_init (mpz_t INTEGER_ARRAY, mp_size_t
3083           ARRAY_SIZE, mp_size_t FIXED_NUM_BITS)
3084      This is a special type of initialization.  *Fixed* space of
3085      FIXED_NUM_BITS is allocated to each of the ARRAY_SIZE integers in
3086      INTEGER_ARRAY.  There is no way to free the storage allocated by
3087      this function.  Don't call `mpz_clear'!
3088
3089      The INTEGER_ARRAY parameter is the first `mpz_t' in the array.  For
3090      example,
3091
3092           mpz_t  arr[20000];
3093           mpz_array_init (arr[0], 20000, 512);
3094
3095      This function is only intended for programs that create a large
3096      number of integers and need to reduce memory usage by avoiding the
3097      overheads of allocating and reallocating lots of small blocks.  In
3098      normal programs this function is not recommended.
3099
3100      The space allocated to each integer by this function will not be
3101      automatically increased, unlike the normal `mpz_init', so an
3102      application must ensure it is sufficient for any value stored.
3103      The following space requirements apply to various routines,
3104
3105         * `mpz_abs', `mpz_neg', `mpz_set', `mpz_set_si' and
3106           `mpz_set_ui' need room for the value they store.
3107
3108         * `mpz_add', `mpz_add_ui', `mpz_sub' and `mpz_sub_ui' need room
3109           for the larger of the two operands, plus an extra
3110           `mp_bits_per_limb'.
3111
3112         * `mpz_mul', `mpz_mul_ui' and `mpz_mul_ui' need room for the sum
3113           of the number of bits in their operands, but each rounded up
3114           to a multiple of `mp_bits_per_limb'.
3115
3116         * `mpz_swap' can be used between two array variables, but not
3117           between an array and a normal variable.
3118
3119      For other functions, or if in doubt, the suggestion is to
3120      calculate in a regular `mpz_init' variable and copy the result to
3121      an array variable with `mpz_set'.
3122
3123  -- Function: void * _mpz_realloc (mpz_t INTEGER, mp_size_t NEW_ALLOC)
3124      Change the space for INTEGER to NEW_ALLOC limbs.  The value in
3125      INTEGER is preserved if it fits, or is set to 0 if not.  The return
3126      value is not useful to applications and should be ignored.
3127
3128      `mpz_realloc2' is the preferred way to accomplish allocation
3129      changes like this.  `mpz_realloc2' and `_mpz_realloc' are the same
3130      except that `_mpz_realloc' takes its size in limbs.
3131
3132  -- Function: mp_limb_t mpz_getlimbn (mpz_t OP, mp_size_t N)
3133      Return limb number N from OP.  The sign of OP is ignored, just the
3134      absolute value is used.  The least significant limb is number 0.
3135
3136      `mpz_size' can be used to find how many limbs make up OP.
3137      `mpz_getlimbn' returns zero if N is outside the range 0 to
3138      `mpz_size(OP)-1'.
3139
3140  -- Function: size_t mpz_size (mpz_t OP)
3141      Return the size of OP measured in number of limbs.  If OP is zero,
3142      the returned value will be zero.
3143
3144 \1f
3145 File: gmp.info,  Node: Rational Number Functions,  Next: Floating-point Functions,  Prev: Integer Functions,  Up: Top
3146
3147 6 Rational Number Functions
3148 ***************************
3149
3150 This chapter describes the GMP functions for performing arithmetic on
3151 rational numbers.  These functions start with the prefix `mpq_'.
3152
3153    Rational numbers are stored in objects of type `mpq_t'.
3154
3155    All rational arithmetic functions assume operands have a canonical
3156 form, and canonicalize their result.  The canonical from means that the
3157 denominator and the numerator have no common factors, and that the
3158 denominator is positive.  Zero has the unique representation 0/1.
3159
3160    Pure assignment functions do not canonicalize the assigned variable.
3161 It is the responsibility of the user to canonicalize the assigned
3162 variable before any arithmetic operations are performed on that
3163 variable.
3164
3165  -- Function: void mpq_canonicalize (mpq_t OP)
3166      Remove any factors that are common to the numerator and
3167      denominator of OP, and make the denominator positive.
3168
3169 * Menu:
3170
3171 * Initializing Rationals::
3172 * Rational Conversions::
3173 * Rational Arithmetic::
3174 * Comparing Rationals::
3175 * Applying Integer Functions::
3176 * I/O of Rationals::
3177
3178 \1f
3179 File: gmp.info,  Node: Initializing Rationals,  Next: Rational Conversions,  Prev: Rational Number Functions,  Up: Rational Number Functions
3180
3181 6.1 Initialization and Assignment Functions
3182 ===========================================