source: trunk/third/gmp/mpz/cong_ui.c @ 18191

Revision 18191, 2.7 KB checked in by ghudson, 22 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r18190, which included commits to RCS files with non-trunk default branches.
RevLine 
[18190]1/* mpz_congruent_ui_p -- test congruence of mpz and ulong.
2
3Copyright 2000, 2001, 2002 Free Software Foundation, Inc.
4
5This file is part of the GNU MP Library.
6
7The GNU MP Library is free software; you can redistribute it and/or modify
8it under the terms of the GNU Lesser General Public License as published by
9the Free Software Foundation; either version 2.1 of the License, or (at your
10option) any later version.
11
12The GNU MP Library is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
15License for more details.
16
17You should have received a copy of the GNU Lesser General Public License
18along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
19the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20MA 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
33int
34mpz_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}
Note: See TracBrowser for help on using the repository browser.