1 /* mpz_divexact_gcd -- exact division optimized for GCDs.
3 THE FUNCTIONS IN THIS FILE ARE FOR INTERNAL USE AND ARE ALMOST CERTAIN TO
4 BE SUBJECT TO INCOMPATIBLE CHANGES IN FUTURE GNU MP RELEASES.
6 Copyright 2000, 2005 Free Software Foundation, Inc.
8 This file is part of the GNU MP Library.
10 The GNU MP Library is free software; you can redistribute it and/or modify
11 it under the terms of the GNU Lesser General Public License as published by
12 the Free Software Foundation; either version 3 of the License, or (at your
13 option) any later version.
15 The GNU MP Library is distributed in the hope that it will be useful, but
16 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18 License for more details.
20 You should have received a copy of the GNU Lesser General Public License
21 along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
28 /* Set q to a/d, expecting d to be from a GCD and therefore usually small.
30 The distribution of GCDs of random numbers can be found in Knuth volume 2
31 section 4.5.2 theorem D.
39 Only the low limb is examined for optimizations, since GCDs bigger than
40 2^32 (or 2^64) will occur very infrequently.
42 Future: This could change to an mpn_divexact_gcd, possibly partly
43 inlined, if/when the relevant mpq functions change to an mpn based
48 mpz_divexact_by3 (mpz_ptr q, mpz_srcptr a)
50 mp_size_t size = SIZ(a);
58 mp_size_t abs_size = ABS(size);
61 MPZ_REALLOC (q, abs_size);
64 mpn_divexact_by3 (qp, PTR(a), abs_size);
66 abs_size -= (qp[abs_size-1] == 0);
67 SIZ(q) = (size>0 ? abs_size : -abs_size);
72 mpz_divexact_gcd (mpz_ptr q, mpz_srcptr a, mpz_srcptr d)
74 ASSERT (mpz_sgn (d) > 0);
78 mp_limb_t dl = PTR(d)[0];
89 mpz_divexact_by3 (q, a);
93 count_trailing_zeros (twos, dl);
98 mpz_tdiv_q_2exp (q, a, twos);
103 mpz_tdiv_q_2exp (q, a, twos);
104 mpz_divexact_by3 (q, q);
109 mpz_divexact (q, a, d);