Annotation of OpenXM_contrib/gmp/mpz/cong_ui.c, Revision 1.1.1.1
1.1 ohara 1: /* mpz_congruent_ui_p -- test congruence of mpz and ulong.
2:
3: Copyright 2000, 2001, 2002 Free Software Foundation, Inc.
4:
5: This file is part of the GNU MP Library.
6:
7: The GNU MP Library is free software; you can redistribute it and/or modify
8: it under the terms of the GNU Lesser General Public License as published by
9: the Free Software Foundation; either version 2.1 of the License, or (at your
10: option) any later version.
11:
12: The GNU MP Library is distributed in the hope that it will be useful, but
13: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14: or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
15: License for more details.
16:
17: You should have received a copy of the GNU Lesser General Public License
18: along with the GNU MP Library; see the file COPYING.LIB. If not, write to
19: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20: MA 02111-1307, USA. */
21:
22: #include "gmp.h"
23: #include "gmp-impl.h"
24: #include "longlong.h"
25:
26:
27: /* There's some explicit checks for c<d since it seems reasonably likely an
28: application might use that in a test.
29:
30: Hopefully the compiler can generate something good for r==(c%d), though
31: if modexact is being used exclusively then that's not reached. */
32:
33: int
34: mpz_congruent_ui_p (mpz_srcptr a, unsigned long cu, unsigned long du)
35: {
36: mp_srcptr ap;
37: mp_size_t asize;
38: mp_limb_t c, d, r;
39:
40: if (du == 0)
41: DIVIDE_BY_ZERO;
42:
43: asize = SIZ(a);
44: if (asize == 0)
45: {
46: if (cu < du)
47: return cu == 0;
48: else
49: return (cu % du) == 0;
50: }
51:
52: /* For nails don't try to be clever if c or d is bigger than a limb, just
53: fake up some mpz_t's and go to the main mpz_congruent_p. */
54: if (du > GMP_NUMB_MAX || cu > GMP_NUMB_MAX)
55: {
56: mp_limb_t climbs[2], dlimbs[2];
57: mpz_t cz, dz;
58:
59: ALLOC(cz) = 2;
60: PTR(cz) = climbs;
61: ALLOC(dz) = 2;
62: PTR(dz) = dlimbs;
63:
64: mpz_set_ui (cz, cu);
65: mpz_set_ui (dz, du);
66: return mpz_congruent_p (a, cz, dz);
67: }
68:
69: /* NEG_MOD works on limbs, so convert ulong to limb */
70: c = cu;
71: d = du;
72:
73: if (asize < 0)
74: {
75: asize = -asize;
76: NEG_MOD (c, c, d);
77: }
78:
79: ap = PTR (a);
80:
81: if (BELOW_THRESHOLD (asize, MODEXACT_1_ODD_THRESHOLD))
82: {
83: r = mpn_mod_1 (ap, asize, d);
84: if (c < d)
85: return r == c;
86: else
87: return r == (c % d);
88: }
89:
90: if ((d & 1) == 0)
91: {
92: /* Strip low zero bits to get odd d required by modexact. If
93: d==e*2^n then a==c mod d if and only if both a==c mod 2^n
94: and a==c mod e. */
95:
96: unsigned twos;
97:
98: if ((ap[0]-c) & LOW_ZEROS_MASK (d))
99: return 0;
100:
101: count_trailing_zeros (twos, d);
102: d >>= twos;
103: }
104:
105: r = mpn_modexact_1c_odd (ap, asize, d, c);
106: return r == 0 || r == d;
107: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>