tdiv_qr.c revision 1.1
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 mrg Copyright 1991, 1993, 1994, 2000, 2001, 2005 Free Software Foundation, Inc. 5 1.1 mrg 6 1.1 mrg This file is part of the GNU MP Library. 7 1.1 mrg 8 1.1 mrg The GNU MP Library is free software; you can redistribute it and/or modify 9 1.1 mrg it under the terms of the GNU Lesser General Public License as published by 10 1.1 mrg the Free Software Foundation; either version 3 of the License, or (at your 11 1.1 mrg option) any later version. 12 1.1 mrg 13 1.1 mrg The GNU MP Library is distributed in the hope that it will be useful, but 14 1.1 mrg WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 15 1.1 mrg or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 16 1.1 mrg License for more details. 17 1.1 mrg 18 1.1 mrg You should have received a copy of the GNU Lesser General Public License 19 1.1 mrg along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ 20 1.1 mrg 21 1.1 mrg #include "gmp.h" 22 1.1 mrg #include "gmp-impl.h" 23 1.1 mrg #include "longlong.h" 24 1.1 mrg #ifdef BERKELEY_MP 25 1.1 mrg #include "mp.h" 26 1.1 mrg #endif 27 1.1 mrg 28 1.1 mrg void 29 1.1 mrg #ifndef BERKELEY_MP 30 1.1 mrg mpz_tdiv_qr (mpz_ptr quot, mpz_ptr rem, mpz_srcptr num, mpz_srcptr den) 31 1.1 mrg #else /* BERKELEY_MP */ 32 1.1 mrg mdiv (mpz_srcptr num, mpz_srcptr den, mpz_ptr quot, mpz_ptr rem) 33 1.1 mrg #endif /* BERKELEY_MP */ 34 1.1 mrg { 35 1.1 mrg mp_size_t ql; 36 1.1 mrg mp_size_t ns, ds, nl, dl; 37 1.1 mrg mp_ptr np, dp, qp, rp; 38 1.1 mrg TMP_DECL; 39 1.1 mrg 40 1.1 mrg ns = SIZ (num); 41 1.1 mrg ds = SIZ (den); 42 1.1 mrg nl = ABS (ns); 43 1.1 mrg dl = ABS (ds); 44 1.1 mrg ql = nl - dl + 1; 45 1.1 mrg 46 1.1 mrg if (dl == 0) 47 1.1 mrg DIVIDE_BY_ZERO; 48 1.1 mrg 49 1.1 mrg MPZ_REALLOC (rem, dl); 50 1.1 mrg 51 1.1 mrg if (ql <= 0) 52 1.1 mrg { 53 1.1 mrg if (num != rem) 54 1.1 mrg { 55 1.1 mrg mp_ptr np, rp; 56 1.1 mrg np = PTR (num); 57 1.1 mrg rp = PTR (rem); 58 1.1 mrg MPN_COPY (rp, np, nl); 59 1.1 mrg SIZ (rem) = SIZ (num); 60 1.1 mrg } 61 1.1 mrg /* This needs to follow the assignment to rem, in case the 62 1.1 mrg numerator and quotient are the same. */ 63 1.1 mrg SIZ (quot) = 0; 64 1.1 mrg return; 65 1.1 mrg } 66 1.1 mrg 67 1.1 mrg MPZ_REALLOC (quot, ql); 68 1.1 mrg 69 1.1 mrg TMP_MARK; 70 1.1 mrg qp = PTR (quot); 71 1.1 mrg rp = PTR (rem); 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