diff options
author | Niels M?ller <nisse@lysator.liu.se> | 2019-08-16 08:00:46 +0200 |
---|---|---|
committer | Niels M?ller <nisse@lysator.liu.se> | 2019-08-16 08:00:46 +0200 |
commit | 694d0c60b43d40bd18bcf5dda6ba1181cedd1324 (patch) | |
tree | 889630dee3f2aac7e0cc85cdb7d8f893cd216094 /tests/refmpz.c | |
parent | 58b80c88cdbd0af5ebcec9f731f93b74db8d9d1b (diff) | |
download | gmp-694d0c60b43d40bd18bcf5dda6ba1181cedd1324.tar.gz |
New function mpn_gcd_22.
* mpn/generic/gcd.c (gcd_2): Moved to gcd_22.c below.
(mpn_gcd): Adapt for calling gcd_22.
* mpn/generic/gcd_22.c (mpn_gcd_22): New file and function.
* gmp-impl.h (mp_double_limb_t): New (typedef) struct.
* configure.ac (gmp_mpn_functions): Added gcd_22.
* tests/mpn/t-gcd_22.c: New test.
* tests/mpn/Makefile.am (check_PROGRAMS): Add t-gcd_22.
* tests/refmpz.c (refmpz_gcd): New function (plain binary gcd).
Diffstat (limited to 'tests/refmpz.c')
-rw-r--r-- | tests/refmpz.c | 46 |
1 files changed, 46 insertions, 0 deletions
diff --git a/tests/refmpz.c b/tests/refmpz.c index cb280d534..167799f97 100644 --- a/tests/refmpz.c +++ b/tests/refmpz.c @@ -78,6 +78,52 @@ refmpz_hamdist (mpz_srcptr x, mpz_srcptr y) return ret; } +void +refmpz_gcd (mpz_ptr g, mpz_srcptr a_orig, mpz_srcptr b_orig) +{ + mp_bitcnt_t a_twos, b_twos, common_twos; + mpz_t a; + mpz_t b; + mpz_init (a); + mpz_init (b); + mpz_abs (a, a_orig); + mpz_abs (b, b_orig); + + if (mpz_sgn (a) == 0) + { + mpz_set (g, b); + return; + } + if (mpz_sgn (b) == 0) + { + mpz_set (g, a); + return; + } + a_twos = mpz_scan1 (a, 0); + mpz_tdiv_q_2exp (a, a, a_twos); + + b_twos = mpz_scan1 (b, 0); + mpz_tdiv_q_2exp (b, b, b_twos); + + common_twos = MIN(a_twos, b_twos); + for (;;) + { + int c; + mp_bitcnt_t twos; + c = mpz_cmp (a, b); + if (c == 0) + break; + if (c < 0) + mpz_swap (a, b); + mpz_sub (a, a, b); + twos = mpz_scan1 (a, 0); + mpz_tdiv_q_2exp (a, a, twos); + } + mpz_mul_2exp (g, a, common_twos); + + mpz_clear (a); + mpz_clear (b); +} /* (0/b), with mpz b; is 1 if b=+/-1, 0 otherwise */ #define JACOBI_0Z(b) JACOBI_0LS (PTR(b)[0], SIZ(b)) |