Annotation of OpenXM_contrib/gmp/gmp.info-7, Revision 1.1
1.1 ! ohara 1: This is gmp.info, produced by makeinfo version 4.2 from gmp.texi.
! 2:
! 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::.
! 16: INFO-DIR-SECTION GNU libraries
! 17: START-INFO-DIR-ENTRY
! 18: * gmp: (gmp). GNU Multiple Precision Arithmetic Library.
! 19: END-INFO-DIR-ENTRY
! 20:
! 21:
! 22: File: gmp.info, Node: Assembler Cache Handling, Next: Assembler Floating Point, Prev: Assembler Carry Propagation, Up: Assembler Coding
! 23:
! 24: Cache Handling
! 25: --------------
! 26:
! 27: GMP aims to perform well both on operands that fit entirely in L1
! 28: cache and those which don't.
! 29:
! 30: Basic routines like `mpn_add_n' or `mpn_lshift' are often used on
! 31: large operands, so L2 and main memory performance is important for them.
! 32: `mpn_mul_1' and `mpn_addmul_1' are mostly used for multiply and square
! 33: basecases, so L1 performance matters most for them, unless assembler
! 34: versions of `mpn_mul_basecase' and `mpn_sqr_basecase' exist, in which
! 35: case the remaining uses are mostly for larger operands.
! 36:
! 37: For L2 or main memory operands, memory access times will almost
! 38: certainly be more than the calculation time. The aim therefore is to
! 39: maximize memory throughput, by starting a load of the next cache line
! 40: which processing the contents of the previous one. Clearly this is
! 41: only possible if the chip has a lock-up free cache or some sort of
! 42: prefetch instruction. Most current chips have both these features.
! 43:
! 44: Prefetching sources combines well with loop unrolling, since a
! 45: prefetch can be initiated once per unrolled loop (or more than once if
! 46: the loop covers more than one cache line).
! 47:
! 48: On CPUs without write-allocate caches, prefetching destinations will
! 49: ensure individual stores don't go further down the cache hierarchy,
! 50: limiting bandwidth. Of course for calculations which are slow anyway,
! 51: like `mpn_divrem_1', write-throughs might be fine.
! 52:
! 53: The distance ahead to prefetch will be determined by memory latency
! 54: versus throughput. The aim of course is to have data arriving
! 55: continuously, at peak throughput. Some CPUs have limits on the number
! 56: of fetches or prefetches in progress.
! 57:
! 58: If a special prefetch instruction doesn't exist then a plain load
! 59: can be used, but in that case care must be taken not to attempt to read
! 60: past the end of an operand, since that might produce a segmentation
! 61: violation.
! 62:
! 63: Some CPUs or systems have hardware that detects sequential memory
! 64: accesses and initiates suitable cache movements automatically, making
! 65: life easy.
! 66:
! 67:
! 68: File: gmp.info, Node: Assembler Floating Point, Next: Assembler SIMD Instructions, Prev: Assembler Cache Handling, Up: Assembler Coding
! 69:
! 70: Floating Point
! 71: --------------
! 72:
! 73: Floating point arithmetic is used in GMP for multiplications on CPUs
! 74: with poor integer multipliers. It's mostly useful for `mpn_mul_1',
! 75: `mpn_addmul_1' and `mpn_submul_1' on 64-bit machines, and
! 76: `mpn_mul_basecase' on both 32-bit and 64-bit machines.
! 77:
! 78: With IEEE 53-bit double precision floats, integer multiplications
! 79: producing up to 53 bits will give exact results. Breaking a 64x64
! 80: multiplication into eight 16x32->48 bit pieces is convenient. With
! 81: some care though six 21x32->53 bit products can be used, if one of the
! 82: lower two 21-bit pieces also uses the sign bit.
! 83:
! 84: For the `mpn_mul_1' family of functions on a 64-bit machine, the
! 85: invariant single limb is split at the start, into 3 or 4 pieces.
! 86: Inside the loop, the bignum operand is split into 32-bit pieces. Fast
! 87: conversion of these unsigned 32-bit pieces to floating point is highly
! 88: machine-dependent. In some cases, reading the data into the integer
! 89: unit, zero-extending to 64-bits, then transferring to the floating
! 90: point unit back via memory is the only option.
! 91:
! 92: Converting partial products back to 64-bit limbs is usually best
! 93: done as a signed conversion. Since all values are smaller than 2^53,
! 94: signed and unsigned are the same, but most processors lack unsigned
! 95: conversions.
! 96:
! 97:
! 98:
! 99: Here is a diagram showing 16x32 bit products for an `mpn_mul_1' or
! 100: `mpn_addmul_1' with a 64-bit limb. The single limb operand V is split
! 101: into four 16-bit parts. The multi-limb operand U is split in the loop
! 102: into two 32-bit parts.
! 103:
! 104: +---+---+---+---+
! 105: |v48|v32|v16|v00| V operand
! 106: +---+---+---+---+
! 107:
! 108: +-------+---+---+
! 109: x | u32 | u00 | U operand (one limb)
! 110: +---------------+
! 111:
! 112: ---------------------------------
! 113:
! 114: +-----------+
! 115: | u00 x v00 | p00 48-bit products
! 116: +-----------+
! 117: +-----------+
! 118: | u00 x v16 | p16
! 119: +-----------+
! 120: +-----------+
! 121: | u00 x v32 | p32
! 122: +-----------+
! 123: +-----------+
! 124: | u00 x v48 | p48
! 125: +-----------+
! 126: +-----------+
! 127: | u32 x v00 | r32
! 128: +-----------+
! 129: +-----------+
! 130: | u32 x v16 | r48
! 131: +-----------+
! 132: +-----------+
! 133: | u32 x v32 | r64
! 134: +-----------+
! 135: +-----------+
! 136: | u32 x v48 | r80
! 137: +-----------+
! 138:
! 139: p32 and r32 can be summed using floating-point addition, and
! 140: likewise p48 and r48. p00 and p16 can be summed with r64 and r80 from
! 141: the previous iteration.
! 142:
! 143: For each loop then, four 49-bit quantities are transfered to the
! 144: integer unit, aligned as follows,
! 145:
! 146: |-----64bits----|-----64bits----|
! 147: +------------+
! 148: | p00 + r64' | i00
! 149: +------------+
! 150: +------------+
! 151: | p16 + r80' | i16
! 152: +------------+
! 153: +------------+
! 154: | p32 + r32 | i32
! 155: +------------+
! 156: +------------+
! 157: | p48 + r48 | i48
! 158: +------------+
! 159:
! 160: The challenge then is to sum these efficiently and add in a carry
! 161: limb, generating a low 64-bit result limb and a high 33-bit carry limb
! 162: (i48 extends 33 bits into the high half).
! 163:
! 164:
! 165: File: gmp.info, Node: Assembler SIMD Instructions, Next: Assembler Software Pipelining, Prev: Assembler Floating Point, Up: Assembler Coding
! 166:
! 167: SIMD Instructions
! 168: -----------------
! 169:
! 170: The single-instruction multiple-data support in current
! 171: microprocessors is aimed at signal processing algorithms where each
! 172: data point can be treated more or less independently. There's
! 173: generally not much support for propagating the sort of carries that
! 174: arise in GMP.
! 175:
! 176: SIMD multiplications of say four 16x16 bit multiplies only do as much
! 177: work as one 32x32 from GMP's point of view, and need some shifts and
! 178: adds besides. But of course if say the SIMD form is fully pipelined
! 179: and uses less instruction decoding then it may still be worthwhile.
! 180:
! 181: On the 80x86 chips, MMX has so far found a use in `mpn_rshift' and
! 182: `mpn_lshift' since it allows 64-bit operations, and is used in a special
! 183: case for 16-bit multipliers in the P55 `mpn_mul_1'. 3DNow and SSE
! 184: haven't found a use so far.
! 185:
! 186:
! 187: File: gmp.info, Node: Assembler Software Pipelining, Next: Assembler Loop Unrolling, Prev: Assembler SIMD Instructions, Up: Assembler Coding
! 188:
! 189: Software Pipelining
! 190: -------------------
! 191:
! 192: Software pipelining consists of scheduling instructions around the
! 193: branch point in a loop. For example a loop taking a checksum of an
! 194: array of limbs might have a load and an add, but the load wouldn't be
! 195: for that add, rather for the one next time around the loop. Each load
! 196: then is effectively scheduled back in the previous iteration, allowing
! 197: latency to be hidden.
! 198:
! 199: Naturally this is wanted only when doing things like loads or
! 200: multiplies that take a few cycles to complete, and only where a CPU has
! 201: multiple functional units so that other work can be done while waiting.
! 202:
! 203: A pipeline with several stages will have a data value in progress at
! 204: each stage and each loop iteration moves them along one stage. This is
! 205: like juggling.
! 206:
! 207: Within the loop some moves between registers may be necessary to
! 208: have the right values in the right places for each iteration. Loop
! 209: unrolling can help this, with each unrolled block able to use different
! 210: registers for different values, even if some shuffling is still needed
! 211: just before going back to the top of the loop.
! 212:
! 213:
! 214: File: gmp.info, Node: Assembler Loop Unrolling, Prev: Assembler Software Pipelining, Up: Assembler Coding
! 215:
! 216: Loop Unrolling
! 217: --------------
! 218:
! 219: Loop unrolling consists of replicating code so that several limbs are
! 220: processed in each loop. At a minimum this reduces loop overheads by a
! 221: corresponding factor, but it can also allow better register usage, for
! 222: example alternately using one register combination and then another.
! 223: Judicious use of `m4' macros can help avoid lots of duplication in the
! 224: source code.
! 225:
! 226: Unrolling is commonly done to a power of 2 multiple so the number of
! 227: unrolled loops and the number of remaining limbs can be calculated with
! 228: a shift and mask. But other multiples can be used too, just by
! 229: subtracting each N limbs processed from a counter and waiting for less
! 230: than N remaining (or offsetting the counter by N so it goes negative
! 231: when there's less than N remaining).
! 232:
! 233: The limbs not a multiple of the unrolling can be handled in various
! 234: ways, for example
! 235:
! 236: * A simple loop at the end (or the start) to process the excess.
! 237: Care will be wanted that it isn't too much slower than the
! 238: unrolled part.
! 239:
! 240: * A set of binary tests, for example after an 8-limb unrolling, test
! 241: for 4 more limbs to process, then a further 2 more or not, and
! 242: finally 1 more or not. This will probably take more code space
! 243: than a simple loop.
! 244:
! 245: * A `switch' statement, providing separate code for each possible
! 246: excess, for example an 8-limb unrolling would have separate code
! 247: for 0 remaining, 1 remaining, etc, up to 7 remaining. This might
! 248: take a lot of code, but may be the best way to optimize all cases
! 249: in combination with a deep pipelined loop.
! 250:
! 251: * A computed jump into the middle of the loop, thus making the first
! 252: iteration handle the excess. This should make times smoothly
! 253: increase with size, which is attractive, but setups for the jump
! 254: and adjustments for pointers can be tricky and could become quite
! 255: difficult in combination with deep pipelining.
! 256:
! 257: One way to write the setups and finishups for a pipelined unrolled
! 258: loop is simply to duplicate the loop at the start and the end, then
! 259: delete instructions at the start which have no valid antecedents, and
! 260: delete instructions at the end whose results are unwanted. Sizes not a
! 261: multiple of the unrolling can then be handled as desired.
! 262:
! 263:
! 264: File: gmp.info, Node: Internals, Next: Contributors, Prev: Algorithms, Up: Top
! 265:
! 266: Internals
! 267: *********
! 268:
! 269: *This chapter is provided only for informational purposes and the
! 270: various internals described here may change in future GMP releases.
! 271: Applications expecting to be compatible with future releases should use
! 272: only the documented interfaces described in previous chapters.*
! 273:
! 274: * Menu:
! 275:
! 276: * Integer Internals::
! 277: * Rational Internals::
! 278: * Float Internals::
! 279: * Raw Output Internals::
! 280: * C++ Interface Internals::
! 281:
! 282:
! 283: File: gmp.info, Node: Integer Internals, Next: Rational Internals, Prev: Internals, Up: Internals
! 284:
! 285: Integer Internals
! 286: =================
! 287:
! 288: `mpz_t' variables represent integers using sign and magnitude, in
! 289: space dynamically allocated and reallocated. The fields are as follows.
! 290:
! 291: `_mp_size'
! 292: The number of limbs, or the negative of that when representing a
! 293: negative integer. Zero is represented by `_mp_size' set to zero,
! 294: in which case the `_mp_d' data is unused.
! 295:
! 296: `_mp_d'
! 297: A pointer to an array of limbs which is the magnitude. These are
! 298: stored "little endian" as per the `mpn' functions, so `_mp_d[0]'
! 299: is the least significant limb and `_mp_d[ABS(_mp_size)-1]' is the
! 300: most significant. Whenever `_mp_size' is non-zero, the most
! 301: significant limb is non-zero.
! 302:
! 303: Currently there's always at least one limb allocated, so for
! 304: instance `mpz_set_ui' never needs to reallocate, and `mpz_get_ui'
! 305: can fetch `_mp_d[0]' unconditionally (though its value is then
! 306: only wanted if `_mp_size' is non-zero).
! 307:
! 308: `_mp_alloc'
! 309: `_mp_alloc' is the number of limbs currently allocated at `_mp_d',
! 310: and naturally `_mp_alloc >= ABS(_mp_size)'. When an `mpz' routine
! 311: is about to (or might be about to) increase `_mp_size', it checks
! 312: `_mp_alloc' to see whether there's enough space, and reallocates
! 313: if not. `MPZ_REALLOC' is generally used for this.
! 314:
! 315: The various bitwise logical functions like `mpz_and' behave as if
! 316: negative values were twos complement. But sign and magnitude is always
! 317: used internally, and necessary adjustments are made during the
! 318: calculations. Sometimes this isn't pretty, but sign and magnitude are
! 319: best for other routines.
! 320:
! 321: Some internal temporary variables are setup with `MPZ_TMP_INIT' and
! 322: these have `_mp_d' space obtained from `TMP_ALLOC' rather than the
! 323: memory allocation functions. Care is taken to ensure that these are
! 324: big enough that no reallocation is necessary (since it would have
! 325: unpredictable consequences).
! 326:
! 327:
! 328: File: gmp.info, Node: Rational Internals, Next: Float Internals, Prev: Integer Internals, Up: Internals
! 329:
! 330: Rational Internals
! 331: ==================
! 332:
! 333: `mpq_t' variables represent rationals using an `mpz_t' numerator and
! 334: denominator (*note Integer Internals::).
! 335:
! 336: The canonical form adopted is denominator positive (and non-zero),
! 337: no common factors between numerator and denominator, and zero uniquely
! 338: represented as 0/1.
! 339:
! 340: It's believed that casting out common factors at each stage of a
! 341: calculation is best in general. A GCD is an O(N^2) operation so it's
! 342: better to do a few small ones immediately than to delay and have to do
! 343: a big one later. Knowing the numerator and denominator have no common
! 344: factors can be used for example in `mpq_mul' to make only two cross
! 345: GCDs necessary, not four.
! 346:
! 347: This general approach to common factors is badly sub-optimal in the
! 348: presence of simple factorizations or little prospect for cancellation,
! 349: but GMP has no way to know when this will occur. As per *Note
! 350: Efficiency::, that's left to applications. The `mpq_t' framework might
! 351: still suit, with `mpq_numref' and `mpq_denref' for direct access to the
! 352: numerator and denominator, or of course `mpz_t' variables can be used
! 353: directly.
! 354:
! 355:
! 356: File: gmp.info, Node: Float Internals, Next: Raw Output Internals, Prev: Rational Internals, Up: Internals
! 357:
! 358: Float Internals
! 359: ===============
! 360:
! 361: Efficient calculation is the primary aim of GMP floats and the use
! 362: of whole limbs and simple rounding facilitates this.
! 363:
! 364: `mpf_t' floats have a variable precision mantissa and a single
! 365: machine word signed exponent. The mantissa is represented using sign
! 366: and magnitude.
! 367:
! 368: most least
! 369: significant significant
! 370: limb limb
! 371:
! 372: _mp_d
! 373: |---- _mp_exp ---> |
! 374: _____ _____ _____ _____ _____
! 375: |_____|_____|_____|_____|_____|
! 376: . <------------ radix point
! 377:
! 378: <-------- _mp_size --------->
! 379:
! 380: The fields are as follows.
! 381:
! 382: `_mp_size'
! 383: The number of limbs currently in use, or the negative of that when
! 384: representing a negative value. Zero is represented by `_mp_size'
! 385: and `_mp_exp' both set to zero, and in that case the `_mp_d' data
! 386: is unused. (In the future `_mp_exp' might be undefined when
! 387: representing zero.)
! 388:
! 389: `_mp_prec'
! 390: The precision of the mantissa, in limbs. In any calculation the
! 391: aim is to produce `_mp_prec' limbs of result (the most significant
! 392: being non-zero).
! 393:
! 394: `_mp_d'
! 395: A pointer to the array of limbs which is the absolute value of the
! 396: mantissa. These are stored "little endian" as per the `mpn'
! 397: functions, so `_mp_d[0]' is the least significant limb and
! 398: `_mp_d[ABS(_mp_size)-1]' the most significant.
! 399:
! 400: The most significant limb is always non-zero, but there are no
! 401: other restrictions on its value, in particular the highest 1 bit
! 402: can be anywhere within the limb.
! 403:
! 404: `_mp_prec+1' limbs are allocated to `_mp_d', the extra limb being
! 405: for convenience (see below). There are no reallocations during a
! 406: calculation, only in a change of precision with `mpf_set_prec'.
! 407:
! 408: `_mp_exp'
! 409: The exponent, in limbs, determining the location of the implied
! 410: radix point. Zero means the radix point is just above the most
! 411: significant limb. Positive values mean a radix point offset
! 412: towards the lower limbs and hence a value >= 1, as for example in
! 413: the diagram above. Negative exponents mean a radix point further
! 414: above the highest limb.
! 415:
! 416: Naturally the exponent can be any value, it doesn't have to fall
! 417: within the limbs as the diagram shows, it can be a long way above
! 418: or a long way below. Limbs other than those included in the
! 419: `{_mp_d,_mp_size}' data are treated as zero.
! 420:
! 421:
! 422: The following various points should be noted.
! 423:
! 424: Low Zeros
! 425: The least significant limbs `_mp_d[0]' etc can be zero, though
! 426: such low zeros can always be ignored. Routines likely to produce
! 427: low zeros check and avoid them to save time in subsequent
! 428: calculations, but for most routines they're quite unlikely and
! 429: aren't checked.
! 430:
! 431: Mantissa Size Range
! 432: The `_mp_size' count of limbs in use can be less than `_mp_prec' if
! 433: the value can be represented in less. This means low precision
! 434: values or small integers stored in a high precision `mpf_t' can
! 435: still be operated on efficiently.
! 436:
! 437: `_mp_size' can also be greater than `_mp_prec'. Firstly a value is
! 438: allowed to use all of the `_mp_prec+1' limbs available at `_mp_d',
! 439: and secondly when `mpf_set_prec_raw' lowers `_mp_prec' it leaves
! 440: `_mp_size' unchanged and so the size can be arbitrarily bigger than
! 441: `_mp_prec'.
! 442:
! 443: Rounding
! 444: All rounding is done on limb boundaries. Calculating `_mp_prec'
! 445: limbs with the high non-zero will ensure the application requested
! 446: minimum precision is obtained.
! 447:
! 448: The use of simple "trunc" rounding towards zero is efficient,
! 449: since there's no need to examine extra limbs and increment or
! 450: decrement.
! 451:
! 452: Bit Shifts
! 453: Since the exponent is in limbs, there are no bit shifts in basic
! 454: operations like `mpf_add' and `mpf_mul'. When differing exponents
! 455: are encountered all that's needed is to adjust pointers to line up
! 456: the relevant limbs.
! 457:
! 458: Of course `mpf_mul_2exp' and `mpf_div_2exp' will require bit
! 459: shifts, but the choice is between an exponent in limbs which
! 460: requires shifts there, or one in bits which requires them almost
! 461: everywhere else.
! 462:
! 463: Use of `_mp_prec+1' Limbs
! 464: The extra limb on `_mp_d' (`_mp_prec+1' rather than just
! 465: `_mp_prec') helps when an `mpf' routine might get a carry from its
! 466: operation. `mpf_add' for instance will do an `mpn_add' of
! 467: `_mp_prec' limbs. If there's no carry then that's the result, but
! 468: if there is a carry then it's stored in the extra limb of space and
! 469: `_mp_size' becomes `_mp_prec+1'.
! 470:
! 471: Whenever `_mp_prec+1' limbs are held in a variable, the low limb
! 472: is not needed for the intended precision, only the `_mp_prec' high
! 473: limbs. But zeroing it out or moving the rest down is unnecessary.
! 474: Subsequent routines reading the value will simply take the high
! 475: limbs they need, and this will be `_mp_prec' if their target has
! 476: that same precision. This is no more than a pointer adjustment,
! 477: and must be checked anyway since the destination precision can be
! 478: different from the sources.
! 479:
! 480: Copy functions like `mpf_set' will retain a full `_mp_prec+1' limbs
! 481: if available. This ensures that a variable which has `_mp_size'
! 482: equal to `_mp_prec+1' will get its full exact value copied.
! 483: Strictly speaking this is unnecessary since only `_mp_prec' limbs
! 484: are needed for the application's requested precision, but it's
! 485: considered that an `mpf_set' from one variable into another of the
! 486: same precision ought to produce an exact copy.
! 487:
! 488: Application Precisions
! 489: `__GMPF_BITS_TO_PREC' converts an application requested precision
! 490: to an `_mp_prec'. The value in bits is rounded up to a whole limb
! 491: then an extra limb is added since the most significant limb of
! 492: `_mp_d' is only non-zero and therefore might contain only one bit.
! 493:
! 494: `__GMPF_PREC_TO_BITS' does the reverse conversion, and removes the
! 495: extra limb from `_mp_prec' before converting to bits. The net
! 496: effect of reading back with `mpf_get_prec' is simply the precision
! 497: rounded up to a multiple of `mp_bits_per_limb'.
! 498:
! 499: Note that the extra limb added here for the high only being
! 500: non-zero is in addition to the extra limb allocated to `_mp_d'.
! 501: For example with a 32-bit limb, an application request for 250
! 502: bits will be rounded up to 8 limbs, then an extra added for the
! 503: high being only non-zero, giving an `_mp_prec' of 9. `_mp_d' then
! 504: gets 10 limbs allocated. Reading back with `mpf_get_prec' will
! 505: take `_mp_prec' subtract 1 limb and multiply by 32, giving 256
! 506: bits.
! 507:
! 508: Strictly speaking, the fact the high limb has at least one bit
! 509: means that a float with, say, 3 limbs of 32-bits each will be
! 510: holding at least 65 bits, but for the purposes of `mpf_t' it's
! 511: considered simply to be 64 bits, a nice multiple of the limb size.
! 512:
! 513:
! 514: File: gmp.info, Node: Raw Output Internals, Next: C++ Interface Internals, Prev: Float Internals, Up: Internals
! 515:
! 516: Raw Output Internals
! 517: ====================
! 518:
! 519: `mpz_out_raw' uses the following format.
! 520:
! 521: +------+------------------------+
! 522: | size | data bytes |
! 523: +------+------------------------+
! 524:
! 525: The size is 4 bytes written most significant byte first, being the
! 526: number of subsequent data bytes, or the twos complement negative of
! 527: that when a negative integer is represented. The data bytes are the
! 528: absolute value of the integer, written most significant byte first.
! 529:
! 530: The most significant data byte is always non-zero, so the output is
! 531: the same on all systems, irrespective of limb size.
! 532:
! 533: In GMP 1, leading zero bytes were written to pad the data bytes to a
! 534: multiple of the limb size. `mpz_inp_raw' will still accept this, for
! 535: compatibility.
! 536:
! 537: The use of "big endian" for both the size and data fields is
! 538: deliberate, it makes the data easy to read in a hex dump of a file.
! 539: Unfortunately it also means that the limb data must be reversed when
! 540: reading or writing, so neither a big endian nor little endian system
! 541: can just read and write `_mp_d'.
! 542:
! 543:
! 544: File: gmp.info, Node: C++ Interface Internals, Prev: Raw Output Internals, Up: Internals
! 545:
! 546: C++ Interface Internals
! 547: =======================
! 548:
! 549: A system of expression templates is used to ensure something like
! 550: `a=b+c' turns into a simple call to `mpz_add' etc. For `mpf_class' and
! 551: `mpfr_class' the scheme also ensures the precision of the final
! 552: destination is used for any temporaries within a statement like
! 553: `f=w*x+y*z'. These are important features which a naive implementation
! 554: cannot provide.
! 555:
! 556: A simplified description of the scheme follows. The true scheme is
! 557: complicated by the fact that expressions have different return types.
! 558: For detailed information, refer to the source code.
! 559:
! 560: To perform an operation, say, addition, we first define a "function
! 561: object" evaluating it,
! 562:
! 563: struct __gmp_binary_plus
! 564: {
! 565: static void eval(mpf_t f, mpf_t g, mpf_t h) { mpf_add(f, g, h); }
! 566: };
! 567:
! 568: And an "additive expression" object,
! 569:
! 570: __gmp_expr<__gmp_binary_expr<mpf_class, mpf_class, __gmp_binary_plus> >
! 571: operator+(const mpf_class &f, const mpf_class &g)
! 572: {
! 573: return __gmp_expr
! 574: <__gmp_binary_expr<mpf_class, mpf_class, __gmp_binary_plus> >(f, g);
! 575: }
! 576:
! 577: The seemingly redundant `__gmp_expr<__gmp_binary_expr<...>>' is used
! 578: to encapsulate any possible kind of expression into a single template
! 579: type. In fact even `mpf_class' etc are `typedef' specializations of
! 580: `__gmp_expr'.
! 581:
! 582: Next we define assignment of `__gmp_expr' to `mpf_class'.
! 583:
! 584: template <class T>
! 585: mpf_class & mpf_class::operator=(const __gmp_expr<T> &expr)
! 586: {
! 587: expr.eval(this->get_mpf_t(), this->precision());
! 588: return *this;
! 589: }
! 590:
! 591: template <class Op>
! 592: void __gmp_expr<__gmp_binary_expr<mpf_class, mpf_class, Op> >::eval
! 593: (mpf_t f, unsigned long int precision)
! 594: {
! 595: Op::eval(f, expr.val1.get_mpf_t(), expr.val2.get_mpf_t());
! 596: }
! 597:
! 598: where `expr.val1' and `expr.val2' are references to the expression's
! 599: operands (here `expr' is the `__gmp_binary_expr' stored within the
! 600: `__gmp_expr').
! 601:
! 602: This way, the expression is actually evaluated only at the time of
! 603: assignment, when the required precision (that of `f') is known.
! 604: Furthermore the target `mpf_t' is now available, thus we can call
! 605: `mpf_add' directly with `f' as the output argument.
! 606:
! 607: Compound expressions are handled by defining operators taking
! 608: subexpressions as their arguments, like this:
! 609:
! 610: template <class T, class U>
! 611: __gmp_expr
! 612: <__gmp_binary_expr<__gmp_expr<T>, __gmp_expr<U>, __gmp_binary_plus> >
! 613: operator+(const __gmp_expr<T> &expr1, const __gmp_expr<U> &expr2)
! 614: {
! 615: return __gmp_expr
! 616: <__gmp_binary_expr<__gmp_expr<T>, __gmp_expr<U>, __gmp_binary_plus> >
! 617: (expr1, expr2);
! 618: }
! 619:
! 620: And the corresponding specializations of `__gmp_expr::eval':
! 621:
! 622: template <class T, class U, class Op>
! 623: void __gmp_expr
! 624: <__gmp_binary_expr<__gmp_expr<T>, __gmp_expr<U>, Op> >::eval
! 625: (mpf_t f, unsigned long int precision)
! 626: {
! 627: // declare two temporaries
! 628: mpf_class temp1(expr.val1, precision), temp2(expr.val2, precision);
! 629: Op::eval(f, temp1.get_mpf_t(), temp2.get_mpf_t());
! 630: }
! 631:
! 632: The expression is thus recursively evaluated to any level of
! 633: complexity and all subexpressions are evaluated to the precision of `f'.
! 634:
! 635:
! 636: File: gmp.info, Node: Contributors, Next: References, Prev: Internals, Up: Top
! 637:
! 638: Contributors
! 639: ************
! 640:
! 641: Torbjorn Granlund wrote the original GMP library and is still
! 642: developing and maintaining it. Several other individuals and
! 643: organizations have contributed to GMP in various ways. Here is a list
! 644: in chronological order:
! 645:
! 646: Gunnar Sjoedin and Hans Riesel helped with mathematical problems in
! 647: early versions of the library.
! 648:
! 649: Richard Stallman contributed to the interface design and revised the
! 650: first version of this manual.
! 651:
! 652: Brian Beuning and Doug Lea helped with testing of early versions of
! 653: the library and made creative suggestions.
! 654:
! 655: John Amanatides of York University in Canada contributed the function
! 656: `mpz_probab_prime_p'.
! 657:
! 658: Paul Zimmermann of Inria sparked the development of GMP 2, with his
! 659: comparisons between bignum packages.
! 660:
! 661: Ken Weber (Kent State University, Universidade Federal do Rio Grande
! 662: do Sul) contributed `mpz_gcd', `mpz_divexact', `mpn_gcd', and
! 663: `mpn_bdivmod', partially supported by CNPq (Brazil) grant 301314194-2.
! 664:
! 665: Per Bothner of Cygnus Support helped to set up GMP to use Cygnus'
! 666: configure. He has also made valuable suggestions and tested numerous
! 667: intermediary releases.
! 668:
! 669: Joachim Hollman was involved in the design of the `mpf' interface,
! 670: and in the `mpz' design revisions for version 2.
! 671:
! 672: Bennet Yee contributed the initial versions of `mpz_jacobi' and
! 673: `mpz_legendre'.
! 674:
! 675: Andreas Schwab contributed the files `mpn/m68k/lshift.S' and
! 676: `mpn/m68k/rshift.S' (now in `.asm' form).
! 677:
! 678: The development of floating point functions of GNU MP 2, were
! 679: supported in part by the ESPRIT-BRA (Basic Research Activities) 6846
! 680: project POSSO (POlynomial System SOlving).
! 681:
! 682: GNU MP 2 was finished and released by SWOX AB, SWEDEN, in
! 683: cooperation with the IDA Center for Computing Sciences, USA.
! 684:
! 685: Robert Harley of Inria, France and David Seal of ARM, England,
! 686: suggested clever improvements for population count.
! 687:
! 688: Robert Harley also wrote highly optimized Karatsuba and 3-way Toom
! 689: multiplication functions for GMP 3. He also contributed the ARM
! 690: assembly code.
! 691:
! 692: Torsten Ekedahl of the Mathematical department of Stockholm
! 693: University provided significant inspiration during several phases of
! 694: the GMP development. His mathematical expertise helped improve several
! 695: algorithms.
! 696:
! 697: Paul Zimmermann wrote the Divide and Conquer division code, the REDC
! 698: code, the REDC-based mpz_powm code, the FFT multiply code, and the
! 699: Karatsuba square root. The ECMNET project Paul is organizing was a
! 700: driving force behind many of the optimizations in GMP 3.
! 701:
! 702: Linus Nordberg wrote the new configure system based on autoconf and
! 703: implemented the new random functions.
! 704:
! 705: Kent Boortz made the Macintosh port.
! 706:
! 707: Kevin Ryde worked on a number of things: optimized x86 code, m4 asm
! 708: macros, parameter tuning, speed measuring, the configure system,
! 709: function inlining, divisibility tests, bit scanning, Jacobi symbols,
! 710: Fibonacci and Lucas number functions, printf and scanf functions, perl
! 711: interface, demo expression parser, the algorithms chapter in the
! 712: manual, `gmpasm-mode.el', and various miscellaneous improvements
! 713: elsewhere.
! 714:
! 715: Steve Root helped write the optimized alpha 21264 assembly code.
! 716:
! 717: Gerardo Ballabio wrote the `gmpxx.h' C++ class interface and the C++
! 718: `istream' input routines.
! 719:
! 720: GNU MP 4.0 was finished and released by Torbjorn Granlund and Kevin
! 721: Ryde. Torbjorn's work was partially funded by the IDA Center for
! 722: Computing Sciences, USA.
! 723:
! 724: (This list is chronological, not ordered after significance. If you
! 725: have contributed to GMP but are not listed above, please tell
! 726: <tege@swox.com> about the omission!)
! 727:
! 728: Thanks goes to Hans Thorsen for donating an SGI system for the GMP
! 729: test system environment.
! 730:
! 731:
! 732: File: gmp.info, Node: References, Next: GNU Free Documentation License, Prev: Contributors, Up: Top
! 733:
! 734: References
! 735: **********
! 736:
! 737: Books
! 738: =====
! 739:
! 740: * Jonathan M. Borwein and Peter B. Borwein, "Pi and the AGM: A Study
! 741: in Analytic Number Theory and Computational Complexity", Wiley,
! 742: John & Sons, 1998.
! 743:
! 744: * Henri Cohen, "A Course in Computational Algebraic Number Theory",
! 745: Graduate Texts in Mathematics number 138, Springer-Verlag, 1993.
! 746: `http://www.math.u-bordeaux.fr/~cohen'
! 747:
! 748: * Donald E. Knuth, "The Art of Computer Programming", volume 2,
! 749: "Seminumerical Algorithms", 3rd edition, Addison-Wesley, 1998.
! 750: `http://www-cs-faculty.stanford.edu/~knuth/taocp.html'
! 751:
! 752: * John D. Lipson, "Elements of Algebra and Algebraic Computing", The
! 753: Benjamin Cummings Publishing Company Inc, 1981.
! 754:
! 755: * Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone,
! 756: "Handbook of Applied Cryptography",
! 757: `http://www.cacr.math.uwaterloo.ca/hac/'
! 758:
! 759: * Richard M. Stallman, "Using and Porting GCC", Free Software
! 760: Foundation, 1999, available online
! 761: `http://www.gnu.org/software/gcc/onlinedocs/', and in the GCC
! 762: package `ftp://ftp.gnu.org/gnu/gcc/'
! 763:
! 764: Papers
! 765: ======
! 766:
! 767: * Christoph Burnikel and Joachim Ziegler, "Fast Recursive Division",
! 768: Max-Planck-Institut fuer Informatik Research Report
! 769: MPI-I-98-1-022,
! 770: `http://data.mpi-sb.mpg.de/internet/reports.nsf/NumberView/1998-1-022'
! 771:
! 772: * Torbjorn Granlund and Peter L. Montgomery, "Division by Invariant
! 773: Integers using Multiplication", in Proceedings of the SIGPLAN
! 774: PLDI'94 Conference, June 1994. Also available
! 775: `ftp://ftp.cwi.nl/pub/pmontgom/divcnst.psa4.gz' (and .psl.gz).
! 776:
! 777: * Peter L. Montgomery, "Modular Multiplication Without Trial
! 778: Division", in Mathematics of Computation, volume 44, number 170,
! 779: April 1985.
! 780:
! 781: * Tudor Jebelean, "An algorithm for exact division", Journal of
! 782: Symbolic Computation, volume 15, 1993, pp. 169-180. Research
! 783: report version available
! 784: `ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1992/92-35.ps.gz'
! 785:
! 786: * Tudor Jebelean, "Exact Division with Karatsuba Complexity -
! 787: Extended Abstract", RISC-Linz technical report 96-31,
! 788: `ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1996/96-31.ps.gz'
! 789:
! 790: * Tudor Jebelean, "Practical Integer Division with Karatsuba
! 791: Complexity", ISSAC 97, pp. 339-341. Technical report available
! 792: `ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1996/96-29.ps.gz'
! 793:
! 794: * Tudor Jebelean, "A Generalization of the Binary GCD Algorithm",
! 795: ISSAC 93, pp. 111-116. Technical report version available
! 796: `ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1993/93-01.ps.gz'
! 797:
! 798: * Tudor Jebelean, "A Double-Digit Lehmer-Euclid Algorithm for
! 799: Finding the GCD of Long Integers", Journal of Symbolic
! 800: Computation, volume 19, 1995, pp. 145-157. Technical report
! 801: version also available
! 802: `ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1992/92-69.ps.gz'
! 803:
! 804: * Werner Krandick and Tudor Jebelean, "Bidirectional Exact Integer
! 805: Division", Journal of Symbolic Computation, volume 21, 1996, pp.
! 806: 441-455. Early technical report version also available
! 807: `ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1994/94-50.ps.gz'
! 808:
! 809: * R. Moenck and A. Borodin, "Fast Modular Transforms via Division",
! 810: Proceedings of the 13th Annual IEEE Symposium on Switching and
! 811: Automata Theory, October 1972, pp. 90-96. Reprinted as "Fast
! 812: Modular Transforms", Journal of Computer and System Sciences,
! 813: volume 8, number 3, June 1974, pp. 366-386.
! 814:
! 815: * Arnold Scho"nhage and Volker Strassen, "Schnelle Multiplikation
! 816: grosser Zahlen", Computing 7, 1971, pp. 281-292.
! 817:
! 818: * Kenneth Weber, "The accelerated integer GCD algorithm", ACM
! 819: Transactions on Mathematical Software, volume 21, number 1, March
! 820: 1995, pp. 111-122.
! 821:
! 822: * Paul Zimmermann, "Karatsuba Square Root", INRIA Research Report
! 823: 3805, November 1999, `http://www.inria.fr/RRRT/RR-3805.html'
! 824:
! 825: * Paul Zimmermann, "A Proof of GMP Fast Division and Square Root
! 826: Implementations",
! 827: `http://www.loria.fr/~zimmerma/papers/proof-div-sqrt.ps.gz'
! 828:
! 829: * Dan Zuras, "On Squaring and Multiplying Large Integers", ARITH-11:
! 830: IEEE Symposium on Computer Arithmetic, 1993, pp. 260 to 271.
! 831: Reprinted as "More on Multiplying and Squaring Large Integers",
! 832: IEEE Transactions on Computers, volume 43, number 8, August 1994,
! 833: pp. 899-908.
! 834:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gmp.info-7 CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gmp