Return to mul_basecase.c CVS log

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

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

1.1       maekawa     1: /* mpn_mul_basecase -- Internal routine to multiply two natural numbers
                      2:    of length m and n.
                      3:
                      4:    THIS IS AN INTERNAL FUNCTION WITH A MUTABLE INTERFACE.  IT IS ONLY
                      5:    SAFE TO REACH THIS FUNCTION THROUGH DOCUMENTED INTERFACES.
                      6:
                      7:
1.1.1.2 ! ohara       8: Copyright 1991, 1992, 1993, 1994, 1996, 1997, 2000, 2001, 2002 Free Software
1.1       maekawa     9: Foundation, Inc.
                     10:
                     11: This file is part of the GNU MP Library.
                     12:
                     13: The GNU MP Library is free software; you can redistribute it and/or modify
                     14: it under the terms of the GNU Lesser General Public License as published by
                     15: the Free Software Foundation; either version 2.1 of the License, or (at your
                     16: option) any later version.
                     17:
                     18: The GNU MP Library is distributed in the hope that it will be useful, but
                     19: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
                     20: or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
                     21: License for more details.
                     22:
                     23: You should have received a copy of the GNU Lesser General Public License
                     24: along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
                     25: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
                     26: MA 02111-1307, USA. */
                     27:
                     28: #include "gmp.h"
                     29: #include "gmp-impl.h"
                     30:
                     31:
1.1.1.2 ! ohara      32: /* Multiply {up,usize} by {vp,vsize} and write the result to
        !            33:    {prodp,usize+vsize}.  Must have usize>=vsize.
        !            34:
        !            35:    Note that prodp gets usize+vsize limbs stored, even if the actual result
        !            36:    only needs usize+vsize-1.
        !            37:
        !            38:    There's no good reason to call here with vsize>=MUL_KARATSUBA_THRESHOLD.
        !            39:    Currently this is allowed, but it might not be in the future.
        !            40:
        !            41:    This is the most critical code for multiplication.  All multiplies rely
        !            42:    on this, both small and huge.  Small ones arrive here immediately, huge
        !            43:    ones arrive here as this is the base case for Karatsuba's recursive
        !            44:    algorithm.  */
1.1       maekawa    45:
                     46: void
1.1.1.2 ! ohara      47: mpn_mul_basecase (mp_ptr rp,
        !            48:                  mp_srcptr up, mp_size_t un,
        !            49:                  mp_srcptr vp, mp_size_t vn)
1.1       maekawa    50: {
1.1.1.2 ! ohara      51:   ASSERT (un >= vn);
        !            52:   ASSERT (vn >= 1);
        !            53:   ASSERT (! MPN_OVERLAP_P (rp, un+vn, up, un));
        !            54:   ASSERT (! MPN_OVERLAP_P (rp, un+vn, vp, vn));
        !            55:
        !            56:   /* We first multiply by the low order limb (or depending on optional function
        !            57:      availability, limbs).  This result can be stored, not added, to rp.  We
        !            58:      also avoid a loop for zeroing this way.  */
        !            59:
1.1       maekawa    60: #if HAVE_NATIVE_mpn_mul_2
1.1.1.2 ! ohara      61:   if (vn >= 2)
1.1       maekawa    62:     {
1.1.1.2 ! ohara      63:       rp[un + 1] = mpn_mul_2 (rp, up, un, vp);
        !            64:       rp += 2, vp += 2, vn -= 2;
1.1       maekawa    65:     }
                     66:   else
                     67:     {
1.1.1.2 ! ohara      68:       rp[un] = mpn_mul_1 (rp, up, un, vp[0]);
1.1       maekawa    69:       return;
                     70:     }
                     71: #else
1.1.1.2 ! ohara      72:   rp[un] = mpn_mul_1 (rp, up, un, vp[0]);
        !            73:   rp += 1, vp += 1, vn -= 1;
1.1       maekawa    74: #endif
                     75:
1.1.1.2 ! ohara      76:   /* Now accumulate the product of up[] and the next low-order limb (or
        !            77:      depending on optional function availability, limbs) from vp[0].  */
        !            78:
        !            79: #define MAX_LEFT MP_SIZE_T_MAX
        !            80:
        !            81: #if HAVE_NATIVE_mpn_addmul_4
        !            82:   while (vn >= 4)
1.1       maekawa    83:     {
1.1.1.2 ! ohara      84:       rp[un + 4 - 1] = mpn_addmul_4 (rp, up, un, vp);
        !            85:       rp += 4, vp += 4, vn -= 4;
1.1       maekawa    86:     }
1.1.1.2 ! ohara      87: #undef MAX_LEFT
        !            88: #define MAX_LEFT 3
        !            89: #endif
        !            90:
        !            91: #if HAVE_NATIVE_mpn_addmul_3
        !            92:   while (vn >= 3)
        !            93:     {
        !            94:       rp[un + 3 - 1] = mpn_addmul_3 (rp, up, un, vp);
        !            95:       rp += 3, vp += 3, vn -= 3;
        !            96:       if (MAX_LEFT - 3 <= 3)
        !            97:        break;
        !            98:     }
        !            99: #undef MAX_LEFT
        !           100: #define MAX_LEFT 2
        !           101: #endif
        !           102:
        !           103: #if HAVE_NATIVE_mpn_addmul_2
        !           104:   while (vn >= 2)
1.1       maekawa   105:     {
1.1.1.2 ! ohara     106:       rp[un + 2 - 1] = mpn_addmul_2 (rp, up, un, vp);
        !           107:       rp += 2, vp += 2, vn -= 2;
        !           108:       if (MAX_LEFT - 2 <= 2)
        !           109:        break;
1.1       maekawa   110:     }
1.1.1.2 ! ohara     111: #undef MAX_LEFT
        !           112: #define MAX_LEFT 1
1.1       maekawa   113: #endif
1.1.1.2 ! ohara     114:
        !           115:   while (vn >= 1)
        !           116:     {
        !           117:       rp[un] = mpn_addmul_1 (rp, up, un, vp[0]);
        !           118:       rp += 1, vp += 1, vn -= 1;
        !           119:       if (MAX_LEFT - 1 <= 1)
        !           120:        break;
        !           121:     }
1.1       maekawa   122: }