diff options
author | Kevin Ryde <user42@zip.com.au> | 2001-03-02 21:36:32 +0100 |
---|---|---|
committer | Kevin Ryde <user42@zip.com.au> | 2001-03-02 21:36:32 +0100 |
commit | ef6472a304844bc0e335feb12f5e91619a7387b4 (patch) | |
tree | 90c7c3d2c2fe9d0d84e346baef0b9eacd8206092 | |
parent | c372cc8e6186e2fb52dbb3ec16ff7eae4a6c2f95 (diff) | |
download | gmp-ef6472a304844bc0e335feb12f5e91619a7387b4.tar.gz |
* mpz/divis.c, mpz/divis_ui.c, mpz/divis_2exp.c: New files.
-rw-r--r-- | mpz/divis.c | 38 | ||||
-rw-r--r-- | mpz/divis_2exp.c | 53 | ||||
-rw-r--r-- | mpz/divis_ui.c | 66 |
3 files changed, 157 insertions, 0 deletions
diff --git a/mpz/divis.c b/mpz/divis.c new file mode 100644 index 000000000..b071fce00 --- /dev/null +++ b/mpz/divis.c @@ -0,0 +1,38 @@ +/* mpz_divisible_p -- mpz by mpz divisibility test */ + +/* +Copyright 2001 Free Software Foundation, Inc. + +This file is part of the GNU MP Library. + +The GNU MP Library is free software; you can redistribute it and/or modify +it under the terms of the GNU Lesser General Public License as published by +the Free Software Foundation; either version 2.1 of the License, or (at your +option) any later version. + +The GNU MP Library is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY +or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public +License for more details. + +You should have received a copy of the GNU Lesser General Public License +along with the GNU MP Library; see the file COPYING.LIB. If not, write to +the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, +MA 02111-1307, USA. +*/ + +#include "gmp.h" +#include "gmp-impl.h" + +int +mpz_divisible_p (mpz_srcptr a, mpz_srcptr d) +{ + int dsize; + + dsize = SIZ(d); + if (dsize == 0) + DIVIDE_BY_ZERO; + + return mpn_divisible_p (PTR(a), (mp_size_t) ABSIZ(a), + PTR(d), (mp_size_t) ABS(dsize)); +} diff --git a/mpz/divis_2exp.c b/mpz/divis_2exp.c new file mode 100644 index 000000000..9392fde33 --- /dev/null +++ b/mpz/divis_2exp.c @@ -0,0 +1,53 @@ +/* mpz_divisible_2exp_p -- mpz by 2^n divisibility test */ + +/* +Copyright 2001 Free Software Foundation, Inc. + +This file is part of the GNU MP Library. + +The GNU MP Library is free software; you can redistribute it and/or modify +it under the terms of the GNU Lesser General Public License as published by +the Free Software Foundation; either version 2.1 of the License, or (at your +option) any later version. + +The GNU MP Library is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY +or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public +License for more details. + +You should have received a copy of the GNU Lesser General Public License +along with the GNU MP Library; see the file COPYING.LIB. If not, write to +the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, +MA 02111-1307, USA. +*/ + +#include "gmp.h" +#include "gmp-impl.h" + + +int +mpz_divisible_2exp_p (mpz_srcptr a, unsigned long d) +{ + unsigned long i, dlimbs, dbits; + mp_ptr ap; + mp_limb_t dmask; + int asize; + + asize = ABSIZ(a); + dlimbs = d / BITS_PER_MP_LIMB; + + /* if d covers the whole of a, then only a==0 is divisible */ + if (asize <= dlimbs) + return asize == 0; + + /* whole limbs must be zero */ + ap = PTR(a); + for (i = 0; i < dlimbs; i++) + if (ap[i] != 0) + return 0; + + /* left over bits must be zero */ + dbits = d % BITS_PER_MP_LIMB; + dmask = (CNST_LIMB(1) << dbits) - 1; + return (ap[dlimbs] & dmask) == 0; +} diff --git a/mpz/divis_ui.c b/mpz/divis_ui.c new file mode 100644 index 000000000..9390669cc --- /dev/null +++ b/mpz/divis_ui.c @@ -0,0 +1,66 @@ +/* mpz_divisible_ui_p -- mpz by ulong divisibility test */ + +/* +Copyright 2000, 2001 Free Software Foundation, Inc. + +This file is part of the GNU MP Library. + +The GNU MP Library is free software; you can redistribute it and/or modify +it under the terms of the GNU Lesser General Public License as published by +the Free Software Foundation; either version 2.1 of the License, or (at your +option) any later version. + +The GNU MP Library is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY +or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public +License for more details. + +You should have received a copy of the GNU Lesser General Public License +along with the GNU MP Library; see the file COPYING.LIB. If not, write to +the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, +MA 02111-1307, USA. +*/ + +#include "gmp.h" +#include "gmp-impl.h" +#include "longlong.h" + + +/* A bit mask of all the least significant zero bits of n. */ +#define LOW_ZEROS_MASK(n) (((n) & -(n)) - 1) + + +int +mpz_divisible_ui_p (mpz_srcptr a, unsigned long d) +{ + mp_size_t asize; + mp_ptr ap; + unsigned twos; + + if (d == 0) + DIVIDE_BY_ZERO; + + asize = SIZ(a); + if (asize == 0) /* 0 divisible by any d */ + return 1; + + ap = PTR(a); + asize = ABS(asize); /* ignore sign of a */ + + if (BELOW_THRESHOLD (asize, MODEXACT_1_ODD_THRESHOLD)) + return mpn_mod_1 (ap, asize, (mp_limb_t) d) == 0; + + if (! (d & 1)) + { + /* Strip low zero bits to get odd d required by modexact. If d==e*2^n + and a is divisible by 2^n and by e, then it's divisible by d. */ + + if ((ap[0] & LOW_ZEROS_MASK (d)) != 0) + return 0; + + count_trailing_zeros (twos, (mp_limb_t) d); + d >>= twos; + } + + return mpn_modexact_1_odd (ap, asize, (mp_limb_t) d) == 0; +} |