src/libs/mapm/mapm_rcp.c

   1
   2 /*
   3  *  M_APM  -  mapm_rcp.c
   4  *
   5  *  Copyright (C) 2000 - 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_rcp.c,v 1.7 2007/12/03 01:46:46 mike Exp $
  23  *
  24  *      This file contains the fast division and reciprocal functions
  25  *
  26  *      $Log: mapm_rcp.c,v $
  27  *      Revision 1.7  2007/12/03 01:46:46  mike
  28  *      Update license
  29  *
  30  *      Revision 1.6  2003/07/21 20:20:17  mike
  31  *      Modify error messages to be in a consistent format.
  32  *
  33  *      Revision 1.5  2003/05/01 21:58:40  mike
  34  *      remove math.h
  35  *
  36  *      Revision 1.4  2003/03/31 22:15:49  mike
  37  *      call generic error handling function
  38  *
  39  *      Revision 1.3  2002/11/03 21:32:09  mike
  40  *      Updated function parameters to use the modern style
  41  *
  42  *      Revision 1.2  2000/09/26 16:27:48  mike
  43  *      add some comments
  44  *
  45  *      Revision 1.1  2000/09/26 16:16:00  mike
  46  *      Initial revision
  47  */
  48
  49 #include "m_apm_lc.h"
  50
  51 /****************************************************************************/
  52 void    m_apm_divide(M_APM rr, int places, M_APM aa, M_APM bb)
  53 {
  54 M_APM   tmp0, tmp1;
  55 int     sn, nexp, dplaces;
  56
  57 sn = aa->m_apm_sign * bb->m_apm_sign;
  58
  59 if (sn == 0)                  /* one number is zero, result is zero */
  60   {
  61    if (bb->m_apm_sign == 0)
  62      {
  63       M_apm_log_error_msg(M_APM_RETURN, "\'m_apm_divide\', Divide by 0");
  64      }
  65
  66    M_set_to_zero(rr);
  67    return;
  68   }
  69
  70 /*
  71  *    Use the original 'Knuth' method for smaller divides. On the
  72  *    author's system, this was the *approx* break even point before
  73  *    the reciprocal method used below became faster.
  74  */
  75
  76 if (places < 250)
  77   {
  78    M_apm_sdivide(rr, places, aa, bb);
  79    return;
  80   }
  81
  82 /* mimic the decimal place behavior of the original divide */
  83
  84 nexp = aa->m_apm_exponent - bb->m_apm_exponent;
  85
  86 if (nexp > 0)
  87   dplaces = nexp + places;
  88 else
  89   dplaces = places;
  90
  91 tmp0 = M_get_stack_var();
  92 tmp1 = M_get_stack_var();
  93
  94 m_apm_reciprocal(tmp0, (dplaces + 8), bb);
  95 m_apm_multiply(tmp1, tmp0, aa);
  96 m_apm_round(rr, dplaces, tmp1);
  97
  98 M_restore_stack(2);
  99 }
 100 /****************************************************************************/
 101 void    m_apm_reciprocal(M_APM rr, int places, M_APM aa)
 102 {
 103 M_APM   last_x, guess, tmpN, tmp1, tmp2;
 104 char    sbuf[32];
 105 int     ii, bflag, dplaces, nexp, tolerance;
 106
 107 if (aa->m_apm_sign == 0)
 108   {
 109    M_apm_log_error_msg(M_APM_RETURN, "\'m_apm_reciprocal\', Input = 0");
 110
 111    M_set_to_zero(rr);
 112    return;
 113   }
 114
 115 last_x = M_get_stack_var();
 116 guess  = M_get_stack_var();
 117 tmpN   = M_get_stack_var();
 118 tmp1   = M_get_stack_var();
 119 tmp2   = M_get_stack_var();
 120
 121 m_apm_absolute_value(tmpN, aa);
 122
 123 /*
 124     normalize the input number (make the exponent 0) so
 125     the 'guess' below will not over/under flow on large
 126     magnitude exponents.
 127 */
 128
 129 nexp = aa->m_apm_exponent;
 130 tmpN->m_apm_exponent -= nexp;
 131
 132 m_apm_to_string(sbuf, 15, tmpN);
 133 m_apm_set_double(guess, (1.0 / atof(sbuf)));
 134
 135 tolerance = places + 4;
 136 dplaces   = places + 16;
 137 bflag     = FALSE;
 138
 139 m_apm_negate(last_x, MM_Ten);
 140
 141 /*   Use the following iteration to calculate the reciprocal :
 142
 143
 144          X     =  X  *  [ 2 - N * X ]
 145           n+1
 146 */
 147
 148 ii = 0;
 149
 150 while (TRUE)
 151   {
 152    m_apm_multiply(tmp1, tmpN, guess);
 153    m_apm_subtract(tmp2, MM_Two, tmp1);
 154    m_apm_multiply(tmp1, tmp2, guess);
 155
 156    if (bflag)
 157      break;
 158
 159    m_apm_round(guess, dplaces, tmp1);
 160
 161    /* force at least 2 iterations so 'last_x' has valid data */
 162
 163    if (ii != 0)
 164      {
 165       m_apm_subtract(tmp2, guess, last_x);
 166
 167       if (tmp2->m_apm_sign == 0)
 168         break;
 169
 170       /*
 171        *   if we are within a factor of 4 on the error term,
 172        *   we will be accurate enough after the *next* iteration
 173        *   is complete.
 174        */
 175
 176       if ((-4 * tmp2->m_apm_exponent) > tolerance)
 177         bflag = TRUE;
 178      }
 179
 180    m_apm_copy(last_x, guess);
 181    ii++;
 182   }
 183
 184 m_apm_round(rr, places, tmp1);
 185 rr->m_apm_exponent -= nexp;
 186 rr->m_apm_sign = aa->m_apm_sign;
 187 M_restore_stack(5);
 188 }
 189 /****************************************************************************/