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
81extern void M_fast_multiply(M_APM, M_APM, M_APM);
82
83/****************************************************************************/
84void	m_apm_multiply(M_APM r, M_APM a, M_APM b)
85{
86int	ai, itmp, sign, nexp, ii, jj, indexa, indexb, index0, numdigits;
87UCHAR   *cp, *cpr, *cp_div, *cp_rem;
88void	*vp;
89
90sign = a->m_apm_sign * b->m_apm_sign;
91nexp = a->m_apm_exponent + b->m_apm_exponent;
92
93if (sign == 0)      /* one number is zero, result is zero */
94  {
95   M_set_to_zero(r);
96   return;
97  }
98
99numdigits = a->m_apm_datalength + b->m_apm_datalength;
100indexa = (a->m_apm_datalength + 1) >> 1;
101indexb = (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
112if (indexa >= 48 && indexb >= 48)
113  {
114   M_fast_multiply(r, a, b);
115   return;
116  }
117
118ii = (numdigits + 1) >> 1;     /* required size of result, in bytes */
119
120if (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
133M_get_div_rem_addr(&cp_div, &cp_rem);
134
135index0 = indexa + indexb;
136cp = r->m_apm_data;
137memset(cp, 0, index0);
138ii = indexa;
139
140while (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
176r->m_apm_sign       = sign;
177r->m_apm_exponent   = nexp;
178r->m_apm_datalength = numdigits;
179
180M_apm_normalize(r);
181}
182/****************************************************************************/
183