1 1.1 mrg /* mpz_tdiv_qr(quot,rem,dividend,divisor) -- Set QUOT to DIVIDEND/DIVISOR, 2 1.1 mrg and REM to DIVIDEND mod DIVISOR. 3 1.1 mrg 4 1.1.1.2 mrg Copyright 1991, 1993, 1994, 2000, 2001, 2005, 2011, 2012 Free Software 5 1.1.1.2 mrg Foundation, Inc. 6 1.1 mrg 7 1.1 mrg This file is part of the GNU MP Library. 8 1.1 mrg 9 1.1 mrg The GNU MP Library is free software; you can redistribute it and/or modify 10 1.1.1.3 mrg it under the terms of either: 11 1.1.1.3 mrg 12 1.1.1.3 mrg * the GNU Lesser General Public License as published by the Free 13 1.1.1.3 mrg Software Foundation; either version 3 of the License, or (at your 14 1.1.1.3 mrg option) any later version. 15 1.1.1.3 mrg 16 1.1.1.3 mrg or 17 1.1.1.3 mrg 18 1.1.1.3 mrg * the GNU General Public License as published by the Free Software 19 1.1.1.3 mrg Foundation; either version 2 of the License, or (at your option) any 20 1.1.1.3 mrg later version. 21 1.1.1.3 mrg 22 1.1.1.3 mrg or both in parallel, as here. 23 1.1 mrg 24 1.1 mrg The GNU MP Library is distributed in the hope that it will be useful, but 25 1.1 mrg WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 26 1.1.1.3 mrg or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 27 1.1.1.3 mrg for more details. 28 1.1 mrg 29 1.1.1.3 mrg You should have received copies of the GNU General Public License and the 30 1.1.1.3 mrg GNU Lesser General Public License along with the GNU MP Library. If not, 31 1.1.1.3 mrg see https://www.gnu.org/licenses/. */ 32 1.1 mrg 33 1.1 mrg #include "gmp-impl.h" 34 1.1 mrg #include "longlong.h" 35 1.1 mrg 36 1.1 mrg void 37 1.1 mrg mpz_tdiv_qr (mpz_ptr quot, mpz_ptr rem, mpz_srcptr num, mpz_srcptr den) 38 1.1 mrg { 39 1.1 mrg mp_size_t ql; 40 1.1 mrg mp_size_t ns, ds, nl, dl; 41 1.1 mrg mp_ptr np, dp, qp, rp; 42 1.1 mrg TMP_DECL; 43 1.1 mrg 44 1.1 mrg ns = SIZ (num); 45 1.1 mrg ds = SIZ (den); 46 1.1 mrg nl = ABS (ns); 47 1.1 mrg dl = ABS (ds); 48 1.1 mrg ql = nl - dl + 1; 49 1.1 mrg 50 1.1.1.2 mrg if (UNLIKELY (dl == 0)) 51 1.1 mrg DIVIDE_BY_ZERO; 52 1.1 mrg 53 1.1.1.2 mrg rp = MPZ_REALLOC (rem, dl); 54 1.1 mrg 55 1.1 mrg if (ql <= 0) 56 1.1 mrg { 57 1.1 mrg if (num != rem) 58 1.1 mrg { 59 1.1 mrg np = PTR (num); 60 1.1 mrg MPN_COPY (rp, np, nl); 61 1.1 mrg SIZ (rem) = SIZ (num); 62 1.1 mrg } 63 1.1 mrg /* This needs to follow the assignment to rem, in case the 64 1.1 mrg numerator and quotient are the same. */ 65 1.1 mrg SIZ (quot) = 0; 66 1.1 mrg return; 67 1.1 mrg } 68 1.1 mrg 69 1.1.1.2 mrg qp = MPZ_REALLOC (quot, ql); 70 1.1 mrg 71 1.1 mrg TMP_MARK; 72 1.1 mrg np = PTR (num); 73 1.1 mrg dp = PTR (den); 74 1.1 mrg 75 1.1 mrg /* FIXME: We should think about how to handle the temporary allocation. 76 1.1 mrg Perhaps mpn_tdiv_qr should handle it, since it anyway often needs to 77 1.1 mrg allocate temp space. */ 78 1.1 mrg 79 1.1 mrg /* Copy denominator to temporary space if it overlaps with the quotient 80 1.1 mrg or remainder. */ 81 1.1 mrg if (dp == rp || dp == qp) 82 1.1 mrg { 83 1.1 mrg mp_ptr tp; 84 1.1 mrg tp = TMP_ALLOC_LIMBS (dl); 85 1.1 mrg MPN_COPY (tp, dp, dl); 86 1.1 mrg dp = tp; 87 1.1 mrg } 88 1.1 mrg /* Copy numerator to temporary space if it overlaps with the quotient or 89 1.1 mrg remainder. */ 90 1.1 mrg if (np == rp || np == qp) 91 1.1 mrg { 92 1.1 mrg mp_ptr tp; 93 1.1 mrg tp = TMP_ALLOC_LIMBS (nl); 94 1.1 mrg MPN_COPY (tp, np, nl); 95 1.1 mrg np = tp; 96 1.1 mrg } 97 1.1 mrg 98 1.1 mrg mpn_tdiv_qr (qp, rp, 0L, np, nl, dp, dl); 99 1.1 mrg 100 1.1 mrg ql -= qp[ql - 1] == 0; 101 1.1 mrg MPN_NORMALIZE (rp, dl); 102 1.1 mrg 103 1.1 mrg SIZ (quot) = (ns ^ ds) >= 0 ? ql : -ql; 104 1.1 mrg SIZ (rem) = ns >= 0 ? dl : -dl; 105 1.1 mrg TMP_FREE; 106 1.1 mrg } 107
Indexes created Thu Oct 01 00:25:45 UTC 2026