tdiv_qr.c revision 1.1.1.3
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.h" 34 1.1 mrg #include "gmp-impl.h" 35 1.1 mrg #include "longlong.h" 36 1.1 mrg 37 1.1 mrg void 38 1.1 mrg mpz_tdiv_qr (mpz_ptr quot, mpz_ptr rem, mpz_srcptr num, mpz_srcptr den) 39 1.1 mrg { 40 1.1 mrg mp_size_t ql; 41 1.1 mrg mp_size_t ns, ds, nl, dl; 42 1.1 mrg mp_ptr np, dp, qp, rp; 43 1.1 mrg TMP_DECL; 44 1.1 mrg 45 1.1 mrg ns = SIZ (num); 46 1.1 mrg ds = SIZ (den); 47 1.1 mrg nl = ABS (ns); 48 1.1 mrg dl = ABS (ds); 49 1.1 mrg ql = nl - dl + 1; 50 1.1 mrg 51 1.1.1.2 mrg if (UNLIKELY (dl == 0)) 52 1.1 mrg DIVIDE_BY_ZERO; 53 1.1 mrg 54 1.1.1.2 mrg rp = MPZ_REALLOC (rem, dl); 55 1.1 mrg 56 1.1 mrg if (ql <= 0) 57 1.1 mrg { 58 1.1 mrg if (num != rem) 59 1.1 mrg { 60 1.1 mrg np = PTR (num); 61 1.1 mrg MPN_COPY (rp, np, nl); 62 1.1 mrg SIZ (rem) = SIZ (num); 63 1.1 mrg } 64 1.1 mrg /* This needs to follow the assignment to rem, in case the 65 1.1 mrg numerator and quotient are the same. */ 66 1.1 mrg SIZ (quot) = 0; 67 1.1 mrg return; 68 1.1 mrg } 69 1.1 mrg 70 1.1.1.2 mrg qp = MPZ_REALLOC (quot, ql); 71 1.1 mrg 72 1.1 mrg TMP_MARK; 73 1.1 mrg np = PTR (num); 74 1.1 mrg dp = PTR (den); 75 1.1 mrg 76 1.1 mrg /* FIXME: We should think about how to handle the temporary allocation. 77 1.1 mrg Perhaps mpn_tdiv_qr should handle it, since it anyway often needs to 78 1.1 mrg allocate temp space. */ 79 1.1 mrg 80 1.1 mrg /* Copy denominator to temporary space if it overlaps with the quotient 81 1.1 mrg or remainder. */ 82 1.1 mrg if (dp == rp || dp == qp) 83 1.1 mrg { 84 1.1 mrg mp_ptr tp; 85 1.1 mrg tp = TMP_ALLOC_LIMBS (dl); 86 1.1 mrg MPN_COPY (tp, dp, dl); 87 1.1 mrg dp = tp; 88 1.1 mrg } 89 1.1 mrg /* Copy numerator to temporary space if it overlaps with the quotient or 90 1.1 mrg remainder. */ 91 1.1 mrg if (np == rp || np == qp) 92 1.1 mrg { 93 1.1 mrg mp_ptr tp; 94 1.1 mrg tp = TMP_ALLOC_LIMBS (nl); 95 1.1 mrg MPN_COPY (tp, np, nl); 96 1.1 mrg np = tp; 97 1.1 mrg } 98 1.1 mrg 99 1.1 mrg mpn_tdiv_qr (qp, rp, 0L, np, nl, dp, dl); 100 1.1 mrg 101 1.1 mrg ql -= qp[ql - 1] == 0; 102 1.1 mrg MPN_NORMALIZE (rp, dl); 103 1.1 mrg 104 1.1 mrg SIZ (quot) = (ns ^ ds) >= 0 ? ql : -ql; 105 1.1 mrg SIZ (rem) = ns >= 0 ? dl : -dl; 106 1.1 mrg TMP_FREE; 107 1.1 mrg } 108
Indexes created Thu Oct 01 00:25:45 UTC 2026