Annotation of OpenXM_contrib/gmp/gmp.info-3, Revision 1.1.1.3
1.1.1.2 maekawa 1: This is gmp.info, produced by makeinfo version 4.0 from gmp.texi.
1.1 maekawa 2:
1.1.1.2 maekawa 3: INFO-DIR-SECTION GNU libraries
1.1 maekawa 4: START-INFO-DIR-ENTRY
1.1.1.2 maekawa 5: * gmp: (gmp). GNU Multiple Precision Arithmetic Library.
1.1 maekawa 6: END-INFO-DIR-ENTRY
7:
8: This file documents GNU MP, a library for arbitrary-precision
9: arithmetic.
10:
1.1.1.2 maekawa 11: Copyright (C) 1991, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000
12: Free Software Foundation, Inc.
1.1 maekawa 13:
14: Permission is granted to make and distribute verbatim copies of this
15: manual provided the copyright notice and this permission notice are
16: preserved on all copies.
17:
18: Permission is granted to copy and distribute modified versions of
19: this manual under the conditions for verbatim copying, provided that
20: the entire resulting derived work is distributed under the terms of a
21: permission notice identical to this one.
22:
23: Permission is granted to copy and distribute translations of this
24: manual into another language, under the above conditions for modified
25: versions, except that this permission notice may be stated in a
26: translation approved by the Foundation.
27:
28:
1.1.1.2 maekawa 29: File: gmp.info, Node: Low-level Functions, Next: Random Number Functions, Prev: Floating-point Functions, Up: Top
1.1 maekawa 30:
1.1.1.2 maekawa 31: Low-level Functions
32: *******************
33:
34: This chapter describes low-level GMP functions, used to implement
35: the high-level GMP functions, but also intended for time-critical user
36: code.
37:
38: These functions start with the prefix `mpn_'.
39:
40: The `mpn' functions are designed to be as fast as possible, *not* to
41: provide a coherent calling interface. The different functions have
42: somewhat similar interfaces, but there are variations that make them
43: hard to use. These functions do as little as possible apart from the
44: real multiple precision computation, so that no time is spent on things
45: that not all callers need.
46:
47: A source operand is specified by a pointer to the least significant
48: limb and a limb count. A destination operand is specified by just a
49: pointer. It is the responsibility of the caller to ensure that the
50: destination has enough space for storing the result.
51:
52: With this way of specifying operands, it is possible to perform
53: computations on subranges of an argument, and store the result into a
54: subrange of a destination.
55:
56: A common requirement for all functions is that each source area
57: needs at least one limb. No size argument may be zero. Unless
58: otherwise stated, in-place operations are allowed where source and
59: destination are the same, but not where they only partly overlap.
60:
61: The `mpn' functions are the base for the implementation of the
62: `mpz_', `mpf_', and `mpq_' functions.
63:
64: This example adds the number beginning at S1P and the number
65: beginning at S2P and writes the sum at DESTP. All areas have SIZE
66: limbs.
67:
68: cy = mpn_add_n (destp, s1p, s2p, size)
69:
70: In the notation used here, a source operand is identified by the
71: pointer to the least significant limb, and the limb count in braces.
72: For example, {s1p, s1size}.
73:
74: - Function: mp_limb_t mpn_add_n (mp_limb_t *RP, const mp_limb_t *S1P,
75: const mp_limb_t *S2P, mp_size_t SIZE)
76: Add {S1P, SIZE} and {S2P, SIZE}, and write the SIZE least
77: significant limbs of the result to RP. Return carry, either 0 or
78: 1.
79:
80: This is the lowest-level function for addition. It is the
81: preferred function for addition, since it is written in assembly
82: for most targets. For addition of a variable to itself (i.e., S1P
83: equals S2P, use `mpn_lshift' with a count of 1 for optimal speed.
84:
85: - Function: mp_limb_t mpn_add_1 (mp_limb_t *RP, const mp_limb_t *S1P,
86: mp_size_t SIZE, mp_limb_t S2LIMB)
87: Add {S1P, SIZE} and S2LIMB, and write the SIZE least significant
88: limbs of the result to RP. Return carry, either 0 or 1.
89:
90: - Function: mp_limb_t mpn_add (mp_limb_t *RP, const mp_limb_t *S1P,
91: mp_size_t S1SIZE, const mp_limb_t *S2P, mp_size_t S2SIZE)
92: Add {S1P, S1SIZE} and {S2P, S2SIZE}, and write the S1SIZE least
93: significant limbs of the result to RP. Return carry, either 0 or
94: 1.
95:
96: This function requires that S1SIZE is greater than or equal to
97: S2SIZE.
98:
99: - Function: mp_limb_t mpn_sub_n (mp_limb_t *RP, const mp_limb_t *S1P,
100: const mp_limb_t *S2P, mp_size_t SIZE)
101: Subtract {S2P, S2SIZE} from {S1P, SIZE}, and write the SIZE least
102: significant limbs of the result to RP. Return borrow, either 0 or
103: 1.
104:
105: This is the lowest-level function for subtraction. It is the
106: preferred function for subtraction, since it is written in
107: assembly for most targets.
108:
109: - Function: mp_limb_t mpn_sub_1 (mp_limb_t *RP, const mp_limb_t *S1P,
110: mp_size_t SIZE, mp_limb_t S2LIMB)
111: Subtract S2LIMB from {S1P, SIZE}, and write the SIZE least
112: significant limbs of the result to RP. Return borrow, either 0 or
113: 1.
114:
115: - Function: mp_limb_t mpn_sub (mp_limb_t *RP, const mp_limb_t *S1P,
116: mp_size_t S1SIZE, const mp_limb_t *S2P, mp_size_t S2SIZE)
117: Subtract {S2P, S2SIZE} from {S1P, S1SIZE}, and write the S1SIZE
118: least significant limbs of the result to RP. Return borrow,
119: either 0 or 1.
120:
121: This function requires that S1SIZE is greater than or equal to
122: S2SIZE.
123:
124: - Function: void mpn_mul_n (mp_limb_t *RP, const mp_limb_t *S1P, const
125: mp_limb_t *S2P, mp_size_t SIZE)
126: Multiply {S1P, SIZE} and {S2P, SIZE}, and write the *entire*
127: result to RP.
128:
129: The destination has to have space for 2*SIZE limbs, even if the
130: significant result might be one limb smaller.
131:
132: - Function: mp_limb_t mpn_mul_1 (mp_limb_t *RP, const mp_limb_t *S1P,
133: mp_size_t SIZE, mp_limb_t S2LIMB)
134: Multiply {S1P, SIZE} and S2LIMB, and write the SIZE least
135: significant limbs of the product to RP. Return the most
136: significant limb of the product.
137:
138: This is a low-level function that is a building block for general
139: multiplication as well as other operations in GMP. It is written
140: in assembly for most targets.
141:
142: Don't call this function if S2LIMB is a power of 2; use
143: `mpn_lshift' with a count equal to the logarithm of S2LIMB
144: instead, for optimal speed.
145:
146: - Function: mp_limb_t mpn_addmul_1 (mp_limb_t *RP, const mp_limb_t
147: *S1P, mp_size_t SIZE, mp_limb_t S2LIMB)
148: Multiply {S1P, SIZE} and S2LIMB, and add the SIZE least
149: significant limbs of the product to {RP, SIZE} and write the
150: result to RP. Return the most significant limb of the product,
151: plus carry-out from the addition.
152:
153: This is a low-level function that is a building block for general
154: multiplication as well as other operations in GMP. It is written
155: in assembly for most targets.
156:
157: - Function: mp_limb_t mpn_submul_1 (mp_limb_t *RP, const mp_limb_t
158: *S1P, mp_size_t SIZE, mp_limb_t S2LIMB)
159: Multiply {S1P, SIZE} and S2LIMB, and subtract the SIZE least
160: significant limbs of the product from {RP, SIZE} and write the
161: result to RP. Return the most significant limb of the product,
162: minus borrow-out from the subtraction.
163:
164: This is a low-level function that is a building block for general
165: multiplication and division as well as other operations in GMP.
166: It is written in assembly for most targets.
167:
168: - Function: mp_limb_t mpn_mul (mp_limb_t *RP, const mp_limb_t *S1P,
169: mp_size_t S1SIZE, const mp_limb_t *S2P, mp_size_t S2SIZE)
170: Multiply {S1P, S1SIZE} and {S2P, S2SIZE}, and write the result to
171: RP. Return the most significant limb of the result.
172:
173: The destination has to have space for S1SIZE + S2SIZE limbs, even
174: if the result might be one limb smaller.
175:
176: This function requires that S1SIZE is greater than or equal to
177: S2SIZE. The destination must be distinct from either input
178: operands.
179:
1.1.1.3 ! maekawa 180: - Function: void mpn_tdiv_qr (mp_limb_t *QP, mp_limb_t *RP, mp_size_t
! 181: QXN, const mp_limb_t *NP, mp_size_t NN, const mp_limb_t *DP,
! 182: mp_size_t DN)
1.1.1.2 maekawa 183: Divide {NP, NN} by {DP, DN}. Write the quotient at QP and the
184: remainder at RP.
185:
186: The quotient written at QP will be NN - DN + 1 limbs. The
187: remainder written at RP will be DN limbs.
188:
189: It is required that NN is greater than or equal to DN. The QXN
190: operand must be zero.
191:
192: The quotient is rounded towards 0.
193:
194: No overlap between arguments is permitted.
195:
196: - Function: mp_limb_t mpn_divrem (mp_limb_t *R1P, mp_size_t XSIZE,
197: mp_limb_t *RS2P, mp_size_t RS2SIZE, const mp_limb_t *S3P,
198: mp_size_t S3SIZE)
199: [This function is obsolete. Please call `mpn_tdiv_qr' instead for
200: best performance.]
201:
202: Divide {RS2P, RS2SIZE} by {S3P, S3SIZE}, and write the quotient at
203: R1P, with the exception of the most significant limb, which is
204: returned. The remainder replaces the dividend at RS2P; it will be
205: S3SIZE limbs long (i.e., as many limbs as the divisor).
206:
207: In addition to an integer quotient, XSIZE fraction limbs are
208: developed, and stored after the integral limbs. For most usages,
209: XSIZE will be zero.
210:
211: It is required that RS2SIZE is greater than or equal to S3SIZE.
212: It is required that the most significant bit of the divisor is set.
213:
214: If the quotient is not needed, pass RS2P + S3SIZE as R1P. Aside
215: from that special case, no overlap between arguments is permitted.
216:
217: Return the most significant limb of the quotient, either 0 or 1.
218:
219: The area at R1P needs to be RS2SIZE - S3SIZE + XSIZE limbs large.
220:
221: - Function: mp_limb_t mpn_divrem_1 (mp_limb_t *R1P, mp_size_t XSIZE,
222: mp_limb_t *S2P, mp_size_t S2SIZE, mp_limb_t S3LIMB)
223: - Macro: mp_limb_t mpn_divmod_1 (mp_limb_t *R1P, mp_limb_t *S2P,
224: mp_size_t S2SIZE, mp_limb_t S3LIMB)
225: Divide {S2P, S2SIZE} by S3LIMB, and write the quotient at R1P.
226: Return the remainder.
227:
228: The integer quotient is written to {R1P+XSIZE, S2SIZE} and in
229: addition XSIZE fraction limbs are developed and written to {R1P,
230: XSIZE}. Either or both S2SIZE and XSIZE can be zero. For most
231: usages, XSIZE will be zero.
232:
233: `mpn_divmod_1' exists for upward source compatibility and is
234: simply a macro calling `mpn_divrem_1' with an XSIZE of 0.
235:
236: The areas at R1P and S2P have to be identical or completely
237: separate, not partially overlapping.
238:
239: - Function: mp_limb_t mpn_divmod (mp_limb_t *R1P, mp_limb_t *RS2P,
240: mp_size_t RS2SIZE, const mp_limb_t *S3P, mp_size_t S3SIZE)
241: *This interface is obsolete. It will disappear from future
242: releases. Use `mpn_divrem' in its stead.*
243:
244: - Macro: mp_limb_t mpn_divexact_by3 (mp_limb_t *RP, mp_limb_t *SP,
245: mp_size_t SIZE)
246: - Function: mp_limb_t mpn_divexact_by3c (mp_limb_t *RP, mp_limb_t *SP,
247: mp_size_t SIZE, mp_limb_t CARRY)
248: Divide {SP, SIZE} by 3, expecting it to divide exactly, and
249: writing the result to {RP, SIZE}. If 3 divides exactly, the
250: return value is zero and the result is the quotient. If not, the
251: return value is non-zero and the result won't be anything useful.
252:
253: `mpn_divexact_by3c' takes an initial carry parameter, which can be
254: the return value from a previous call, so a large calculation can
255: be done piece by piece. `mpn_divexact_by3' is simply a macro
256: calling `mpn_divexact_by3c' with a 0 carry parameter.
257:
258: These routines use a multiply-by-inverse and will be faster than
259: `mpn_divrem_1' on CPUs with fast multiplication but slow division.
260:
261: The source a, result q, size n, initial carry i, and return value
262: c satisfy c*b^n + a-i = 3*q, where b is the size of a limb (2^32
263: or 2^64). c is always 0, 1 or 2, and the initial carry must also
264: be 0, 1 or 2 (these are both borrows really). When c=0, clearly
265: q=(a-i)/3. When c!=0, the remainder (a-i) mod 3 is given by 3-c,
266: because b == 1 mod 3.
267:
268: - Function: mp_limb_t mpn_mod_1 (mp_limb_t *S1P, mp_size_t S1SIZE,
269: mp_limb_t S2LIMB)
270: Divide {S1P, S1SIZE} by S2LIMB, and return the remainder. S1SIZE
271: can be zero.
272:
273: - Function: mp_limb_t mpn_preinv_mod_1 (mp_limb_t *S1P, mp_size_t
274: S1SIZE, mp_limb_t S2LIMB, mp_limb_t S3LIMB)
275: *This interface is obsolete. It will disappear from future
276: releases. Use `mpn_mod_1' in its stead.*
277:
278: - Function: mp_limb_t mpn_bdivmod (mp_limb_t *RP, mp_limb_t *S1P,
279: mp_size_t S1SIZE, const mp_limb_t *S2P, mp_size_t S2SIZE,
280: unsigned long int D)
281: The function puts the low [D/BITS_PER_MP_LIMB] limbs of Q = {S1P,
282: S1SIZE}/{S2P, S2SIZE} mod 2^D at RP, and returns the high D mod
283: BITS_PER_MP_LIMB bits of Q.
284:
285: {S1P, S1SIZE} - Q * {S2P, S2SIZE} mod 2^(S1SIZE*BITS_PER_MP_LIMB)
286: is placed at S1P. Since the low [D/BITS_PER_MP_LIMB] limbs of
287: this difference are zero, it is possible to overwrite the low
288: limbs at S1P with this difference, provided RP <= S1P.
289:
290: This function requires that S1SIZE * BITS_PER_MP_LIMB >= D, and
291: that {S2P, S2SIZE} is odd.
292:
293: *This interface is preliminary. It might change incompatibly in
294: future revisions.*
295:
296: - Function: mp_limb_t mpn_lshift (mp_limb_t *RP, const mp_limb_t
297: *SRC_PTR, mp_size_t SRC_SIZE, unsigned long int COUNT)
298: Shift {SRC_PTR, SRC_SIZE} COUNT bits to the left, and write the
299: SRC_SIZE least significant limbs of the result to RP. COUNT might
300: be in the range 1 to n - 1, on an n-bit machine. The bits shifted
301: out to the left are returned.
302:
303: Overlapping of the destination space and the source space is
304: allowed in this function, provided RP >= SRC_PTR.
305:
306: This function is written in assembly for most targets.
307:
308: - Function: mp_limp_t mpn_rshift (mp_limb_t *RP, const mp_limb_t
309: *SRC_PTR, mp_size_t SRC_SIZE, unsigned long int COUNT)
310: Shift {SRC_PTR, SRC_SIZE} COUNT bits to the right, and write the
311: SRC_SIZE most significant limbs of the result to RP. COUNT might
312: be in the range 1 to n - 1, on an n-bit machine. The bits shifted
313: out to the right are returned.
314:
315: Overlapping of the destination space and the source space is
316: allowed in this function, provided RP <= SRC_PTR.
317:
318: This function is written in assembly for most targets.
319:
320: - Function: int mpn_cmp (const mp_limb_t *S1P, const mp_limb_t *S2P,
321: mp_size_t SIZE)
322: Compare {S1P, SIZE} and {S2P, SIZE} and return a positive value if
323: s1 > src2, 0 of they are equal, and a negative value if s1 < src2.
324:
325: - Function: mp_size_t mpn_gcd (mp_limb_t *RP, mp_limb_t *S1P,
326: mp_size_t S1SIZE, mp_limb_t *S2P, mp_size_t S2SIZE)
327: Puts at RP the greatest common divisor of {S1P, S1SIZE} and {S2P,
328: S2SIZE}; both source operands are destroyed by the operation. The
329: size in limbs of the greatest common divisor is returned.
330:
331: {S1P, S1SIZE} must have at least as many bits as {S2P, S2SIZE},
332: and {S2P, S2SIZE} must be odd.
333:
334: - Function: mp_limb_t mpn_gcd_1 (const mp_limb_t *S1P, mp_size_t
335: S1SIZE, mp_limb_t S2LIMB)
336: Return the greatest common divisor of {S1P, S1SIZE} and S2LIMB,
337: where S2LIMB (as well as S1SIZE) must be different from 0.
338:
339: - Function: mp_size_t mpn_gcdext (mp_limb_t *R1P, mp_limb_t *R2P,
340: mp_size_t *R2SIZE, mp_limb_t *S1P, mp_size_t S1SIZE,
341: mp_limb_t *S2P, mp_size_t S2SIZE)
342: Compute the greatest common divisor of {S1P, S1SIZE} and {S2P,
343: S2SIZE}. Store the gcd at R1P and return its size in limbs.
344: Write the first cofactor at R2P and store its size in *R2SIZE. If
345: the cofactor is negative, *R2SIZE is negative and R2P is the
346: absolute value of the cofactor.
347:
348: {S1P, S1SIZE} must be greater than or equal to {S2P, S2SIZE}.
349: Neither operand may equal 0. Both source operands are destroyed,
350: plus one limb past the end of each, ie. {S1P, S1SIZE+1} and {S2P,
351: S2SIZE+1}.
352:
353: - Function: mp_size_t mpn_sqrtrem (mp_limb_t *R1P, mp_limb_t *R2P,
354: const mp_limb_t *SP, mp_size_t SIZE)
355: Compute the square root of {SP, SIZE} and put the result at R1P.
356: Write the remainder at R2P, unless R2P is `NULL'.
357:
358: Return the size of the remainder, whether R2P was `NULL' or
359: non-`NULL'. Iff the operand was a perfect square, the return
360: value will be 0.
361:
362: The areas at R1P and SP have to be distinct. The areas at R2P and
363: SP have to be identical or completely separate, not partially
364: overlapping.
365:
366: The area at R1P needs to have space for ceil(SIZE/2) limbs. The
367: area at R2P needs to be SIZE limbs large.
368:
369: - Function: mp_size_t mpn_get_str (unsigned char *STR, int BASE,
370: mp_limb_t *S1P, mp_size_t S1SIZE)
371: Convert {S1P, S1SIZE} to a raw unsigned char array in base BASE.
372: The string is not in ASCII; to convert it to printable format, add
373: the ASCII codes for `0' or `A', depending on the base and range.
374: There may be leading zeros in the string.
375:
376: The area at S1P is clobbered.
377:
378: Return the number of characters in STR.
379:
380: The area at STR has to have space for the largest possible number
381: represented by a S1SIZE long limb array, plus one extra character.
382:
383: - Function: mp_size_t mpn_set_str (mp_limb_t *R1P, const char *STR,
384: size_t STRSIZE, int BASE)
385: Convert the raw unsigned char array at STR of length STRSIZE to a
386: limb array {S1P, S1SIZE}. The base of STR is BASE.
387:
388: Return the number of limbs stored in R1P.
389:
390: - Function: unsigned long int mpn_scan0 (const mp_limb_t *S1P,
391: unsigned long int BIT)
392: Scan S1P from bit position BIT for the next clear bit.
393:
394: It is required that there be a clear bit within the area at S1P at
395: or beyond bit position BIT, so that the function has something to
396: return.
397:
398: - Function: unsigned long int mpn_scan1 (const mp_limb_t *S1P,
399: unsigned long int BIT)
400: Scan S1P from bit position BIT for the next set bit.
401:
402: It is required that there be a set bit within the area at S1P at or
403: beyond bit position BIT, so that the function has something to
404: return.
405:
406: - Function: void mpn_random (mp_limb_t *R1P, mp_size_t R1SIZE)
407: - Function: void mpn_random2 (mp_limb_t *R1P, mp_size_t R1SIZE)
408: Generate a random number of length R1SIZE and store it at R1P.
409: The most significant limb is always non-zero. `mpn_random'
410: generates uniformly distributed limb data, `mpn_random2' generates
411: long strings of zeros and ones in the binary representation.
412:
413: `mpn_random2' is intended for testing the correctness of the `mpn'
414: routines.
415:
416: - Function: unsigned long int mpn_popcount (const mp_limb_t *S1P,
417: unsigned long int SIZE)
418: Count the number of set bits in {S1P, SIZE}.
419:
420: - Function: unsigned long int mpn_hamdist (const mp_limb_t *S1P, const
421: mp_limb_t *S2P, unsigned long int SIZE)
422: Compute the hamming distance between {S1P, SIZE} and {S2P, SIZE}.
423:
424: - Function: int mpn_perfect_square_p (const mp_limb_t *S1P, mp_size_t
425: SIZE)
426: Return non-zero iff {S1P, SIZE} is a perfect square.
427:
428:
429: File: gmp.info, Node: Random Number Functions, Next: BSD Compatible Functions, Prev: Low-level Functions, Up: Top
430:
431: Random Number Functions
1.1 maekawa 432: ***********************
433:
1.1.1.2 maekawa 434: There are two groups of random number functions in GNU MP; older
435: functions that call C library random number generators, rely on a global
436: state, and aren't very random; and newer functions that don't have these
437: problems. The newer functions are self-contained, they accept a random
438: state parameter that supplants global state, and generate good random
439: numbers.
440:
441: The random state parameter is of the type `gmp_randstate_t'. It
442: must be initialized by a call to one of the `gmp_randinit' functions
443: (*Note Random State Initialization::). The initial seed is set using
444: one of the `gmp_randseed' functions (*Note Random State
445: Initialization::).
446:
447: The size of the seed determines the number of different sequences of
448: random numbers that is possible to generate. The "quality" of the seed
449: is the randomness of a given seed compared to the previous seed used
450: and affects the randomness of separate number sequences.
451:
452: The algorithm for assigning seed is critical if the generated random
453: numbers are to be used for important applications, such as generating
454: cryptographic keys.
455:
456: The traditional method is to use the current system time for
457: seeding. One has to be careful when using the current time though. If
458: the application seeds the random functions very often, say several
459: times per second, and the resolution of the system clock is
460: comparatively low, like one second, the same sequence of numbers will
461: be generated until the system clock ticks. Furthermore, the current
462: system time is quite easy to guess, so a system depending on any
463: unpredictability of the random number sequence should absolutely not
464: use that as its only source for a seed value.
465:
466: On some systems there is a special device, often called
467: `/dev/random', which provides a source of somewhat random numbers more
468: usable as seed.
469:
470: The functions actually generating random functions are documented
471: under "Miscellaneous Functions" in their respective function class:
472: *Note Miscellaneous Integer Functions::, *Note Miscellaneous Float
473: Functions::.
474:
1.1 maekawa 475: * Menu:
476:
1.1.1.2 maekawa 477: * Random State Initialization:: How to initialize a random state.
478:
479:
480: File: gmp.info, Node: Random State Initialization, Prev: Random Number Functions, Up: Random Number Functions
481:
482: Random State Initialization
483: ===========================
484:
485: See *Note Random Number Functions:: for a discussion on how to
486: choose the initial seed value passed to these functions.
487:
488: - Function: void gmp_randinit (gmp_randstate_t STATE, gmp_randalg_t
489: ALG, ...)
490: Initialize random state variable STATE.
491:
492: ALG denotes what algorithm to use for random number generation.
493: Use one of
494: - GMP_RAND_ALG_LC -- Linear congruential.
495:
496: A fast generator defined by X = (aX + c) mod m.
497:
498: A third argument SIZE of type unsigned long int is required.
499: SIZE is the size of the largest good quality random number to
500: be generated, expressed in number of bits. If the random
501: generation functions are asked for a bigger random number
502: than indicated by this parameter, two or more numbers of SIZE
503: bits will be generated and concatenated, resulting in a "bad"
504: random number. This can be used to generate big random
505: numbers relatively cheap if the quality of randomness isn't
506: of great importance.
507:
508: a, c, and m are picked from a table where the modulus (m) is
509: a power of 2 and the multiplier is congruent to 5 (mod 8).
510: The choice is based on the SIZE parameter. The maximum SIZE
511: supported by this algorithm is 128. If you need bigger
512: random numbers, use your own scheme and call one of the other
513: `gmp_randinit' functions.
514:
515:
516: If ALG is 0 or GMP_RAND_ALG_DEFAULT, the default algorithm is
517: used. The default algorithm is typically a fast algorithm like
518: the linear congruential and requires a third SIZE argument (see
519: GMP_RAND_ALG_LC).
520:
521: When you're done with a STATE variable, call `gmp_randclear' to
522: deallocate any memory allocated by this function.
523:
524: `gmp_randinit' may set the following bits in GMP_ERRNO:
525: * GMP_ERROR_UNSUPPORTED_ARGUMENT -- ALG is unsupported
526:
527: * GMP_ERROR_INVALID_ARGUMENT -- SIZE is too big
528:
529: - Function: void gmp_randinit_lc_2exp (gmp_randstate_t STATE, mpz_t A,
530: unsigned long int C, unsigned long int M2EXP)
531:
532: Initialize random state variable STATE with given linear
533: congruential scheme.
534:
535: Parameters A, C, and M2EXP are the multiplier, adder, and modulus
536: for the linear congruential scheme to use, respectively. The
537: modulus is expressed as a power of 2, so that M = 2^M2EXP.
538:
539: The least significant bits of a random number generated by the
540: linear congruential algorithm where the modulus is a power of two
541: are not very random. Therefore, the lower half of a random number
542: generated by an LC scheme initialized with this function is
543: discarded. Thus, the size of a random number is M2EXP / 2
544: (rounded upwards) bits when this function has been used for
545: initializing the random state.
546:
547: When you're done with a STATE variable, call `gmp_randclear' to
548: deallocate any memory allocated by this function.
549:
550: - Function: void gmp_randseed (gmp_randstate_t STATE, mpz_t SEED)
551: - Function: void gmp_randseed_ui (gmp_randstate_t STATE, unsigned long
552: int SEED)
553: Set the initial seed value.
554:
555: Parameter SEED is the initial random seed. The function
556: `gmp_randseed_ui' takes the SEED as an unsigned long int rather
557: than as an mpz_t.
558:
559: - Function: void gmp_randclear (gmp_randstate_t STATE)
560: Free all memory occupied by STATE. Make sure to call this
561: function for all `gmp_randstate_t' variables when you are done with
562: them.
563:
564:
565: File: gmp.info, Node: BSD Compatible Functions, Next: Custom Allocation, Prev: Random Number Functions, Up: Top
566:
567: Berkeley MP Compatible Functions
568: ********************************
569:
570: These functions are intended to be fully compatible with the
571: Berkeley MP library which is available on many BSD derived U*ix
572: systems. The `--enable-mpbsd' option must be used when building GNU MP
573: to make these available (*note Installing GMP::).
574:
575: The original Berkeley MP library has a usage restriction: you cannot
576: use the same variable as both source and destination in a single
577: function call. The compatible functions in GNU MP do not share this
578: restriction--inputs and outputs may overlap.
579:
580: It is not recommended that new programs are written using these
581: functions. Apart from the incomplete set of functions, the interface
582: for initializing `MINT' objects is more error prone, and the `pow'
583: function collides with `pow' in `libm.a'.
584:
585: Include the header `mp.h' to get the definition of the necessary
586: types and functions. If you are on a BSD derived system, make sure to
587: include GNU `mp.h' if you are going to link the GNU `libmp.a' to your
588: program. This means that you probably need to give the -I<dir> option
589: to the compiler, where <dir> is the directory where you have GNU `mp.h'.
590:
591: - Function: MINT * itom (signed short int INITIAL_VALUE)
592: Allocate an integer consisting of a `MINT' object and dynamic limb
593: space. Initialize the integer to INITIAL_VALUE. Return a pointer
594: to the `MINT' object.
595:
596: - Function: MINT * xtom (char *INITIAL_VALUE)
597: Allocate an integer consisting of a `MINT' object and dynamic limb
598: space. Initialize the integer from INITIAL_VALUE, a hexadecimal,
599: '\0'-terminate C string. Return a pointer to the `MINT' object.
600:
601: - Function: void move (MINT *SRC, MINT *DEST)
602: Set DEST to SRC by copying. Both variables must be previously
603: initialized.
604:
605: - Function: void madd (MINT *SRC_1, MINT *SRC_2, MINT *DESTINATION)
606: Add SRC_1 and SRC_2 and put the sum in DESTINATION.
607:
608: - Function: void msub (MINT *SRC_1, MINT *SRC_2, MINT *DESTINATION)
609: Subtract SRC_2 from SRC_1 and put the difference in DESTINATION.
610:
611: - Function: void mult (MINT *SRC_1, MINT *SRC_2, MINT *DESTINATION)
612: Multiply SRC_1 and SRC_2 and put the product in DESTINATION.
613:
614: - Function: void mdiv (MINT *DIVIDEND, MINT *DIVISOR, MINT *QUOTIENT,
615: MINT *REMAINDER)
616: - Function: void sdiv (MINT *DIVIDEND, signed short int DIVISOR, MINT
617: *QUOTIENT, signed short int *REMAINDER)
618: Set QUOTIENT to DIVIDEND/DIVISOR, and REMAINDER to DIVIDEND mod
619: DIVISOR. The quotient is rounded towards zero; the remainder has
620: the same sign as the dividend unless it is zero.
621:
622: Some implementations of these functions work differently--or not
623: at all--for negative arguments.
624:
625: - Function: void msqrt (MINT *OPERAND, MINT *ROOT, MINT *REMAINDER)
626: Set ROOT to the truncated integer part of the square root of
627: OPERAND. Set REMAINDER to OPERAND-ROOT*ROOT, (i.e., zero if
628: OPERAND is a perfect square).
629:
630: If ROOT and REMAINDER are the same variable, the results are
631: undefined.
632:
633: - Function: void pow (MINT *BASE, MINT *EXP, MINT *MOD, MINT *DEST)
634: Set DEST to (BASE raised to EXP) modulo MOD.
635:
636: - Function: void rpow (MINT *BASE, signed short int EXP, MINT *DEST)
637: Set DEST to BASE raised to EXP.
638:
639: - Function: void gcd (MINT *OPERAND1, MINT *OPERAND2, MINT *RES)
640: Set RES to the greatest common divisor of OPERAND1 and OPERAND2.
641:
642: - Function: int mcmp (MINT *OPERAND1, MINT *OPERAND2)
643: Compare OPERAND1 and OPERAND2. Return a positive value if
644: OPERAND1 > OPERAND2, zero if OPERAND1 = OPERAND2, and a negative
645: value if OPERAND1 < OPERAND2.
646:
647: - Function: void min (MINT *DEST)
648: Input a decimal string from `stdin', and put the read integer in
649: DEST. SPC and TAB are allowed in the number string, and are
650: ignored.
651:
652: - Function: void mout (MINT *SRC)
653: Output SRC to `stdout', as a decimal string. Also output a
654: newline.
655:
656: - Function: char * mtox (MINT *OPERAND)
657: Convert OPERAND to a hexadecimal string, and return a pointer to
658: the string. The returned string is allocated using the default
659: memory allocation function, `malloc' by default.
660:
661: - Function: void mfree (MINT *OPERAND)
662: De-allocate, the space used by OPERAND. *This function should
663: only be passed a value returned by `itom' or `xtom'.*
664:
665:
666: File: gmp.info, Node: Custom Allocation, Next: Contributors, Prev: BSD Compatible Functions, Up: Top
667:
668: Custom Allocation
669: *****************
670:
671: By default, GMP uses `malloc', `realloc' and `free' for memory
672: allocation. If `malloc' or `realloc' fails, GMP prints a message to
673: the standard error output and terminates execution.
674:
675: Some applications might want to allocate memory in other ways, or
676: might not want a fatal error when there is no more memory available.
677: To accomplish this, you can specify alternative memory allocation
678: functions.
679:
680: This can be done in the Berkeley compatibility library as well as
681: the main GMP library.
682:
683: - Function: void mp_set_memory_functions (
684: void *(*ALLOC_FUNC_PTR) (size_t),
685: void *(*REALLOC_FUNC_PTR) (void *, size_t, size_t),
686: void (*FREE_FUNC_PTR) (void *, size_t))
687: Replace the current allocation functions from the arguments. If
688: an argument is `NULL', the corresponding default function is
689: retained.
690:
691: *Be sure to call this function only when there are no active GMP
692: objects allocated using the previous memory functions! Usually,
693: that means that you have to call this function before any other
694: GMP function.*
695:
696: The functions you supply should fit the following declarations:
697:
698: - Function: void * allocate_function (size_t ALLOC_SIZE)
699: This function should return a pointer to newly allocated space
700: with at least ALLOC_SIZE storage units.
701:
702: - Function: void * reallocate_function (void *PTR, size_t OLD_SIZE,
703: size_t NEW_SIZE)
704: This function should return a pointer to newly allocated space of
705: at least NEW_SIZE storage units, after copying at least the first
706: OLD_SIZE storage units from PTR. It should also de-allocate the
707: space at PTR.
708:
709: You can assume that the space at PTR was formerly returned from
710: `allocate_function' or `reallocate_function', for a request for
711: OLD_SIZE storage units.
712:
713: - Function: void deallocate_function (void *PTR, size_t SIZE)
714: De-allocate the space pointed to by PTR.
715:
716: You can assume that the space at PTR was formerly returned from
717: `allocate_function' or `reallocate_function', for a request for
718: SIZE storage units.
719:
720: (A "storage unit" is the unit in which the `sizeof' operator returns
721: the size of an object, normally an 8 bit byte.)
722:
723:
724: File: gmp.info, Node: Contributors, Next: References, Prev: Custom Allocation, Up: Top
725:
726: Contributors
727: ************
728:
729: Torbjorn Granlund wrote the original GMP library and is still
730: developing and maintaining it. Several other individuals and
731: organizations have contributed to GMP in various ways. Here is a list
732: in chronological order:
733:
734: Gunnar Sjoedin and Hans Riesel helped with mathematical problems in
735: early versions of the library.
736:
737: Richard Stallman contributed to the interface design and revised the
738: first version of this manual.
739:
740: Brian Beuning and Doug Lea helped with testing of early versions of
741: the library and made creative suggestions.
742:
743: John Amanatides of York University in Canada contributed the function
744: `mpz_probab_prime_p'.
745:
746: Paul Zimmermann of Inria sparked the development of GMP 2, with his
747: comparisons between bignum packages.
748:
749: Ken Weber (Kent State University, Universidade Federal do Rio Grande
750: do Sul) contributed `mpz_gcd', `mpz_divexact', `mpn_gcd', and
751: `mpn_bdivmod', partially supported by CNPq (Brazil) grant 301314194-2.
752:
753: Per Bothner of Cygnus Support helped to set up GMP to use Cygnus'
754: configure. He has also made valuable suggestions and tested numerous
755: intermediary releases.
756:
757: Joachim Hollman was involved in the design of the `mpf' interface,
758: and in the `mpz' design revisions for version 2.
759:
760: Bennet Yee contributed the functions `mpz_jacobi' and `mpz_legendre'.
761:
762: Andreas Schwab contributed the files `mpn/m68k/lshift.S' and
763: `mpn/m68k/rshift.S'.
764:
765: The development of floating point functions of GNU MP 2, were
766: supported in part by the ESPRIT-BRA (Basic Research Activities) 6846
767: project POSSO (POlynomial System SOlving).
768:
769: GNU MP 2 was finished and released by SWOX AB (formerly known as TMG
770: Datakonsult), Swedenborgsgatan 23, SE-118 27 STOCKHOLM, SWEDEN, in
771: cooperation with the IDA Center for Computing Sciences, USA.
772:
773: Robert Harley of Inria, France and David Seal of ARM, England,
774: suggested clever improvements for population count.
775:
776: Robert Harley also wrote highly optimized Karatsuba and 3-way Toom
777: multiplication functions for GMP 3. He also contributed the ARM
778: assembly code.
779:
780: Torsten Ekedahl of the Mathematical department of Stockholm
781: University provided significant inspiration during several phases of
782: the GMP development. His mathematical expertise helped improve several
783: algorithms.
784:
785: Paul Zimmermann wrote the Burnikel-Ziegler division code, the REDC
786: code, the REDC-based mpz_powm code, and the FFT multiply code. The
787: ECMNET project Paul is organizing has been a driving force behind many
788: of the optimization of GMP 3.
789:
790: Linus Nordberg wrote the new configure system based on autoconf and
791: implemented the new random functions.
792:
793: Kent Boortz made the Macintosh port.
794:
795: Kevin Ryde wrote a lot of very high quality x86 code, optimized for
796: most CPU variants. He also made countless other valuable contributions.
797:
798: Steve Root helped write the optimized alpha 21264 assembly code.
799:
800: GNU MP 3.1 was finished and released by Torbjorn Granlund and Kevin
801: Ryde. Torbjorn's work was partially funded by the IDA Center for
802: Computing Sciences, USA.
803:
804: (This list is chronological, not ordered after significance. If you
805: have contributed to GMP but are not listed above, please tell
806: <tege@swox.com> about the omission!)
807:
808:
809: File: gmp.info, Node: References, Next: Concept Index, Prev: Contributors, Up: Top
810:
811: References
812: **********
813:
814: * Donald E. Knuth, "The Art of Computer Programming", vol 2,
815: "Seminumerical Algorithms", 3rd edition, Addison-Wesley, 1988.
816:
817: * John D. Lipson, "Elements of Algebra and Algebraic Computing", The
818: Benjamin Cummings Publishing Company Inc, 1981.
819:
820: * Richard M. Stallman, "Using and Porting GCC", Free Software
821: Foundation, 1999, available online
822: `http://www.gnu.org/software/gcc/onlinedocs/', and in the GCC
823: package `ftp://ftp.gnu.org/pub/gnu/gcc/'.
824:
825: * Peter L. Montgomery, "Modular Multiplication Without Trial
826: Division", in Mathematics of Computation, volume 44, number 170,
827: April 1985.
828:
829: * Torbjorn Granlund and Peter L. Montgomery, "Division by Invariant
830: Integers using Multiplication", in Proceedings of the SIGPLAN
831: PLDI'94 Conference, June 1994. Available online,
832: `ftp://ftp.cwi.nl/pub/pmontgom/divcnst.psa4.gz' (and .psl.gz too).
833:
834: * Tudor Jebelean, "An algorithm for exact division", Journal of
835: Symbolic Computation, v. 15, 1993, pp. 169-180. Research report
836: version available online
837: `ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1992/92-35.ps.gz'
838:
839: * Kenneth Weber, "The accelerated integer GCD algorithm", ACM
840: Transactions on Mathematical Software, v. 21 (March), 1995, pp.
841: 111-122.
842:
843: * Christoph Burnikel and Joachim Ziegler, "Fast Recursive Division",
844: Max-Planck-Institut fuer Informatik Research Report
845: MPI-I-98-1-022,
846: `http://www.mpi-sb.mpg.de/~ziegler/TechRep.ps.gz'.
847:
848: * Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone,
849: "Handbook of Applied Cryptography",
850: `http://cacr.math.uwaterloo.ca/hac/'.
851:
852: * Henri Cohen, "A Course in Computational Algebraic Number Theory",
853: Graduate Texts in Mathematics number 138, Springer-Verlag, 1993.
854: Errata available online
855: `http://www.math.u-bordeaux.fr/~cohen'
856:
857:
858: File: gmp.info, Node: Concept Index, Next: Function Index, Prev: References, Up: Top
859:
860: Concept Index
861: *************
862:
863: * Menu:
1.1 maekawa 864:
1.1.1.2 maekawa 865: * ABI: ABI and ISA.
866: * About this manual: Introduction to GMP.
867: * alloca: Build Options.
868: * Allocation of memory: Custom Allocation.
869: * Anonymous FTP of latest version: Getting the Latest Version of GMP.
870: * Arithmetic functions <1>: Float Arithmetic.
871: * Arithmetic functions <2>: Rational Arithmetic.
872: * Arithmetic functions: Integer Arithmetic.
873: * Assignment functions <1>: Assigning Floats.
874: * Assignment functions: Assigning Integers.
875: * Basics: GMP Basics.
876: * Berkeley MP compatible functions: BSD Compatible Functions.
877: * Binomial coefficient functions: Number Theoretic Functions.
878: * Bit manipulation functions: Integer Logic and Bit Fiddling.
879: * Bit shift left: Integer Arithmetic.
880: * Bit shift right: Integer Division.
881: * Bits per limb: Useful Macros and Constants.
882: * BSD MP compatible functions: BSD Compatible Functions.
883: * Bug reporting: Reporting Bugs.
884: * Build notes for binary packaging: Notes for Package Builds.
885: * Build notes for particular systems: Notes for Particular Systems.
886: * Build options: Build Options.
887: * Build problems known: Known Build Problems.
888: * Comparison functions <1>: Integer Comparisons.
889: * Comparison functions <2>: Comparing Rationals.
890: * Comparison functions: Float Comparison.
891: * Compatibility with older versions: Compatibility with older versions.
892: * Conditions for copying GNU MP: Copying.
893: * Configuring GMP: Installing GMP.
894: * Constants: Useful Macros and Constants.
895: * Contributors: Contributors.
896: * Conventions for variables: GMP Variable Conventions.
897: * Conversion functions <1>: Converting Integers.
898: * Conversion functions: Converting Floats.
899: * Copying conditions: Copying.
900: * CPUs supported: Introduction to GMP.
901: * Custom allocation: Custom Allocation.
902: * Demonstration programs: Build Options.
903: * Division functions <1>: Integer Division.
904: * Division functions <2>: Rational Arithmetic.
905: * Division functions: Float Arithmetic.
906: * Exact division functions: Integer Division.
907: * Example programs: Build Options.
908: * Exponentiation functions <1>: Float Arithmetic.
909: * Exponentiation functions: Integer Exponentiation.
910: * Extended GCD: Number Theoretic Functions.
911: * Factorial functions: Number Theoretic Functions.
912: * Fibonacci sequence functions: Number Theoretic Functions.
913: * Float arithmetic functions: Float Arithmetic.
914: * Float assignment functions: Assigning Floats.
915: * Float comparison functions: Float Comparison.
916: * Float conversion functions: Converting Floats.
917: * Float functions: Floating-point Functions.
918: * Float init and assign functions: Simultaneous Float Init & Assign.
919: * Float initialization functions: Initializing Floats.
920: * Float input and output functions: I/O of Floats.
921: * Float miscellaneous functions: Miscellaneous Float Functions.
922: * Floating-point functions: Floating-point Functions.
923: * Floating-point number: Nomenclature and Types.
924: * FTP of latest version: Getting the Latest Version of GMP.
925: * Function classes: Function Classes.
926: * GMP version number: Useful Macros and Constants.
927: * gmp.h: GMP Basics.
928: * Greatest common divisor functions: Number Theoretic Functions.
929: * Home page: Introduction to GMP.
930: * I/O functions <1>: I/O of Rationals.
931: * I/O functions <2>: I/O of Integers.
932: * I/O functions: I/O of Floats.
933: * Initialization and assignment functions <1>: Initializing Rationals.
934: * Initialization and assignment functions <2>: Simultaneous Float Init & Assign.
935: * Initialization and assignment functions: Simultaneous Integer Init & Assign.
936: * Initialization functions <1>: Initializing Integers.
937: * Initialization functions: Initializing Floats.
938: * Input functions <1>: I/O of Floats.
939: * Input functions <2>: I/O of Rationals.
940: * Input functions: I/O of Integers.
941: * Installing GMP: Installing GMP.
942: * Integer: Nomenclature and Types.
943: * Integer arithmetic functions: Integer Arithmetic.
944: * Integer assignment functions: Assigning Integers.
945: * Integer bit manipulation functions: Integer Logic and Bit Fiddling.
946: * Integer comparison functions: Integer Comparisons.
947: * Integer conversion functions: Converting Integers.
948: * Integer division functions: Integer Division.
949: * Integer exponentiation functions: Integer Exponentiation.
950: * Integer functions: Integer Functions.
951: * Integer init and assign: Simultaneous Integer Init & Assign.
952: * Integer initialization functions: Initializing Integers.
953: * Integer input and output functions: I/O of Integers.
954: * Integer miscellaneous functions: Miscellaneous Integer Functions.
955: * Integer random number functions: Integer Random Numbers.
956: * Integer root functions: Integer Roots.
957: * Introduction: Introduction to GMP.
958: * ISA: ABI and ISA.
959: * Jabobi symbol functions: Number Theoretic Functions.
960: * Kronecker symbol functions: Number Theoretic Functions.
961: * Latest version of GMP: Getting the Latest Version of GMP.
962: * Least common multiple functions: Number Theoretic Functions.
963: * Libtool versioning: Notes for Package Builds.
964: * Limb: Nomenclature and Types.
965: * Limb size: Useful Macros and Constants.
966: * Logical functions: Integer Logic and Bit Fiddling.
967: * Low-level functions: Low-level Functions.
968: * Mailing list: Introduction to GMP.
969: * Memory allocation: Custom Allocation.
970: * Miscellaneous float functions: Miscellaneous Float Functions.
971: * Miscellaneous integer functions: Miscellaneous Integer Functions.
972: * Miscellaneous rational functions: Miscellaneous Rational Functions.
973: * Modular inverse functions: Number Theoretic Functions.
974: * mp.h: BSD Compatible Functions.
975: * Multi-threading: GMP and Reentrancy.
976: * Nomenclature: Nomenclature and Types.
977: * Number theoretic functions: Number Theoretic Functions.
978: * Numerator and denominator: Applying Integer Functions.
979: * Output functions <1>: I/O of Floats.
980: * Output functions <2>: I/O of Integers.
981: * Output functions: I/O of Rationals.
982: * Packaged builds: Notes for Package Builds.
983: * Parameter conventions: GMP Variable Conventions.
984: * Precision of floats: Floating-point Functions.
985: * Prime testing functions: Number Theoretic Functions.
986: * Random number functions <1>: Integer Random Numbers.
987: * Random number functions: Random Number Functions.
988: * Random number state: Random State Initialization.
989: * Rational arithmetic functions: Rational Arithmetic.
990: * Rational comparison functions: Comparing Rationals.
991: * Rational init and assign: Initializing Rationals.
992: * Rational input and output functions: I/O of Rationals.
993: * Rational miscellaneous functions: Miscellaneous Rational Functions.
994: * Rational number: Nomenclature and Types.
995: * Rational number functions: Rational Number Functions.
996: * Rational numerator and denominator: Applying Integer Functions.
997: * Reentrancy: GMP and Reentrancy.
998: * References: References.
999: * Reporting bugs: Reporting Bugs.
1000: * Root extraction functions <1>: Float Arithmetic.
1001: * Root extraction functions: Integer Roots.
1002: * Stack overflow segfaults: Build Options.
1003: * Stripped libraries: Known Build Problems.
1004: * Thread safety: GMP and Reentrancy.
1005: * Types: Nomenclature and Types.
1006: * Upward compatibility: Compatibility with older versions.
1007: * Useful macros and constants: Useful Macros and Constants.
1008: * User-defined precision: Floating-point Functions.
1009: * Variable conventions: GMP Variable Conventions.
1010: * Version number: Useful Macros and Constants.
1011: * Web page: Introduction to GMP.
1.1 maekawa 1012:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gmp.info-3 CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gmp