Annotation of OpenXM_contrib/gmp/gmp.info-2, Revision 1.1.1.4
1.1.1.4 ! ohara 1: This is gmp.info, produced by makeinfo version 4.2 from gmp.texi.
1.1 maekawa 2:
1.1.1.4 ! ohara 3: This manual describes how to install and use the GNU multiple precision
! 4: arithmetic library, version 4.1.2.
! 5:
! 6: Copyright 1991, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
! 7: 2001, 2002 Free Software Foundation, Inc.
! 8:
! 9: Permission is granted to copy, distribute and/or modify this
! 10: document under the terms of the GNU Free Documentation License, Version
! 11: 1.1 or any later version published by the Free Software Foundation;
! 12: with no Invariant Sections, with the Front-Cover Texts being "A GNU
! 13: Manual", and with the Back-Cover Texts being "You have freedom to copy
! 14: and modify this GNU Manual, like GNU software". A copy of the license
! 15: is included in *Note GNU Free Documentation License::.
1.1.1.2 maekawa 16: INFO-DIR-SECTION GNU libraries
1.1 maekawa 17: START-INFO-DIR-ENTRY
1.1.1.2 maekawa 18: * gmp: (gmp). GNU Multiple Precision Arithmetic Library.
1.1 maekawa 19: END-INFO-DIR-ENTRY
20:
1.1.1.2 maekawa 21:
1.1.1.4 ! ohara 22: File: gmp.info, Node: Parameter Conventions, Next: Memory Management, Prev: Variable Conventions, Up: GMP Basics
1.1.1.2 maekawa 23:
1.1.1.4 ! ohara 24: Parameter Conventions
! 25: =====================
1.1.1.2 maekawa 26:
1.1.1.4 ! ohara 27: When a GMP variable is used as a function parameter, it's
! 28: effectively a call-by-reference, meaning if the function stores a value
! 29: there it will change the original in the caller. Parameters which are
! 30: input-only can be designated `const' to provoke a compiler error or
! 31: warning on attempting to modify them.
! 32:
! 33: When a function is going to return a GMP result, it should designate
! 34: a parameter that it sets, like the library functions do. More than one
! 35: value can be returned by having more than one output parameter, again
! 36: like the library functions. A `return' of an `mpz_t' etc doesn't
! 37: return the object, only a pointer, and this is almost certainly not
! 38: what's wanted.
1.1.1.2 maekawa 39:
1.1.1.4 ! ohara 40: Here's an example accepting an `mpz_t' parameter, doing a
! 41: calculation, and storing the result to the indicated parameter.
1.1.1.2 maekawa 42:
1.1.1.4 ! ohara 43: void
! 44: foo (mpz_t result, const mpz_t param, unsigned long n)
! 45: {
! 46: unsigned long i;
! 47: mpz_mul_ui (result, param, n);
! 48: for (i = 1; i < n; i++)
! 49: mpz_add_ui (result, result, i*7);
! 50: }
! 51:
! 52: int
! 53: main (void)
! 54: {
! 55: mpz_t r, n;
! 56: mpz_init (r);
! 57: mpz_init_set_str (n, "123456", 0);
! 58: foo (r, n, 20L);
! 59: gmp_printf ("%Zd\n", r);
! 60: return 0;
! 61: }
1.1.1.2 maekawa 62:
1.1.1.4 ! ohara 63: `foo' works even if the mainline passes the same variable for
! 64: `param' and `result', just like the library functions. But sometimes
! 65: it's tricky to make that work, and an application might not want to
! 66: bother supporting that sort of thing.
1.1.1.2 maekawa 67:
1.1.1.4 ! ohara 68: For interest, the GMP types `mpz_t' etc are implemented as
! 69: one-element arrays of certain structures. This is why declaring a
! 70: variable creates an object with the fields GMP needs, but then using it
! 71: as a parameter passes a pointer to the object. Note that the actual
! 72: fields in each `mpz_t' etc are for internal use only and should not be
! 73: accessed directly by code that expects to be compatible with future GMP
! 74: releases.
1.1.1.2 maekawa 75:
76:
1.1.1.4 ! ohara 77: File: gmp.info, Node: Memory Management, Next: Reentrancy, Prev: Parameter Conventions, Up: GMP Basics
1.1.1.2 maekawa 78:
1.1.1.4 ! ohara 79: Memory Management
! 80: =================
1.1.1.2 maekawa 81:
1.1.1.4 ! ohara 82: The GMP types like `mpz_t' are small, containing only a couple of
! 83: sizes, and pointers to allocated data. Once a variable is initialized,
! 84: GMP takes care of all space allocation. Additional space is allocated
! 85: whenever a variable doesn't have enough.
1.1.1.2 maekawa 86:
1.1.1.4 ! ohara 87: `mpz_t' and `mpq_t' variables never reduce their allocated space.
! 88: Normally this is the best policy, since it avoids frequent reallocation.
! 89: Applications that need to return memory to the heap at some particular
! 90: point can use `mpz_realloc2', or clear variables no longer needed.
1.1.1.2 maekawa 91:
1.1.1.4 ! ohara 92: `mpf_t' variables, in the current implementation, use a fixed amount
! 93: of space, determined by the chosen precision and allocated at
! 94: initialization, so their size doesn't change.
1.1.1.2 maekawa 95:
1.1.1.4 ! ohara 96: All memory is allocated using `malloc' and friends by default, but
! 97: this can be changed, see *Note Custom Allocation::. Temporary memory
! 98: on the stack is also used (via `alloca'), but this can be changed at
! 99: build-time if desired, see *Note Build Options::.
1.1.1.2 maekawa 100:
101:
1.1.1.4 ! ohara 102: File: gmp.info, Node: Reentrancy, Next: Useful Macros and Constants, Prev: Memory Management, Up: GMP Basics
1.1.1.2 maekawa 103:
1.1.1.4 ! ohara 104: Reentrancy
! 105: ==========
1.1.1.2 maekawa 106:
1.1.1.4 ! ohara 107: GMP is reentrant and thread-safe, with some exceptions:
1.1.1.2 maekawa 108:
1.1.1.4 ! ohara 109: * If configured with `--enable-alloca=malloc-notreentrant' (or with
! 110: `--enable-alloca=notreentrant' when `alloca' is not available),
! 111: then naturally GMP is not reentrant.
1.1.1.2 maekawa 112:
1.1.1.4 ! ohara 113: * `mpf_set_default_prec' and `mpf_init' use a global variable for the
! 114: selected precision. `mpf_init2' can be used instead.
1.1.1.2 maekawa 115:
1.1.1.4 ! ohara 116: * `mpz_random' and the other old random number functions use a global
! 117: random state and are hence not reentrant. The newer random number
! 118: functions that accept a `gmp_randstate_t' parameter can be used
1.1.1.2 maekawa 119: instead.
120:
1.1.1.4 ! ohara 121: * `mp_set_memory_functions' uses global variables to store the
! 122: selected memory allocation functions.
1.1.1.2 maekawa 123:
1.1.1.4 ! ohara 124: * If the memory allocation functions set by a call to
! 125: `mp_set_memory_functions' (or `malloc' and friends by default) are
! 126: not reentrant, then GMP will not be reentrant either.
! 127:
! 128: * If the standard I/O functions such as `fwrite' are not reentrant
! 129: then the GMP I/O functions using them will not be reentrant either.
! 130:
! 131: * It's safe for two threads to read from the same GMP variable
! 132: simultaneously, but it's not safe for one to read while the
! 133: another might be writing, nor for two threads to write
! 134: simultaneously. It's not safe for two threads to generate a
! 135: random number from the same `gmp_randstate_t' simultaneously,
! 136: since this involves an update of that variable.
! 137:
! 138: * On SCO systems the default `<ctype.h>' macros use per-file static
! 139: variables and may not be reentrant, depending whether the compiler
! 140: optimizes away fetches from them. The GMP text-based input
! 141: functions are affected.
! 142:
! 143:
! 144: File: gmp.info, Node: Useful Macros and Constants, Next: Compatibility with older versions, Prev: Reentrancy, Up: GMP Basics
! 145:
! 146: Useful Macros and Constants
! 147: ===========================
! 148:
! 149: - Global Constant: const int mp_bits_per_limb
! 150: The number of bits per limb.
! 151:
! 152: - Macro: __GNU_MP_VERSION
! 153: - Macro: __GNU_MP_VERSION_MINOR
! 154: - Macro: __GNU_MP_VERSION_PATCHLEVEL
! 155: The major and minor GMP version, and patch level, respectively, as
! 156: integers. For GMP i.j, these numbers will be i, j, and 0,
! 157: respectively. For GMP i.j.k, these numbers will be i, j, and k,
! 158: respectively.
! 159:
! 160: - Global Constant: const char * const gmp_version
! 161: The GMP version number, as a null-terminated string, in the form
! 162: "i.j" or "i.j.k". This release is "4.1.2".
! 163:
! 164:
! 165: File: gmp.info, Node: Compatibility with older versions, Next: Demonstration Programs, Prev: Useful Macros and Constants, Up: GMP Basics
! 166:
! 167: Compatibility with older versions
! 168: =================================
! 169:
! 170: This version of GMP is upwardly binary compatible with all 4.x and
! 171: 3.x versions, and upwardly compatible at the source level with all 2.x
! 172: versions, with the following exceptions.
! 173:
! 174: * `mpn_gcd' had its source arguments swapped as of GMP 3.0, for
! 175: consistency with other `mpn' functions.
! 176:
! 177: * `mpf_get_prec' counted precision slightly differently in GMP 3.0
! 178: and 3.0.1, but in 3.1 reverted to the 2.x style.
! 179:
! 180: There are a number of compatibility issues between GMP 1 and GMP 2
! 181: that of course also apply when porting applications from GMP 1 to GMP
! 182: 4. Please see the GMP 2 manual for details.
! 183:
! 184: The Berkeley MP compatibility library (*note BSD Compatible
! 185: Functions::) is source and binary compatible with the standard `libmp'.
! 186:
! 187:
! 188: File: gmp.info, Node: Demonstration Programs, Next: Efficiency, Prev: Compatibility with older versions, Up: GMP Basics
! 189:
! 190: Demonstration programs
! 191: ======================
! 192:
! 193: The `demos' subdirectory has some sample programs using GMP. These
! 194: aren't built or installed, but there's a `Makefile' with rules for them.
! 195: For instance,
! 196:
! 197: make pexpr
! 198: ./pexpr 68^975+10
! 199:
! 200: The following programs are provided
! 201:
! 202: * `pexpr' is an expression evaluator, the program used on the GMP
! 203: web page.
! 204:
! 205: * The `calc' subdirectory has a similar but simpler evaluator using
! 206: `lex' and `yacc'.
! 207:
! 208: * The `expr' subdirectory is yet another expression evaluator, a
! 209: library designed for ease of use within a C program. See
! 210: `demos/expr/README' for more information.
! 211:
! 212: * `factorize' is a Pollard-Rho factorization program.
! 213:
! 214: * `isprime' is a command-line interface to the `mpz_probab_prime_p'
! 215: function.
! 216:
! 217: * `primes' counts or lists primes in an interval, using a sieve.
! 218:
! 219: * `qcn' is an example use of `mpz_kronecker_ui' to estimate quadratic
! 220: class numbers.
! 221:
! 222: * The `perl' subdirectory is a comprehensive perl interface to GMP.
! 223: See `demos/perl/INSTALL' for more information. Documentation is
! 224: in POD format in `demos/perl/GMP.pm'.
! 225:
! 226:
! 227: File: gmp.info, Node: Efficiency, Next: Debugging, Prev: Demonstration Programs, Up: GMP Basics
! 228:
! 229: Efficiency
! 230: ==========
! 231:
! 232: Small operands
! 233: On small operands, the time for function call overheads and memory
! 234: allocation can be significant in comparison to actual calculation.
! 235: This is unavoidable in a general purpose variable precision
! 236: library, although GMP attempts to be as efficient as it can on
! 237: both large and small operands.
! 238:
! 239: Static Linking
! 240: On some CPUs, in particular the x86s, the static `libgmp.a' should
! 241: be used for maximum speed, since the PIC code in the shared
! 242: `libgmp.so' will have a small overhead on each function call and
! 243: global data address. For many programs this will be
! 244: insignificant, but for long calculations there's a gain to be had.
! 245:
! 246: Initializing and clearing
! 247: Avoid excessive initializing and clearing of variables, since this
! 248: can be quite time consuming, especially in comparison to otherwise
! 249: fast operations like addition.
! 250:
! 251: A language interpreter might want to keep a free list or stack of
! 252: initialized variables ready for use. It should be possible to
! 253: integrate something like that with a garbage collector too.
! 254:
! 255: Reallocations
! 256: An `mpz_t' or `mpq_t' variable used to hold successively increasing
! 257: values will have its memory repeatedly `realloc'ed, which could be
! 258: quite slow or could fragment memory, depending on the C library.
! 259: If an application can estimate the final size then `mpz_init2' or
! 260: `mpz_realloc2' can be called to allocate the necessary space from
! 261: the beginning (*note Initializing Integers::).
! 262:
! 263: It doesn't matter if a size set with `mpz_init2' or `mpz_realloc2'
! 264: is too small, since all functions will do a further reallocation
! 265: if necessary. Badly overestimating memory required will waste
! 266: space though.
! 267:
! 268: `2exp' functions
! 269: It's up to an application to call functions like `mpz_mul_2exp'
! 270: when appropriate. General purpose functions like `mpz_mul' make
! 271: no attempt to identify powers of two or other special forms,
! 272: because such inputs will usually be very rare and testing every
! 273: time would be wasteful.
! 274:
! 275: `ui' and `si' functions
! 276: The `ui' functions and the small number of `si' functions exist for
! 277: convenience and should be used where applicable. But if for
! 278: example an `mpz_t' contains a value that fits in an `unsigned
! 279: long' there's no need extract it and call a `ui' function, just
! 280: use the regular `mpz' function.
! 281:
! 282: In-Place Operations
! 283: `mpz_abs', `mpq_abs', `mpf_abs', `mpz_neg', `mpq_neg' and
! 284: `mpf_neg' are fast when used for in-place operations like
! 285: `mpz_abs(x,x)', since in the current implementation only a single
! 286: field of `x' needs changing. On suitable compilers (GCC for
! 287: instance) this is inlined too.
! 288:
! 289: `mpz_add_ui', `mpz_sub_ui', `mpf_add_ui' and `mpf_sub_ui' benefit
! 290: from an in-place operation like `mpz_add_ui(x,x,y)', since usually
! 291: only one or two limbs of `x' will need to be changed. The same
! 292: applies to the full precision `mpz_add' etc if `y' is small. If
! 293: `y' is big then cache locality may be helped, but that's all.
! 294:
! 295: `mpz_mul' is currently the opposite, a separate destination is
! 296: slightly better. A call like `mpz_mul(x,x,y)' will, unless `y' is
! 297: only one limb, make a temporary copy of `x' before forming the
! 298: result. Normally that copying will only be a tiny fraction of the
! 299: time for the multiply, so this is not a particularly important
! 300: consideration.
! 301:
! 302: `mpz_set', `mpq_set', `mpq_set_num', `mpf_set', etc, make no
! 303: attempt to recognise a copy of something to itself, so a call like
! 304: `mpz_set(x,x)' will be wasteful. Naturally that would never be
! 305: written deliberately, but if it might arise from two pointers to
! 306: the same object then a test to avoid it might be desirable.
! 307:
! 308: if (x != y)
! 309: mpz_set (x, y);
! 310:
! 311: Note that it's never worth introducing extra `mpz_set' calls just
! 312: to get in-place operations. If a result should go to a particular
! 313: variable then just direct it there and let GMP take care of data
! 314: movement.
! 315:
! 316: Divisibility Testing (Small Integers)
! 317: `mpz_divisible_ui_p' and `mpz_congruent_ui_p' are the best
! 318: functions for testing whether an `mpz_t' is divisible by an
! 319: individual small integer. They use an algorithm which is faster
! 320: than `mpz_tdiv_ui', but which gives no useful information about
! 321: the actual remainder, only whether it's zero (or a particular
! 322: value).
! 323:
! 324: However when testing divisibility by several small integers, it's
! 325: best to take a remainder modulo their product, to save
! 326: multi-precision operations. For instance to test whether a number
! 327: is divisible by any of 23, 29 or 31 take a remainder modulo
! 328: 23*29*31 = 20677 and then test that.
! 329:
! 330: The division functions like `mpz_tdiv_q_ui' which give a quotient
! 331: as well as a remainder are generally a little slower than the
! 332: remainder-only functions like `mpz_tdiv_ui'. If the quotient is
! 333: only rarely wanted then it's probably best to just take a
! 334: remainder and then go back and calculate the quotient if and when
! 335: it's wanted (`mpz_divexact_ui' can be used if the remainder is
! 336: zero).
! 337:
! 338: Rational Arithmetic
! 339: The `mpq' functions operate on `mpq_t' values with no common
! 340: factors in the numerator and denominator. Common factors are
! 341: checked-for and cast out as necessary. In general, cancelling
! 342: factors every time is the best approach since it minimizes the
! 343: sizes for subsequent operations.
! 344:
! 345: However, applications that know something about the factorization
! 346: of the values they're working with might be able to avoid some of
! 347: the GCDs used for canonicalization, or swap them for divisions.
! 348: For example when multiplying by a prime it's enough to check for
! 349: factors of it in the denominator instead of doing a full GCD. Or
! 350: when forming a big product it might be known that very little
! 351: cancellation will be possible, and so canonicalization can be left
! 352: to the end.
! 353:
! 354: The `mpq_numref' and `mpq_denref' macros give access to the
! 355: numerator and denominator to do things outside the scope of the
! 356: supplied `mpq' functions. *Note Applying Integer Functions::.
! 357:
! 358: The canonical form for rationals allows mixed-type `mpq_t' and
! 359: integer additions or subtractions to be done directly with
! 360: multiples of the denominator. This will be somewhat faster than
! 361: `mpq_add'. For example,
! 362:
! 363: /* mpq increment */
! 364: mpz_add (mpq_numref(q), mpq_numref(q), mpq_denref(q));
! 365:
! 366: /* mpq += unsigned long */
! 367: mpz_addmul_ui (mpq_numref(q), mpq_denref(q), 123UL);
! 368:
! 369: /* mpq -= mpz */
! 370: mpz_submul (mpq_numref(q), mpq_denref(q), z);
! 371:
! 372: Number Sequences
! 373: Functions like `mpz_fac_ui', `mpz_fib_ui' and `mpz_bin_uiui' are
! 374: designed for calculating isolated values. If a range of values is
! 375: wanted it's probably best to call to get a starting point and
! 376: iterate from there.
! 377:
! 378: Text Input/Output
! 379: Hexadecimal or octal are suggested for input or output in text
! 380: form. Power-of-2 bases like these can be converted much more
! 381: efficiently than other bases, like decimal. For big numbers
! 382: there's usually nothing of particular interest to be seen in the
! 383: digits, so the base doesn't matter much.
! 384:
! 385: Maybe we can hope octal will one day become the normal base for
! 386: everyday use, as proposed by King Charles XII of Sweden and later
! 387: reformers.
! 388:
! 389:
! 390: File: gmp.info, Node: Debugging, Next: Profiling, Prev: Efficiency, Up: GMP Basics
! 391:
! 392: Debugging
! 393: =========
! 394:
! 395: Stack Overflow
! 396: Depending on the system, a segmentation violation or bus error
! 397: might be the only indication of stack overflow. See
! 398: `--enable-alloca' choices in *Note Build Options::, for how to
! 399: address this.
! 400:
! 401: In new enough versions of GCC, `-fstack-check' may be able to
! 402: ensure an overflow is recognised by the system before too much
! 403: damage is done, or `-fstack-limit-symbol' or
! 404: `-fstack-limit-register' may be able to add checking if the system
! 405: itself doesn't do any (*note Options for Code Generation:
! 406: (gcc)Code Gen Options.). These options must be added to the
! 407: `CFLAGS' used in the GMP build (*note Build Options::), adding
! 408: them just to an application will have no effect. Note also
! 409: they're a slowdown, adding overhead to each function call and each
! 410: stack allocation.
! 411:
! 412: Heap Problems
! 413: The most likely cause of application problems with GMP is heap
! 414: corruption. Failing to `init' GMP variables will have
! 415: unpredictable effects, and corruption arising elsewhere in a
! 416: program may well affect GMP. Initializing GMP variables more than
! 417: once or failing to clear them will cause memory leaks.
! 418:
! 419: In all such cases a malloc debugger is recommended. On a GNU or
! 420: BSD system the standard C library `malloc' has some diagnostic
! 421: facilities, see *Note Allocation Debugging: (libc)Allocation
! 422: Debugging, or `man 3 malloc'. Other possibilities, in no
! 423: particular order, include
! 424:
! 425: `http://www.inf.ethz.ch/personal/biere/projects/ccmalloc'
! 426: `http://quorum.tamu.edu/jon/gnu' (debauch)
! 427: `http://dmalloc.com'
! 428: `http://www.perens.com/FreeSoftware' (electric fence)
! 429: `http://packages.debian.org/fda'
! 430: `http://www.gnupdate.org/components/leakbug'
! 431: `http://people.redhat.com/~otaylor/memprof'
! 432: `http://www.cbmamiga.demon.co.uk/mpatrol'
! 433:
! 434: The GMP default allocation routines in `memory.c' also have a
! 435: simple sentinel scheme which can be enabled with `#define DEBUG'
! 436: in that file. This is mainly designed for detecting buffer
! 437: overruns during GMP development, but might find other uses.
! 438:
! 439: Stack Backtraces
! 440: On some systems the compiler options GMP uses by default can
! 441: interfere with debugging. In particular on x86 and 68k systems
! 442: `-fomit-frame-pointer' is used and this generally inhibits stack
! 443: backtracing. Recompiling without such options may help while
! 444: debugging, though the usual caveats about it potentially moving a
! 445: memory problem or hiding a compiler bug will apply.
! 446:
! 447: GNU Debugger
! 448: A sample `.gdbinit' is included in the distribution, showing how
! 449: to call some undocumented dump functions to print GMP variables
! 450: from within GDB. Note that these functions shouldn't be used in
! 451: final application code since they're undocumented and may be
! 452: subject to incompatible changes in future versions of GMP.
! 453:
! 454: Source File Paths
! 455: GMP has multiple source files with the same name, in different
! 456: directories. For example `mpz', `mpq', `mpf' and `mpfr' each have
! 457: an `init.c'. If the debugger can't already determine the right
! 458: one it may help to build with absolute paths on each C file. One
! 459: way to do that is to use a separate object directory with an
! 460: absolute path to the source directory.
! 461:
! 462: cd /my/build/dir
! 463: /my/source/dir/gmp-4.1.2/configure
! 464:
! 465: This works via `VPATH', and might require GNU `make'. Alternately
! 466: it might be possible to change the `.c.lo' rules appropriately.
! 467:
! 468: Assertion Checking
! 469: The build option `--enable-assert' is available to add some
! 470: consistency checks to the library (see *Note Build Options::).
! 471: These are likely to be of limited value to most applications.
! 472: Assertion failures are just as likely to indicate memory
! 473: corruption as a library or compiler bug.
! 474:
! 475: Applications using the low-level `mpn' functions, however, will
! 476: benefit from `--enable-assert' since it adds checks on the
! 477: parameters of most such functions, many of which have subtle
! 478: restrictions on their usage. Note however that only the generic C
! 479: code has checks, not the assembler code, so CPU `none' should be
! 480: used for maximum checking.
! 481:
! 482: Temporary Memory Checking
! 483: The build option `--enable-alloca=debug' arranges that each block
! 484: of temporary memory in GMP is allocated with a separate call to
! 485: `malloc' (or the allocation function set with
! 486: `mp_set_memory_functions').
! 487:
! 488: This can help a malloc debugger detect accesses outside the
! 489: intended bounds, or detect memory not released. In a normal
! 490: build, on the other hand, temporary memory is allocated in blocks
! 491: which GMP divides up for its own use, or may be allocated with a
! 492: compiler builtin `alloca' which will go nowhere near any malloc
! 493: debugger hooks.
! 494:
! 495: Maximum Debuggability
! 496: To summarize the above, a GMP build for maximum debuggability
! 497: would be
! 498:
! 499: ./configure --disable-shared --enable-assert \
! 500: --enable-alloca=debug --host=none CFLAGS=-g
! 501:
! 502: For C++, add `--enable-cxx CXXFLAGS=-g'.
! 503:
! 504: Checker
! 505: The checker program (`http://savannah.gnu.org/projects/checker')
! 506: can be used with GMP. It contains a stub library which means GMP
! 507: applications compiled with checker can use a normal GMP build.
! 508:
! 509: A build of GMP with checking within GMP itself can be made. This
! 510: will run very very slowly. Configure with
! 511:
! 512: ./configure --host=none-pc-linux-gnu CC=checkergcc
! 513:
! 514: `--host=none' must be used, since the GMP assembler code doesn't
! 515: support the checking scheme. The GMP C++ features cannot be used,
! 516: since current versions of checker (0.9.9.1) don't yet support the
! 517: standard C++ library.
! 518:
! 519: Valgrind
! 520: The valgrind program (`http://devel-home.kde.org/~sewardj') is a
! 521: memory checker for x86s. It translates and emulates machine
! 522: instructions to do strong checks for uninitialized data (at the
! 523: level of individual bits), memory accesses through bad pointers,
! 524: and memory leaks.
! 525:
! 526: Current versions (20020226 snapshot) don't support MMX or SSE, so
! 527: GMP must be configured for an x86 without those (eg. plain
! 528: `i386'), or with a special `MPN_PATH' that excludes those
! 529: subdirectories (*note Build Options::).
! 530:
! 531: Other Problems
! 532: Any suspected bug in GMP itself should be isolated to make sure
! 533: it's not an application problem, see *Note Reporting Bugs::.
! 534:
! 535:
! 536: File: gmp.info, Node: Profiling, Next: Autoconf, Prev: Debugging, Up: GMP Basics
! 537:
! 538: Profiling
! 539: =========
! 540:
! 541: Running a program under a profiler is a good way to find where it's
! 542: spending most time and where improvements can be best sought.
! 543:
! 544: Depending on the system, it may be possible to get a flat profile,
! 545: meaning simple timer sampling of the program counter, with no special
! 546: GMP build options, just a `-p' when compiling the mainline. This is a
! 547: good way to ensure minimum interference with normal operation. The
! 548: necessary symbol type and size information exists in most of the GMP
! 549: assembler code.
! 550:
! 551: The `--enable-profiling' build option can be used to add suitable
! 552: compiler flags, either for `prof' (`-p') or `gprof' (`-pg'), see *Note
! 553: Build Options::. Which of the two is available and what they do will
! 554: depend on the system, and possibly on support available in `libc'. For
! 555: some systems appropriate corresponding `mcount' calls are added to the
! 556: assembler code too.
! 557:
! 558: On x86 systems `prof' gives call counting, so that average time spent
! 559: in a function can be determined. `gprof', where supported, adds call
! 560: graph construction, so for instance calls to `mpn_add_n' from `mpz_add'
! 561: and from `mpz_mul' can be differentiated.
! 562:
! 563: On x86 and 68k systems `-pg' and `-fomit-frame-pointer' are
! 564: incompatible, so the latter is not used when `gprof' profiling is
! 565: selected, which may result in poorer code generation. If `prof'
! 566: profiling is selected instead it should still be possible to use
! 567: `gprof', but only the `gprof -p' flat profile and call counts can be
! 568: expected to be valid, not the `gprof -q' call graph.
! 569:
! 570:
! 571: File: gmp.info, Node: Autoconf, Next: Emacs, Prev: Profiling, Up: GMP Basics
! 572:
! 573: Autoconf
! 574: ========
! 575:
! 576: Autoconf based applications can easily check whether GMP is
! 577: installed. The only thing to be noted is that GMP library symbols from
! 578: version 3 onwards have prefixes like `__gmpz'. The following therefore
! 579: would be a simple test,
! 580:
! 581: AC_CHECK_LIB(gmp, __gmpz_init)
! 582:
! 583: This just uses the default `AC_CHECK_LIB' actions for found or not
! 584: found, but an application that must have GMP would want to generate an
! 585: error if not found. For example,
! 586:
! 587: AC_CHECK_LIB(gmp, __gmpz_init, , [AC_MSG_ERROR(
! 588: [GNU MP not found, see http://swox.com/gmp])])
! 589:
! 590: If functions added in some particular version of GMP are required,
! 591: then one of those can be used when checking. For example `mpz_mul_si'
! 592: was added in GMP 3.1,
! 593:
! 594: AC_CHECK_LIB(gmp, __gmpz_mul_si, , [AC_MSG_ERROR(
! 595: [GNU MP not found, or not 3.1 or up, see http://swox.com/gmp])])
! 596:
! 597: An alternative would be to test the version number in `gmp.h' using
! 598: say `AC_EGREP_CPP'. That would make it possible to test the exact
! 599: version, if some particular sub-minor release is known to be necessary.
! 600:
! 601: An application that can use either GMP 2 or 3 will need to test for
! 602: `__gmpz_init' (GMP 3 and up) or `mpz_init' (GMP 2), and it's also worth
! 603: checking for `libgmp2' since Debian GNU/Linux systems used that name in
! 604: the past. For example,
! 605:
! 606: AC_CHECK_LIB(gmp, __gmpz_init, ,
! 607: [AC_CHECK_LIB(gmp, mpz_init, ,
! 608: [AC_CHECK_LIB(gmp2, mpz_init)])])
! 609:
! 610: In general it's suggested that applications should simply demand a
! 611: new enough GMP rather than trying to provide supplements for features
! 612: not available in past versions.
! 613:
! 614: Occasionally an application will need or want to know the size of a
! 615: type at configuration or preprocessing time, not just with `sizeof' in
! 616: the code. This can be done in the normal way with `mp_limb_t' etc, but
! 617: GMP 4.0 or up is best for this, since prior versions needed certain
! 618: `-D' defines on systems using a `long long' limb. The following would
! 619: suit Autoconf 2.50 or up,
! 620:
! 621: AC_CHECK_SIZEOF(mp_limb_t, , [#include <gmp.h>])
! 622:
! 623: The optional `mpfr' functions are provided in a separate
! 624: `libmpfr.a', and this might be from GMP with `--enable-mpfr' or from
! 625: MPFR installed separately. Either way `libmpfr' depends on `libgmp',
! 626: it doesn't stand alone. Currently only a static `libmpfr.a' will be
! 627: available, not a shared library, since upward binary compatibility is
! 628: not guaranteed.
! 629:
! 630: AC_CHECK_LIB(mpfr, mpfr_add, , [AC_MSG_ERROR(
! 631: [Need MPFR either from GNU MP 4 or separate MPFR package.
! 632: See http://www.mpfr.org or http://swox.com/gmp])
! 633:
! 634:
! 635: File: gmp.info, Node: Emacs, Prev: Autoconf, Up: GMP Basics
! 636:
! 637: Emacs
! 638: =====
! 639:
! 640: <C-h C-i> (`info-lookup-symbol') is a good way to find documentation
! 641: on C functions while editing (*note Info Documentation Lookup:
! 642: (emacs)Info Lookup.).
! 643:
! 644: The GMP manual can be included in such lookups by putting the
! 645: following in your `.emacs',
! 646:
! 647: (eval-after-load "info-look"
! 648: '(let ((mode-value (assoc 'c-mode (assoc 'symbol info-lookup-alist))))
! 649: (setcar (nthcdr 3 mode-value)
! 650: (cons '("(gmp)Function Index" nil "^ -.* " "\\>")
! 651: (nth 3 mode-value)))))
! 652:
! 653: The same can be done for MPFR, with `(mpfr)' in place of `(gmp)'.
! 654:
! 655:
! 656: File: gmp.info, Node: Reporting Bugs, Next: Integer Functions, Prev: GMP Basics, Up: Top
! 657:
! 658: Reporting Bugs
! 659: **************
! 660:
! 661: If you think you have found a bug in the GMP library, please
! 662: investigate it and report it. We have made this library available to
! 663: you, and it is not too much to ask you to report the bugs you find.
! 664:
! 665: Before you report a bug, check it's not already addressed in *Note
! 666: Known Build Problems::, or perhaps *Note Notes for Particular
! 667: Systems::. You may also want to check `http://swox.com/gmp/' for
! 668: patches for this release.
! 669:
! 670: Please include the following in any report,
! 671:
! 672: * The GMP version number, and if pre-packaged or patched then say so.
! 673:
! 674: * A test program that makes it possible for us to reproduce the bug.
! 675: Include instructions on how to run the program.
! 676:
! 677: * A description of what is wrong. If the results are incorrect, in
! 678: what way. If you get a crash, say so.
! 679:
! 680: * If you get a crash, include a stack backtrace from the debugger if
! 681: it's informative (`where' in `gdb', or `$C' in `adb').
! 682:
! 683: * Please do not send core dumps, executables or `strace's.
! 684:
! 685: * The configuration options you used when building GMP, if any.
! 686:
! 687: * The name of the compiler and its version. For `gcc', get the
! 688: version with `gcc -v', otherwise perhaps `what `which cc`', or
! 689: similar.
! 690:
! 691: * The output from running `uname -a'.
! 692:
! 693: * The output from running `./config.guess', and from running
! 694: `./configfsf.guess' (might be the same).
! 695:
! 696: * If the bug is related to `configure', then the contents of
! 697: `config.log'.
! 698:
! 699: * If the bug is related to an `asm' file not assembling, then the
! 700: contents of `config.m4' and the offending line or lines from the
! 701: temporary `mpn/tmp-<file>.s'.
! 702:
! 703: Please make an effort to produce a self-contained report, with
! 704: something definite that can be tested or debugged. Vague queries or
! 705: piecemeal messages are difficult to act on and don't help the
! 706: development effort.
! 707:
! 708: It is not uncommon that an observed problem is actually due to a bug
! 709: in the compiler; the GMP code tends to explore interesting corners in
! 710: compilers.
! 711:
! 712: If your bug report is good, we will do our best to help you get a
! 713: corrected version of the library; if the bug report is poor, we won't
! 714: do anything about it (except maybe ask you to send a better report).
! 715:
! 716: Send your report to: <bug-gmp@gnu.org>.
! 717:
! 718: If you think something in this manual is unclear, or downright
! 719: incorrect, or if the language needs to be improved, please send a note
! 720: to the same address.
! 721:
! 722:
! 723: File: gmp.info, Node: Integer Functions, Next: Rational Number Functions, Prev: Reporting Bugs, Up: Top
1.1.1.2 maekawa 724:
1.1.1.4 ! ohara 725: Integer Functions
! 726: *****************
1.1.1.2 maekawa 727:
1.1.1.4 ! ohara 728: This chapter describes the GMP functions for performing integer
! 729: arithmetic. These functions start with the prefix `mpz_'.
1.1.1.2 maekawa 730:
1.1.1.4 ! ohara 731: GMP integers are stored in objects of type `mpz_t'.
1.1.1.2 maekawa 732:
1.1.1.4 ! ohara 733: * Menu:
1.1.1.2 maekawa 734:
1.1.1.4 ! ohara 735: * Initializing Integers::
! 736: * Assigning Integers::
! 737: * Simultaneous Integer Init & Assign::
! 738: * Converting Integers::
! 739: * Integer Arithmetic::
! 740: * Integer Division::
! 741: * Integer Exponentiation::
! 742: * Integer Roots::
! 743: * Number Theoretic Functions::
! 744: * Integer Comparisons::
! 745: * Integer Logic and Bit Fiddling::
! 746: * I/O of Integers::
! 747: * Integer Random Numbers::
! 748: * Integer Import and Export::
! 749: * Miscellaneous Integer Functions::
1.1.1.2 maekawa 750:
751:
1.1.1.4 ! ohara 752: File: gmp.info, Node: Initializing Integers, Next: Assigning Integers, Prev: Integer Functions, Up: Integer Functions
1.1.1.2 maekawa 753:
1.1.1.4 ! ohara 754: Initialization Functions
! 755: ========================
1.1.1.2 maekawa 756:
1.1.1.4 ! ohara 757: The functions for integer arithmetic assume that all integer objects
! 758: are initialized. You do that by calling the function `mpz_init'. For
! 759: example,
1.1.1.2 maekawa 760:
1.1.1.4 ! ohara 761: {
! 762: mpz_t integ;
! 763: mpz_init (integ);
! 764: ...
! 765: mpz_add (integ, ...);
! 766: ...
! 767: mpz_sub (integ, ...);
! 768:
! 769: /* Unless the program is about to exit, do ... */
! 770: mpz_clear (integ);
! 771: }
1.1.1.2 maekawa 772:
1.1.1.4 ! ohara 773: As you can see, you can store new values any number of times, once an
! 774: object is initialized.
1.1.1.2 maekawa 775:
1.1.1.4 ! ohara 776: - Function: void mpz_init (mpz_t INTEGER)
! 777: Initialize INTEGER, and set its value to 0.
1.1.1.2 maekawa 778:
1.1.1.4 ! ohara 779: - Function: void mpz_init2 (mpz_t INTEGER, unsigned long N)
! 780: Initialize INTEGER, with space for N bits, and set its value to 0.
1.1 maekawa 781:
1.1.1.4 ! ohara 782: N is only the initial space, INTEGER will grow automatically in
! 783: the normal way, if necessary, for subsequent values stored.
! 784: `mpz_init2' makes it possible to avoid such reallocations if a
! 785: maximum size is known in advance.
1.1 maekawa 786:
1.1.1.4 ! ohara 787: - Function: void mpz_clear (mpz_t INTEGER)
! 788: Free the space occupied by INTEGER. Call this function for all
! 789: `mpz_t' variables when you are done with them.
1.1 maekawa 790:
1.1.1.4 ! ohara 791: - Function: void mpz_realloc2 (mpz_t INTEGER, unsigned long N)
! 792: Change the space allocated for INTEGER to N bits. The value in
! 793: INTEGER is preserved if it fits, or is set to 0 if not.
1.1 maekawa 794:
1.1.1.4 ! ohara 795: This function can be used to increase the space for a variable in
! 796: order to avoid repeated automatic reallocations, or to decrease it
! 797: to give memory back to the heap.
1.1 maekawa 798:
1.1.1.4 ! ohara 799: - Function: void mpz_array_init (mpz_t INTEGER_ARRAY[], size_t
! 800: ARRAY_SIZE, mp_size_t FIXED_NUM_BITS)
! 801: This is a special type of initialization. *Fixed* space of
! 802: FIXED_NUM_BITS bits is allocated to each of the ARRAY_SIZE
! 803: integers in INTEGER_ARRAY.
1.1 maekawa 804:
1.1.1.4 ! ohara 805: The space will not be automatically increased, unlike the normal
! 806: `mpz_init', but instead an application must ensure it's sufficient
! 807: for any value stored. The following space requirements apply to
! 808: various functions,
1.1 maekawa 809:
1.1.1.4 ! ohara 810: * `mpz_abs', `mpz_neg', `mpz_set', `mpz_set_si' and
! 811: `mpz_set_ui' need room for the value they store.
1.1 maekawa 812:
1.1.1.4 ! ohara 813: * `mpz_add', `mpz_add_ui', `mpz_sub' and `mpz_sub_ui' need room
! 814: for the larger of the two operands, plus an extra
! 815: `mp_bits_per_limb'.
1.1 maekawa 816:
1.1.1.4 ! ohara 817: * `mpz_mul', `mpz_mul_ui' and `mpz_mul_ui' need room for the sum
! 818: of the number of bits in their operands, but each rounded up
! 819: to a multiple of `mp_bits_per_limb'.
1.1 maekawa 820:
1.1.1.4 ! ohara 821: * `mpz_swap' can be used between two array variables, but not
! 822: between an array and a normal variable.
1.1 maekawa 823:
1.1.1.4 ! ohara 824: For other functions, or if in doubt, the suggestion is to
! 825: calculate in a regular `mpz_init' variable and copy the result to
! 826: an array variable with `mpz_set'.
1.1 maekawa 827:
1.1.1.4 ! ohara 828: `mpz_array_init' can reduce memory usage in algorithms that need
! 829: large arrays of integers, since it avoids allocating and
! 830: reallocating lots of small memory blocks. There is no way to free
! 831: the storage allocated by this function. Don't call `mpz_clear'!
1.1 maekawa 832:
1.1.1.4 ! ohara 833: - Function: void * _mpz_realloc (mpz_t INTEGER, mp_size_t NEW_ALLOC)
! 834: Change the space for INTEGER to NEW_ALLOC limbs. The value in
! 835: INTEGER is preserved if it fits, or is set to 0 if not. The return
! 836: value is not useful to applications and should be ignored.
1.1 maekawa 837:
1.1.1.4 ! ohara 838: `mpz_realloc2' is the preferred way to accomplish allocation
! 839: changes like this. `mpz_realloc2' and `_mpz_realloc' are the same
! 840: except that `_mpz_realloc' takes the new size in limbs.
1.1 maekawa 841:
842:
1.1.1.4 ! ohara 843: File: gmp.info, Node: Assigning Integers, Next: Simultaneous Integer Init & Assign, Prev: Initializing Integers, Up: Integer Functions
1.1 maekawa 844:
845: Assignment Functions
1.1.1.2 maekawa 846: ====================
1.1 maekawa 847:
1.1.1.4 ! ohara 848: These functions assign new values to already initialized integers
! 849: (*note Initializing Integers::).
1.1 maekawa 850:
1.1.1.4 ! ohara 851: - Function: void mpz_set (mpz_t ROP, mpz_t OP)
! 852: - Function: void mpz_set_ui (mpz_t ROP, unsigned long int OP)
! 853: - Function: void mpz_set_si (mpz_t ROP, signed long int OP)
! 854: - Function: void mpz_set_d (mpz_t ROP, double OP)
! 855: - Function: void mpz_set_q (mpz_t ROP, mpq_t OP)
! 856: - Function: void mpz_set_f (mpz_t ROP, mpf_t OP)
1.1 maekawa 857: Set the value of ROP from OP.
858:
1.1.1.4 ! ohara 859: `mpz_set_d', `mpz_set_q' and `mpz_set_f' truncate OP to make it an
! 860: integer.
! 861:
! 862: - Function: int mpz_set_str (mpz_t ROP, char *STR, int BASE)
! 863: Set the value of ROP from STR, a null-terminated C string in base
! 864: BASE. White space is allowed in the string, and is simply
! 865: ignored. The base may vary from 2 to 36. If BASE is 0, the
! 866: actual base is determined from the leading characters: if the
! 867: first two characters are "0x" or "0X", hexadecimal is assumed,
! 868: otherwise if the first character is "0", octal is assumed,
! 869: otherwise decimal is assumed.
! 870:
! 871: This function returns 0 if the entire string is a valid number in
! 872: base BASE. Otherwise it returns -1.
! 873:
! 874: [It turns out that it is not entirely true that this function
! 875: ignores white-space. It does ignore it between digits, but not
! 876: after a minus sign or within or after "0x". We are considering
1.1.1.2 maekawa 877: changing the definition of this function, making it fail when
878: there is any white-space in the input, since that makes a lot of
1.1.1.4 ! ohara 879: sense. Send your opinion of this change to <bug-gmp@gnu.org>. Do
! 880: you really want it to accept "3 14" as meaning 314 as it does now?]
1.1 maekawa 881:
1.1.1.4 ! ohara 882: - Function: void mpz_swap (mpz_t ROP1, mpz_t ROP2)
1.1.1.2 maekawa 883: Swap the values ROP1 and ROP2 efficiently.
884:
1.1 maekawa 885:
1.1.1.4 ! ohara 886: File: gmp.info, Node: Simultaneous Integer Init & Assign, Next: Converting Integers, Prev: Assigning Integers, Up: Integer Functions
1.1 maekawa 887:
888: Combined Initialization and Assignment Functions
1.1.1.2 maekawa 889: ================================================
1.1 maekawa 890:
1.1.1.2 maekawa 891: For convenience, GMP provides a parallel series of
892: initialize-and-set functions which initialize the output and then store
1.1.1.4 ! ohara 893: the value there. These functions' names have the form `mpz_init_set...'
1.1 maekawa 894:
1.1.1.4 ! ohara 895: Here is an example of using one:
1.1 maekawa 896:
1.1.1.4 ! ohara 897: {
! 898: mpz_t pie;
! 899: mpz_init_set_str (pie, "3141592653589793238462643383279502884", 10);
! 900: ...
! 901: mpz_sub (pie, ...);
! 902: ...
! 903: mpz_clear (pie);
! 904: }
1.1 maekawa 905:
1.1.1.4 ! ohara 906: Once the integer has been initialized by any of the `mpz_init_set...'
! 907: functions, it can be used as the source or destination operand for the
! 908: ordinary integer functions. Don't use an initialize-and-set function
! 909: on a variable already initialized!
1.1 maekawa 910:
1.1.1.4 ! ohara 911: - Function: void mpz_init_set (mpz_t ROP, mpz_t OP)
! 912: - Function: void mpz_init_set_ui (mpz_t ROP, unsigned long int OP)
! 913: - Function: void mpz_init_set_si (mpz_t ROP, signed long int OP)
! 914: - Function: void mpz_init_set_d (mpz_t ROP, double OP)
! 915: Initialize ROP with limb space and set the initial numeric value
! 916: from OP.
! 917:
! 918: - Function: int mpz_init_set_str (mpz_t ROP, char *STR, int BASE)
! 919: Initialize ROP and set its value like `mpz_set_str' (see its
! 920: documentation above for details).
! 921:
! 922: If the string is a correct base BASE number, the function returns
! 923: 0; if an error occurs it returns -1. ROP is initialized even if
! 924: an error occurs. (I.e., you have to call `mpz_clear' for it.)
1.1 maekawa 925:
926:
1.1.1.4 ! ohara 927: File: gmp.info, Node: Converting Integers, Next: Integer Arithmetic, Prev: Simultaneous Integer Init & Assign, Up: Integer Functions
1.1 maekawa 928:
929: Conversion Functions
930: ====================
931:
1.1.1.4 ! ohara 932: This section describes functions for converting GMP integers to
! 933: standard C types. Functions for converting _to_ GMP integers are
! 934: described in *Note Assigning Integers:: and *Note I/O of Integers::.
! 935:
! 936: - Function: unsigned long int mpz_get_ui (mpz_t OP)
! 937: Return the value of OP as an `unsigned long'.
! 938:
! 939: If OP is too big to fit an `unsigned long' then just the least
! 940: significant bits that do fit are returned. The sign of OP is
! 941: ignored, only the absolute value is used.
! 942:
! 943: - Function: signed long int mpz_get_si (mpz_t OP)
! 944: If OP fits into a `signed long int' return the value of OP.
! 945: Otherwise return the least significant part of OP, with the same
! 946: sign as OP.
! 947:
! 948: If OP is too big to fit in a `signed long int', the returned
! 949: result is probably not very useful. To find out if the value will
! 950: fit, use the function `mpz_fits_slong_p'.
! 951:
! 952: - Function: double mpz_get_d (mpz_t OP)
! 953: Convert OP to a `double'.
! 954:
! 955: - Function: double mpz_get_d_2exp (signed long int *EXP, mpz_t OP)
! 956: Find D and EXP such that D times 2 raised to EXP, with
! 957: 0.5<=abs(D)<1, is a good approximation to OP.
1.1 maekawa 958:
1.1.1.4 ! ohara 959: - Function: char * mpz_get_str (char *STR, int BASE, mpz_t OP)
1.1 maekawa 960: Convert OP to a string of digits in base BASE. The base may vary
1.1.1.4 ! ohara 961: from 2 to 36.
1.1 maekawa 962:
1.1.1.4 ! ohara 963: If STR is `NULL', the result string is allocated using the current
! 964: allocation function (*note Custom Allocation::). The block will be
! 965: `strlen(str)+1' bytes, that being exactly enough for the string and
! 966: null-terminator.
1.1 maekawa 967:
1.1.1.4 ! ohara 968: If STR is not `NULL', it should point to a block of storage large
! 969: enough for the result, that being `mpz_sizeinbase (OP, BASE) + 2'.
! 970: The two extra bytes are for a possible minus sign, and the
! 971: null-terminator.
1.1 maekawa 972:
1.1.1.4 ! ohara 973: A pointer to the result string is returned, being either the
! 974: allocated block, or the given STR.
1.1 maekawa 975:
1.1.1.4 ! ohara 976: - Function: mp_limb_t mpz_getlimbn (mpz_t OP, mp_size_t N)
! 977: Return limb number N from OP. The sign of OP is ignored, just the
! 978: absolute value is used. The least significant limb is number 0.
1.1 maekawa 979:
1.1.1.4 ! ohara 980: `mpz_size' can be used to find how many limbs make up OP.
! 981: `mpz_getlimbn' returns zero if N is outside the range 0 to
! 982: `mpz_size(OP)-1'.
1.1.1.2 maekawa 983:
1.1 maekawa 984:
1.1.1.4 ! ohara 985: File: gmp.info, Node: Integer Arithmetic, Next: Integer Division, Prev: Converting Integers, Up: Integer Functions
1.1 maekawa 986:
987: Arithmetic Functions
988: ====================
989:
1.1.1.4 ! ohara 990: - Function: void mpz_add (mpz_t ROP, mpz_t OP1, mpz_t OP2)
! 991: - Function: void mpz_add_ui (mpz_t ROP, mpz_t OP1, unsigned long int
1.1 maekawa 992: OP2)
993: Set ROP to OP1 + OP2.
994:
1.1.1.4 ! ohara 995: - Function: void mpz_sub (mpz_t ROP, mpz_t OP1, mpz_t OP2)
! 996: - Function: void mpz_sub_ui (mpz_t ROP, mpz_t OP1, unsigned long int
1.1 maekawa 997: OP2)
1.1.1.4 ! ohara 998: - Function: void mpz_ui_sub (mpz_t ROP, unsigned long int OP1, mpz_t
1.1 maekawa 999: OP2)
1000: Set ROP to OP1 - OP2.
1001:
1.1.1.4 ! ohara 1002: - Function: void mpz_mul (mpz_t ROP, mpz_t OP1, mpz_t OP2)
! 1003: - Function: void mpz_mul_si (mpz_t ROP, mpz_t OP1, long int OP2)
! 1004: - Function: void mpz_mul_ui (mpz_t ROP, mpz_t OP1, unsigned long int
1.1 maekawa 1005: OP2)
1006: Set ROP to OP1 times OP2.
1007:
1.1.1.4 ! ohara 1008: - Function: void mpz_addmul (mpz_t ROP, mpz_t OP1, mpz_t OP2)
! 1009: - Function: void mpz_addmul_ui (mpz_t ROP, mpz_t OP1, unsigned long
! 1010: int OP2)
! 1011: Set ROP to ROP + OP1 times OP2.
! 1012:
! 1013: - Function: void mpz_submul (mpz_t ROP, mpz_t OP1, mpz_t OP2)
! 1014: - Function: void mpz_submul_ui (mpz_t ROP, mpz_t OP1, unsigned long
! 1015: int OP2)
! 1016: Set ROP to ROP - OP1 times OP2.
1.1 maekawa 1017:
1.1.1.4 ! ohara 1018: - Function: void mpz_mul_2exp (mpz_t ROP, mpz_t OP1, unsigned long int
1.1.1.2 maekawa 1019: OP2)
1.1.1.4 ! ohara 1020: Set ROP to OP1 times 2 raised to OP2. This operation can also be
! 1021: defined as a left shift by OP2 bits.
1.1.1.2 maekawa 1022:
1.1.1.4 ! ohara 1023: - Function: void mpz_neg (mpz_t ROP, mpz_t OP)
1.1 maekawa 1024: Set ROP to -OP.
1025:
1.1.1.4 ! ohara 1026: - Function: void mpz_abs (mpz_t ROP, mpz_t OP)
1.1 maekawa 1027: Set ROP to the absolute value of OP.
1028:
1.1.1.4 ! ohara 1029:
! 1030: File: gmp.info, Node: Integer Division, Next: Integer Exponentiation, Prev: Integer Arithmetic, Up: Integer Functions
1.1 maekawa 1031:
1.1.1.4 ! ohara 1032: Division Functions
! 1033: ==================
! 1034:
! 1035: Division is undefined if the divisor is zero. Passing a zero
! 1036: divisor to the division or modulo functions (including the modular
! 1037: powering functions `mpz_powm' and `mpz_powm_ui'), will cause an
! 1038: intentional division by zero. This lets a program handle arithmetic
! 1039: exceptions in these functions the same way as for normal C `int'
! 1040: arithmetic.
! 1041:
! 1042: - Function: void mpz_cdiv_q (mpz_t Q, mpz_t N, mpz_t D)
! 1043: - Function: void mpz_cdiv_r (mpz_t R, mpz_t N, mpz_t D)
! 1044: - Function: void mpz_cdiv_qr (mpz_t Q, mpz_t R, mpz_t N, mpz_t D)
! 1045: - Function: unsigned long int mpz_cdiv_q_ui (mpz_t Q, mpz_t N,
! 1046: unsigned long int D)
! 1047: - Function: unsigned long int mpz_cdiv_r_ui (mpz_t R, mpz_t N,
! 1048: unsigned long int D)
! 1049: - Function: unsigned long int mpz_cdiv_qr_ui (mpz_t Q, mpz_t R,
! 1050: mpz_t N, unsigned long int D)
! 1051: - Function: unsigned long int mpz_cdiv_ui (mpz_t N,
! 1052: unsigned long int D)
! 1053: - Function: void mpz_cdiv_q_2exp (mpz_t Q, mpz_t N,
! 1054: unsigned long int B)
! 1055: - Function: void mpz_cdiv_r_2exp (mpz_t R, mpz_t N,
! 1056: unsigned long int B)
! 1057:
! 1058: - Function: void mpz_fdiv_q (mpz_t Q, mpz_t N, mpz_t D)
! 1059: - Function: void mpz_fdiv_r (mpz_t R, mpz_t N, mpz_t D)
! 1060: - Function: void mpz_fdiv_qr (mpz_t Q, mpz_t R, mpz_t N, mpz_t D)
! 1061: - Function: unsigned long int mpz_fdiv_q_ui (mpz_t Q, mpz_t N,
! 1062: unsigned long int D)
! 1063: - Function: unsigned long int mpz_fdiv_r_ui (mpz_t R, mpz_t N,
! 1064: unsigned long int D)
! 1065: - Function: unsigned long int mpz_fdiv_qr_ui (mpz_t Q, mpz_t R,
! 1066: mpz_t N, unsigned long int D)
! 1067: - Function: unsigned long int mpz_fdiv_ui (mpz_t N,
! 1068: unsigned long int D)
! 1069: - Function: void mpz_fdiv_q_2exp (mpz_t Q, mpz_t N,
! 1070: unsigned long int B)
! 1071: - Function: void mpz_fdiv_r_2exp (mpz_t R, mpz_t N,
! 1072: unsigned long int B)
! 1073:
! 1074: - Function: void mpz_tdiv_q (mpz_t Q, mpz_t N, mpz_t D)
! 1075: - Function: void mpz_tdiv_r (mpz_t R, mpz_t N, mpz_t D)
! 1076: - Function: void mpz_tdiv_qr (mpz_t Q, mpz_t R, mpz_t N, mpz_t D)
! 1077: - Function: unsigned long int mpz_tdiv_q_ui (mpz_t Q, mpz_t N,
! 1078: unsigned long int D)
! 1079: - Function: unsigned long int mpz_tdiv_r_ui (mpz_t R, mpz_t N,
! 1080: unsigned long int D)
! 1081: - Function: unsigned long int mpz_tdiv_qr_ui (mpz_t Q, mpz_t R,
! 1082: mpz_t N, unsigned long int D)
! 1083: - Function: unsigned long int mpz_tdiv_ui (mpz_t N,
! 1084: unsigned long int D)
! 1085: - Function: void mpz_tdiv_q_2exp (mpz_t Q, mpz_t N,
! 1086: unsigned long int B)
! 1087: - Function: void mpz_tdiv_r_2exp (mpz_t R, mpz_t N,
! 1088: unsigned long int B)
! 1089:
! 1090: Divide N by D, forming a quotient Q and/or remainder R. For the
! 1091: `2exp' functions, D=2^B. The rounding is in three styles, each
! 1092: suiting different applications.
! 1093:
! 1094: * `cdiv' rounds Q up towards +infinity, and R will have the
! 1095: opposite sign to D. The `c' stands for "ceil".
! 1096:
! 1097: * `fdiv' rounds Q down towards -infinity, and R will have the
! 1098: same sign as D. The `f' stands for "floor".
! 1099:
! 1100: * `tdiv' rounds Q towards zero, and R will have the same sign
! 1101: as N. The `t' stands for "truncate".
! 1102:
! 1103: In all cases Q and R will satisfy N=Q*D+R, and R will satisfy
! 1104: 0<=abs(R)<abs(D).
! 1105:
! 1106: The `q' functions calculate only the quotient, the `r' functions
! 1107: only the remainder, and the `qr' functions calculate both. Note
! 1108: that for `qr' the same variable cannot be passed for both Q and R,
! 1109: or results will be unpredictable.
! 1110:
! 1111: For the `ui' variants the return value is the remainder, and in
! 1112: fact returning the remainder is all the `div_ui' functions do. For
! 1113: `tdiv' and `cdiv' the remainder can be negative, so for those the
! 1114: return value is the absolute value of the remainder.
! 1115:
! 1116: The `2exp' functions are right shifts and bit masks, but of course
! 1117: rounding the same as the other functions. For positive N both
! 1118: `mpz_fdiv_q_2exp' and `mpz_tdiv_q_2exp' are simple bitwise right
! 1119: shifts. For negative N, `mpz_fdiv_q_2exp' is effectively an
! 1120: arithmetic right shift treating N as twos complement the same as
! 1121: the bitwise logical functions do, whereas `mpz_tdiv_q_2exp'
! 1122: effectively treats N as sign and magnitude.
! 1123:
! 1124: - Function: void mpz_mod (mpz_t R, mpz_t N, mpz_t D)
! 1125: - Function: unsigned long int mpz_mod_ui (mpz_t R, mpz_t N,
! 1126: unsigned long int D)
! 1127: Set R to N `mod' D. The sign of the divisor is ignored; the
! 1128: result is always non-negative.
! 1129:
! 1130: `mpz_mod_ui' is identical to `mpz_fdiv_r_ui' above, returning the
! 1131: remainder as well as setting R. See `mpz_fdiv_ui' above if only
! 1132: the return value is wanted.
! 1133:
! 1134: - Function: void mpz_divexact (mpz_t Q, mpz_t N, mpz_t D)
! 1135: - Function: void mpz_divexact_ui (mpz_t Q, mpz_t N, unsigned long D)
! 1136: Set Q to N/D. These functions produce correct results only when
! 1137: it is known in advance that D divides N.
! 1138:
! 1139: These routines are much faster than the other division functions,
! 1140: and are the best choice when exact division is known to occur, for
! 1141: example reducing a rational to lowest terms.
! 1142:
! 1143: - Function: int mpz_divisible_p (mpz_t N, mpz_t D)
! 1144: - Function: int mpz_divisible_ui_p (mpz_t N, unsigned long int D)
! 1145: - Function: int mpz_divisible_2exp_p (mpz_t N, unsigned long int B)
! 1146: Return non-zero if N is exactly divisible by D, or in the case of
! 1147: `mpz_divisible_2exp_p' by 2^B.
! 1148:
! 1149: - Function: int mpz_congruent_p (mpz_t N, mpz_t C, mpz_t D)
! 1150: - Function: int mpz_congruent_ui_p (mpz_t N, unsigned long int C,
! 1151: unsigned long int D)
! 1152: - Function: int mpz_congruent_2exp_p (mpz_t N, mpz_t C, unsigned long
! 1153: int B)
! 1154: Return non-zero if N is congruent to C modulo D, or in the case of
! 1155: `mpz_congruent_2exp_p' modulo 2^B.
1.1 maekawa 1156:
1157:
1.1.1.4 ! ohara 1158: File: gmp.info, Node: Integer Exponentiation, Next: Integer Roots, Prev: Integer Division, Up: Integer Functions
1.1 maekawa 1159:
1.1.1.4 ! ohara 1160: Exponentiation Functions
! 1161: ========================
! 1162:
! 1163: - Function: void mpz_powm (mpz_t ROP, mpz_t BASE, mpz_t EXP, mpz_t MOD)
! 1164: - Function: void mpz_powm_ui (mpz_t ROP, mpz_t BASE, unsigned long int
! 1165: EXP, mpz_t MOD)
! 1166: Set ROP to (BASE raised to EXP) modulo MOD.
! 1167:
! 1168: Negative EXP is supported if an inverse BASE^-1 mod MOD exists
! 1169: (see `mpz_invert' in *Note Number Theoretic Functions::). If an
! 1170: inverse doesn't exist then a divide by zero is raised.
! 1171:
! 1172: - Function: void mpz_pow_ui (mpz_t ROP, mpz_t BASE, unsigned long int
! 1173: EXP)
! 1174: - Function: void mpz_ui_pow_ui (mpz_t ROP, unsigned long int BASE,
! 1175: unsigned long int EXP)
! 1176: Set ROP to BASE raised to EXP. The case 0^0 yields 1.
! 1177:
! 1178:
! 1179: File: gmp.info, Node: Integer Roots, Next: Number Theoretic Functions, Prev: Integer Exponentiation, Up: Integer Functions
! 1180:
! 1181: Root Extraction Functions
! 1182: =========================
! 1183:
! 1184: - Function: int mpz_root (mpz_t ROP, mpz_t OP, unsigned long int N)
! 1185: Set ROP to the truncated integer part of the Nth root of OP.
! 1186: Return non-zero if the computation was exact, i.e., if OP is ROP
! 1187: to the Nth power.
! 1188:
! 1189: - Function: void mpz_sqrt (mpz_t ROP, mpz_t OP)
! 1190: Set ROP to the truncated integer part of the square root of OP.
! 1191:
! 1192: - Function: void mpz_sqrtrem (mpz_t ROP1, mpz_t ROP2, mpz_t OP)
! 1193: Set ROP1 to the truncated integer part of the square root of OP,
! 1194: like `mpz_sqrt'. Set ROP2 to the remainder OP-ROP1*ROP1, which
! 1195: will be zero if OP is a perfect square.
! 1196:
! 1197: If ROP1 and ROP2 are the same variable, the results are undefined.
1.1 maekawa 1198:
1.1.1.4 ! ohara 1199: - Function: int mpz_perfect_power_p (mpz_t OP)
! 1200: Return non-zero if OP is a perfect power, i.e., if there exist
! 1201: integers A and B, with B>1, such that OP equals A raised to the
! 1202: power B.
! 1203:
! 1204: Under this definition both 0 and 1 are considered to be perfect
! 1205: powers. Negative values of OP are accepted, but of course can
! 1206: only be odd perfect powers.
! 1207:
! 1208: - Function: int mpz_perfect_square_p (mpz_t OP)
! 1209: Return non-zero if OP is a perfect square, i.e., if the square
! 1210: root of OP is an integer. Under this definition both 0 and 1 are
! 1211: considered to be perfect squares.
1.1 maekawa 1212:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gmp.info-2 CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gmp