1 /* mpz_congruent_p -- test congruence of two mpz's.
3 Copyright 2001, 2002, 2005 Free Software Foundation, Inc.
5 This file is part of the GNU MP Library.
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 3 of the License, or (at your
10 option) any later version.
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.
17 You should have received a copy of the GNU Lesser General Public License
18 along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
25 /* For big divisors this code is only very slightly better than the user
26 doing a combination of mpz_sub and mpz_tdiv_r, but it's quite convenient,
27 and perhaps in the future can be improved, in similar ways to
28 mpn_divisible_p perhaps.
30 The csize==1 / dsize==1 special case makes mpz_congruent_p as good as
31 mpz_congruent_ui_p on relevant operands, though such a combination
32 probably doesn't occur often.
36 If c<d then it'd work to just form a%d and compare a and c (either as
37 a==c or a+c==d depending on the signs), but the saving from avoiding the
38 abs(a-c) calculation would be small compared to the division.
40 Similarly if both a<d and c<d then it would work to just compare a and c
41 (a==c or a+c==d), but this isn't considered a particularly important case
42 and so isn't done for the moment.
44 Low zero limbs on d could be stripped and the corresponding limbs of a
45 and c tested and skipped, but doing so would introduce a borrow when a
46 and c differ in sign and have non-zero skipped limbs. It doesn't seem
47 worth the complications to do this, since low zero limbs on d should
51 mpz_congruent_p (mpz_srcptr a
, mpz_srcptr c
, mpz_srcptr d
)
53 mp_size_t asize
, csize
, dsize
, sign
;
56 mp_limb_t alow
, clow
, dlow
, dmask
, r
;
61 if (UNLIKELY (dsize
== 0))
62 return (mpz_cmp (a
, c
) == 0);
67 if (ABSIZ(a
) < ABSIZ(c
))
68 MPZ_SRCPTR_SWAP (a
, c
);
72 sign
= (asize
^ csize
);
78 return mpn_divisible_p (ap
, asize
, dp
, dsize
);
87 /* Check a==c mod low zero bits of dlow. This might catch a few cases of
88 a!=c quickly, and it helps the csize==1 special cases below. */
89 dmask
= LOW_ZEROS_MASK (dlow
) & GMP_NUMB_MASK
;
90 alow
= (sign
>= 0 ? alow
: -alow
);
91 if (((alow
-clow
) & dmask
) != 0)
100 NEG_MOD (clow
, clow
, dlow
);
102 if (ABOVE_THRESHOLD (asize
, BMOD_1_TO_MOD_1_THRESHOLD
))
104 r
= mpn_mod_1 (ap
, asize
, dlow
);
108 return r
== (clow
% dlow
);
113 /* Strip low zero bits to get odd d required by modexact. If
114 d==e*2^n then a==c mod d if and only if both a==c mod e and
115 a==c mod 2^n, the latter having been done above. */
117 count_trailing_zeros (twos
, dlow
);
121 r
= mpn_modexact_1c_odd (ap
, asize
, dlow
, clow
);
122 return r
== 0 || r
== dlow
;
125 /* dlow==0 is avoided since we don't want to bother handling extra low
126 zero bits if dsecond is even (would involve borrow if a,c differ in
127 sign and alow,clow!=0). */
128 if (dsize
== 2 && dlow
!= 0)
130 mp_limb_t dsecond
= dp
[1];
132 if (dsecond
<= dmask
)
135 count_trailing_zeros (twos
, dlow
);
136 dlow
= (dlow
>> twos
) | (dsecond
<< (GMP_NUMB_BITS
-twos
));
139 /* dlow will be odd here, so the test for it even under cong_1
140 is unnecessary, but the rest of that code is wanted. */
147 xp
= TMP_ALLOC_LIMBS (asize
+1);
149 /* calculate abs(a-c) */
152 /* same signs, subtract */
153 if (asize
> csize
|| mpn_cmp (ap
, cp
, asize
) >= 0)
154 ASSERT_NOCARRY (mpn_sub (xp
, ap
, asize
, cp
, csize
));
156 ASSERT_NOCARRY (mpn_sub_n (xp
, cp
, ap
, asize
));
157 MPN_NORMALIZE (xp
, asize
);
161 /* different signs, add */
163 carry
= mpn_add (xp
, ap
, asize
, cp
, csize
);
165 asize
+= (carry
!= 0);
168 result
= mpn_divisible_p (xp
, asize
, dp
, dsize
);