1 2 /* 3 * M_APM - mapm_mul.c 4 * 5 * Copyright (C) 1999 - 2007 Michael C. Ring 6 * 7 * Permission to use, copy, and distribute this software and its 8 * documentation for any purpose with or without fee is hereby granted, 9 * provided that the above copyright notice appear in all copies and 10 * that both that copyright notice and this permission notice appear 11 * in supporting documentation. 12 * 13 * Permission to modify the software is granted. Permission to distribute 14 * the modified code is granted. Modifications are to be distributed by 15 * using the file 'license.txt' as a template to modify the file header. 16 * 'license.txt' is available in the official MAPM distribution. 17 * 18 * This software is provided "as is" without express or implied warranty. 19 */ 20 21 /* 22 * $Id: mapm_mul.c,v 1.16 2007/12/03 01:45:27 mike Exp $ 23 * 24 * This file contains basic multiplication function. 25 * 26 * $Log: mapm_mul.c,v $ 27 * Revision 1.16 2007/12/03 01:45:27 mike 28 * Update license 29 * 30 * Revision 1.15 2004/02/21 04:30:35 mike 31 * minor optimization by using pointers instead of array indexes. 32 * 33 * Revision 1.14 2003/07/21 20:18:59 mike 34 * Modify error messages to be in a consistent format. 35 * 36 * Revision 1.13 2003/03/31 22:14:05 mike 37 * call generic error handling function 38 * 39 * Revision 1.12 2002/11/03 22:25:36 mike 40 * Updated function parameters to use the modern style 41 * 42 * Revision 1.11 2001/07/24 18:24:26 mike 43 * access div/rem lookup table directly 44 * for speed 45 * 46 * Revision 1.10 2001/02/11 22:31:39 mike 47 * modify parameters to REALLOC 48 * 49 * Revision 1.9 2000/07/09 00:20:03 mike 50 * change break even point again .... 51 * 52 * Revision 1.8 2000/07/08 18:51:43 mike 53 * change break even point between this O(n^2) 54 * multiply and the FFT multiply 55 * 56 * Revision 1.7 2000/04/14 16:27:45 mike 57 * change the break even point between the 2 multiply 58 * functions since we made the fast one even faster. 59 * 60 * Revision 1.6 2000/02/03 22:46:40 mike 61 * use MAPM_* generic memory function 62 * 63 * Revision 1.5 1999/09/19 21:10:14 mike 64 * change the break even point between the 2 multiply choices 65 * 66 * Revision 1.4 1999/08/09 23:57:17 mike 67 * added more comments 68 * 69 * Revision 1.3 1999/08/09 02:38:17 mike 70 * tweak break even point and add comments 71 * 72 * Revision 1.2 1999/08/08 18:35:20 mike 73 * add call to fast algorithm if input numbers are large 74 * 75 * Revision 1.1 1999/05/10 20:56:31 mike 76 * Initial revision 77 */ 78 79 #include "m_apm_lc.h" 80 81 extern void M_fast_multiply(M_APM, M_APM, M_APM); 82 83 /****************************************************************************/ 84 void m_apm_multiply(M_APM r, M_APM a, M_APM b) 85 { 86 int ai, itmp, sign, nexp, ii, jj, indexa, indexb, index0, numdigits; 87 UCHAR *cp, *cpr, *cp_div, *cp_rem; 88 void *vp; 89 90 sign = a->m_apm_sign * b->m_apm_sign; 91 nexp = a->m_apm_exponent + b->m_apm_exponent; 92 93 if (sign == 0) /* one number is zero, result is zero */ 94 { 95 M_set_to_zero(r); 96 return; 97 } 98 99 numdigits = a->m_apm_datalength + b->m_apm_datalength; 100 indexa = (a->m_apm_datalength + 1) >> 1; 101 indexb = (b->m_apm_datalength + 1) >> 1; 102 103 /* 104 * If we are multiplying 2 'big' numbers, use the fast algorithm. 105 * 106 * This is a **very** approx break even point between this algorithm 107 * and the FFT multiply. Note that different CPU's, operating systems, 108 * and compiler's may yield a different break even point. This point 109 * (~96 decimal digits) is how the test came out on the author's system. 110 */ 111 112 if (indexa >= 48 && indexb >= 48) 113 { 114 M_fast_multiply(r, a, b); 115 return; 116 } 117 118 ii = (numdigits + 1) >> 1; /* required size of result, in bytes */ 119 120 if (ii > r->m_apm_malloclength) 121 { 122 if ((vp = MAPM_REALLOC(r->m_apm_data, (ii + 32))) == NULL) 123 { 124 /* fatal, this does not return */ 125 126 M_apm_log_error_msg(M_APM_FATAL, "\'m_apm_multiply\', Out of memory"); 127 } 128 129 r->m_apm_malloclength = ii + 28; 130 r->m_apm_data = (UCHAR *)vp; 131 } 132 133 M_get_div_rem_addr(&cp_div, &cp_rem); 134 135 index0 = indexa + indexb; 136 cp = r->m_apm_data; 137 memset(cp, 0, index0); 138 ii = indexa; 139 140 while (TRUE) 141 { 142 index0--; 143 cpr = cp + index0; 144 jj = indexb; 145 ai = (int)a->m_apm_data[--ii]; 146 147 while (TRUE) 148 { 149 itmp = ai * b->m_apm_data[--jj]; 150 151 *(cpr-1) += cp_div[itmp]; 152 *cpr += cp_rem[itmp]; 153 154 if (*cpr >= 100) 155 { 156 *cpr -= 100; 157 *(cpr-1) += 1; 158 } 159 160 cpr--; 161 162 if (*cpr >= 100) 163 { 164 *cpr -= 100; 165 *(cpr-1) += 1; 166 } 167 168 if (jj == 0) 169 break; 170 } 171 172 if (ii == 0) 173 break; 174 } 175 176 r->m_apm_sign = sign; 177 r->m_apm_exponent = nexp; 178 r->m_apm_datalength = numdigits; 179 180 M_apm_normalize(r); 181 } 182 /****************************************************************************/ 183