Annotation of OpenXM_contrib/gmp/mpz/cong_ui.c, Revision 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>