1/* mpz_divisible_ui_p -- mpz by ulong divisibility test. 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 3 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. If not, see http://www.gnu.org/licenses/. */ 19 20#include "gmp.h" 21#include "gmp-impl.h" 22#include "longlong.h" 23 24 25int 26mpz_divisible_ui_p (mpz_srcptr a, unsigned long d) 27{ 28 mp_size_t asize; 29 mp_ptr ap; 30 unsigned twos; 31 32 asize = SIZ(a); 33 if (UNLIKELY (d == 0)) 34 return (asize == 0); 35 36 if (asize == 0) /* 0 divisible by any d */ 37 return 1; 38 39 /* For nails don't try to be clever if d is bigger than a limb, just fake 40 up an mpz_t and go to the main mpz_divisible_p. */ 41 if (d > GMP_NUMB_MAX) 42 { 43 mp_limb_t dlimbs[2]; 44 mpz_t dz; 45 ALLOC(dz) = 2; 46 PTR(dz) = dlimbs; 47 mpz_set_ui (dz, d); 48 return mpz_divisible_p (a, dz); 49 } 50 51 ap = PTR(a); 52 asize = ABS(asize); /* ignore sign of a */ 53 54 if (ABOVE_THRESHOLD (asize, BMOD_1_TO_MOD_1_THRESHOLD)) 55 return mpn_mod_1 (ap, asize, (mp_limb_t) d) == 0; 56 57 if (! (d & 1)) 58 { 59 /* Strip low zero bits to get odd d required by modexact. If d==e*2^n 60 and a is divisible by 2^n and by e, then it's divisible by d. */ 61 62 if ((ap[0] & LOW_ZEROS_MASK (d)) != 0) 63 return 0; 64 65 count_trailing_zeros (twos, (mp_limb_t) d); 66 d >>= twos; 67 } 68 69 return mpn_modexact_1_odd (ap, asize, (mp_limb_t) d) == 0; 70} 71