← Back to branch summary

~ubuntu-branches/ubuntu/vivid/gcl/vivid

« back to all changes in this revision

Viewing changes to gmp/mpn/generic/mul_basecase.c

  • Committer: Bazaar Package Importer
  • Author(s): Camm Maguire
  • Date: 2002-03-04 14:29:59 UTC
  • Revision ID: james.westby@ubuntu.com-20020304142959-dey14w08kr7lldu3
Tags: upstream-2.5.0.cvs20020219
Import upstream version 2.5.0.cvs20020219

Show diffs side-by-side

added added

removed removed

Lines of Context:
gmp/mpn/generic/mul_basecase.c
 
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
 
 
8
Copyright (C) 1991, 1992, 1993, 1994, 1996, 1997, 2000 Free Software
 
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
/* Handle simple cases with traditional multiplication.
 
32
 
 
33
   This is the most critical code of multiplication.  All multiplies rely on
 
34
   this, both small and huge.  Small ones arrive here immediately, huge ones
 
35
   arrive here as this is the base case for Karatsuba's recursive algorithm. */
 
36
 
 
37
void
 
38
#if __STDC__
 
39
mpn_mul_basecase (mp_ptr prodp,
 
40
                     mp_srcptr up, mp_size_t usize,
 
41
                     mp_srcptr vp, mp_size_t vsize)
 
42
#else
 
43
mpn_mul_basecase (prodp, up, usize, vp, vsize)
 
44
     mp_ptr prodp;
 
45
     mp_srcptr up;
 
46
     mp_size_t usize;
 
47
     mp_srcptr vp;
 
48
     mp_size_t vsize;
 
49
#endif
 
50
{
 
51
  /* We first multiply by the low order one or two limbs, as the result can
 
52
     be stored, not added, to PROD.  We also avoid a loop for zeroing this
 
53
     way.  */
 
54
#if HAVE_NATIVE_mpn_mul_2
 
55
  if (vsize >= 2)
 
56
    {
 
57
      prodp[usize + 1] = mpn_mul_2 (prodp, up, usize, vp[0], vp[1]);
 
58
      prodp += 2, vp += 2, vsize -= 2;
 
59
    }
 
60
  else
 
61
    {
 
62
      prodp[usize] = mpn_mul_1 (prodp, up, usize, vp[0]);
 
63
      return;
 
64
    }
 
65
#else
 
66
  prodp[usize] = mpn_mul_1 (prodp, up, usize, vp[0]);
 
67
  prodp += 1, vp += 1, vsize -= 1;
 
68
#endif
 
69
 
 
70
#if HAVE_NATIVE_mpn_addmul_2
 
71
  while (vsize >= 2)
 
72
    {
 
73
      prodp[usize + 1] = mpn_addmul_2 (prodp, up, usize, vp[0], vp[1]);
 
74
      prodp += 2, vp += 2, vsize -= 2;
 
75
    }
 
76
  if (vsize != 0)
 
77
    prodp[usize] = mpn_addmul_1 (prodp, up, usize, vp[0]);
 
78
#else
 
79
  /* For each iteration in the loop, multiply U with one limb from V, and
 
80
     add the result to PROD.  */
 
81
  while (vsize != 0)
 
82
    {
 
83
      prodp[usize] = mpn_addmul_1 (prodp, up, usize, vp[0]);
 
84
      prodp += 1, vp += 1, vsize -= 1;
 
85
    }
 
86
#endif
 
87
}