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

Revision 18191, 2.7 KB checked in by ghudson, 22 years ago (diff) |
---|

Rev | Line | |
---|---|---|

[18190] | 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 | } |

**Note:**See TracBrowser for help on using the repository browser.