Return to divrem.c CVS log

Up to [local] / OpenXM_contrib / gmp / mpn / generic

Annotation of OpenXM_contrib/gmp/mpn/generic/divrem.c, Revision 1.1.1.2

1.1       maekawa     1: /* mpn_divrem -- Divide natural numbers, producing both remainder and
1.1.1.2 ! maekawa     2:    quotient.  This is now just a middle layer for calling the new
        !             3:    internal mpn_tdiv_qr.
1.1       maekawa     4:
1.1.1.2 ! maekawa     5: Copyright (C) 1993, 1994, 1995, 1996, 1997, 1999, 2000 Free Software
        !             6: Foundation, Inc.
1.1       maekawa     7:
                      8: This file is part of the GNU MP Library.
                      9:
                     10: The GNU MP Library is free software; you can redistribute it and/or modify
1.1.1.2 ! maekawa    11: it under the terms of the GNU Lesser General Public License as published by
        !            12: the Free Software Foundation; either version 2.1 of the License, or (at your
1.1       maekawa    13: option) any later version.
                     14:
                     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
1.1.1.2 ! maekawa    17: or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
1.1       maekawa    18: License for more details.
                     19:
1.1.1.2 ! maekawa    20: You should have received a copy of the GNU Lesser General Public License
1.1       maekawa    21: along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
                     22: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
                     23: MA 02111-1307, USA. */
                     24:
                     25: #include "gmp.h"
                     26: #include "gmp-impl.h"
                     27: #include "longlong.h"
                     28:
                     29: mp_limb_t
                     30: #if __STDC__
1.1.1.2 ! maekawa    31: mpn_divrem (mp_ptr qp, mp_size_t qxn,
        !            32:            mp_ptr np, mp_size_t nn,
        !            33:            mp_srcptr dp, mp_size_t dn)
1.1       maekawa    34: #else
1.1.1.2 ! maekawa    35: mpn_divrem (qp, qxn, np, nn, dp, dn)
1.1       maekawa    36:      mp_ptr qp;
1.1.1.2 ! maekawa    37:      mp_size_t qxn;
1.1       maekawa    38:      mp_ptr np;
1.1.1.2 ! maekawa    39:      mp_size_t nn;
1.1       maekawa    40:      mp_srcptr dp;
1.1.1.2 ! maekawa    41:      mp_size_t dn;
1.1       maekawa    42: #endif
                     43: {
1.1.1.2 ! maekawa    44:   if (dn == 1)
        !            45:     {
        !            46:       mp_limb_t ret;
        !            47:       mp_ptr q2p;
        !            48:       mp_size_t qn;
        !            49:       TMP_DECL (marker);
        !            50:
        !            51:       TMP_MARK (marker);
        !            52:       q2p = (mp_ptr) TMP_ALLOC ((nn + qxn) * BYTES_PER_MP_LIMB);
        !            53:
        !            54:       np[0] = mpn_divrem_1 (q2p, qxn, np, nn, dp[0]);
        !            55:       qn = nn + qxn - 1;
        !            56:       MPN_COPY (qp, q2p, qn);
        !            57:       ret = q2p[qn];
1.1       maekawa    58:
1.1.1.2 ! maekawa    59:       TMP_FREE (marker);
        !            60:       return ret;
        !            61:     }
        !            62:   else if (dn == 2)
1.1       maekawa    63:     {
1.1.1.2 ! maekawa    64:       return mpn_divrem_2 (qp, qxn, np, nn, dp);
        !            65:     }
        !            66:   else
        !            67:     {
        !            68:       mp_ptr rp, q2p;
        !            69:       mp_limb_t qhl;
        !            70:       mp_size_t qn;
        !            71:       TMP_DECL (marker);
        !            72:
        !            73:       TMP_MARK (marker);
        !            74:       if (qxn != 0)
        !            75:        {
        !            76:          mp_ptr n2p;
        !            77:          n2p = (mp_ptr) TMP_ALLOC ((nn + qxn) * BYTES_PER_MP_LIMB);
        !            78:          MPN_ZERO (n2p, qxn);
        !            79:          MPN_COPY (n2p + qxn, np, nn);
        !            80:          q2p = (mp_ptr) TMP_ALLOC ((nn - dn + qxn + 1) * BYTES_PER_MP_LIMB);
        !            81:          rp = (mp_ptr) TMP_ALLOC (dn * BYTES_PER_MP_LIMB);
        !            82:          mpn_tdiv_qr (q2p, rp, 0L, n2p, nn + qxn, dp, dn);
        !            83:          MPN_COPY (np, rp, dn);
        !            84:          qn = nn - dn + qxn;
        !            85:          MPN_COPY (qp, q2p, qn);
        !            86:          qhl = q2p[qn];
        !            87:        }
        !            88:       else
        !            89:        {
        !            90:          q2p = (mp_ptr) TMP_ALLOC ((nn - dn + 1) * BYTES_PER_MP_LIMB);
        !            91:          rp = (mp_ptr) TMP_ALLOC (dn * BYTES_PER_MP_LIMB);
        !            92:          mpn_tdiv_qr (q2p, rp, 0L, np, nn, dp, dn);
        !            93:          MPN_COPY (np, rp, dn);        /* overwrite np area with remainder */
        !            94:          qn = nn - dn;
        !            95:          MPN_COPY (qp, q2p, qn);
        !            96:          qhl = q2p[qn];
        !            97:        }
        !            98:       TMP_FREE (marker);
        !            99:       return qhl;
1.1       maekawa   100:     }
                    101: }