src/libs/mapm/mapm_mul.c

   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 /****************************************************************************/