"Fossies" - the Fresh Open Source Software Archive 
Member "mapm_4.9.5a/mapm_mul.c" (21 Feb 2010, 4924 Bytes) of package /linux/misc/old/mapm-4.9.5a.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "mapm_mul.c" see the
Fossies "Dox" file reference documentation.
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 /****************************************************************************/