1 /* mpn_mul -- Multiply two natural numbers. 2 3 Copyright (C) 1991, 1993, 1994, 1996 Free Software Foundation, Inc. 4 5 This file is part of the GNU MP Library. 6 7 The GNU MP Library is free software; you can redistribute it and/or modify 8 it under the terms of the GNU Lesser General Public License as published by 9 the Free Software Foundation; either version 2.1 of the License, or (at your 10 option) any later version. 11 12 The GNU MP Library is distributed in the hope that it will be useful, but 13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 15 License for more details. 16 17 You should have received a copy of the GNU Lesser General Public License 18 along with the GNU MP Library; see the file COPYING.LIB. If not, write to 19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, 20 MA 02111-1307, USA. */ 21 22 #include "gmp.h" 23 #include "gmp-impl.h" 24 25 /* Multiply the natural numbers u (pointed to by UP, with USIZE limbs) 26 and v (pointed to by VP, with VSIZE limbs), and store the result at 27 PRODP. USIZE + VSIZE limbs are always stored, but if the input 28 operands are normalized. Return the most significant limb of the 29 result. 30 31 NOTE: The space pointed to by PRODP is overwritten before finished 32 with U and V, so overlap is an error. 33 34 Argument constraints: 35 1. USIZE >= VSIZE. 36 2. PRODP != UP and PRODP != VP, i.e. the destination 37 must be distinct from the multiplier and the multiplicand. */ 38 39 /* If KARATSUBA_THRESHOLD is not already defined, define it to a 40 value which is good on most machines. */ 41 #ifndef KARATSUBA_THRESHOLD 42 #define KARATSUBA_THRESHOLD 32 43 #endif 44 45 mp_limb_t 46 #if __STDC__ 47 mpn_mul (mp_ptr prodp, 48 mp_srcptr up, mp_size_t usize, 49 mp_srcptr vp, mp_size_t vsize) 50 #else 51 mpn_mul (prodp, up, usize, vp, vsize) 52 mp_ptr prodp; 53 mp_srcptr up; 54 mp_size_t usize; 55 mp_srcptr vp; 56 mp_size_t vsize; 57 #endif 58 { 59 mp_ptr prod_endp = prodp + usize + vsize - 1; 60 mp_limb_t cy; 61 mp_ptr tspace; 62 TMP_DECL (marker); 63 64 if (vsize < KARATSUBA_THRESHOLD) 65 { 66 /* Handle simple cases with traditional multiplication. 67 68 This is the most critical code of the entire function. All 69 multiplies rely on this, both small and huge. Small ones arrive 70 here immediately. Huge ones arrive here as this is the base case 71 for Karatsuba's recursive algorithm below. */ 72 mp_size_t i; 73 mp_limb_t cy_limb; 74 mp_limb_t v_limb; 75 76 if (vsize == 0) 77 return 0; 78 79 /* Multiply by the first limb in V separately, as the result can be 80 stored (not added) to PROD. We also avoid a loop for zeroing. */ 81 v_limb = vp[0]; 82 if (v_limb <= 1) 83 { 84 if (v_limb == 1) 85 MPN_COPY (prodp, up, usize); 86 else 87 MPN_ZERO (prodp, usize); 88 cy_limb = 0; 89 } 90 else 91 cy_limb = mpn_mul_1 (prodp, up, usize, v_limb); 92 93 prodp[usize] = cy_limb; 94 prodp++; 95 96 /* For each iteration in the outer loop, multiply one limb from 97 U with one limb from V, and add it to PROD. */ 98 for (i = 1; i < vsize; i++) 99 { 100 v_limb = vp[i]; 101 if (v_limb <= 1) 102 { 103 cy_limb = 0; 104 if (v_limb == 1) 105 cy_limb = mpn_add_n (prodp, prodp, up, usize); 106 } 107 else 108 cy_limb = mpn_addmul_1 (prodp, up, usize, v_limb); 109 110 prodp[usize] = cy_limb; 111 prodp++; 112 } 113 return cy_limb; 114 } 115 116 TMP_MARK (marker); 117 118 tspace = (mp_ptr) TMP_ALLOC (2 * vsize * BYTES_PER_MP_LIMB); 119 MPN_MUL_N_RECURSE (prodp, up, vp, vsize, tspace); 120 121 prodp += vsize; 122 up += vsize; 123 usize -= vsize; 124 if (usize >= vsize) 125 { 126 mp_ptr tp = (mp_ptr) TMP_ALLOC (2 * vsize * BYTES_PER_MP_LIMB); 127 do 128 { 129 MPN_MUL_N_RECURSE (tp, up, vp, vsize, tspace); 130 cy = mpn_add_n (prodp, prodp, tp, vsize); 131 mpn_add_1 (prodp + vsize, tp + vsize, vsize, cy); 132 prodp += vsize; 133 up += vsize; 134 usize -= vsize; 135 } 136 while (usize >= vsize); 137 } 138 139 /* True: usize < vsize. */ 140 141 /* Make life simple: Recurse. */ 142 143 if (usize != 0) 144 { 145 mpn_mul (tspace, vp, vsize, up, usize); 146 cy = mpn_add_n (prodp, prodp, tspace, vsize); 147 mpn_add_1 (prodp + vsize, tspace + vsize, usize, cy); 148 } 149 150 TMP_FREE (marker); 151 return *prod_endp; 152 } 153