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/****************************************************************************/
52void	m_apm_divide(M_APM rr, int places, M_APM aa, M_APM bb)
53{
54M_APM   tmp0, tmp1;
55int     sn, nexp, dplaces;
56
57sn = aa->m_apm_sign * bb->m_apm_sign;
58
59if (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
76if (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
84nexp = aa->m_apm_exponent - bb->m_apm_exponent;
85
86if (nexp > 0)
87  dplaces = nexp + places;
88else
89  dplaces = places;
90
91tmp0 = M_get_stack_var();
92tmp1 = M_get_stack_var();
93
94m_apm_reciprocal(tmp0, (dplaces + 8), bb);
95m_apm_multiply(tmp1, tmp0, aa);
96m_apm_round(rr, dplaces, tmp1);
97
98M_restore_stack(2);
99}
100/****************************************************************************/
101void	m_apm_reciprocal(M_APM rr, int places, M_APM aa)
102{
103M_APM   last_x, guess, tmpN, tmp1, tmp2;
104char    sbuf[32];
105int	ii, bflag, dplaces, nexp, tolerance;
106
107if (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
115last_x = M_get_stack_var();
116guess  = M_get_stack_var();
117tmpN   = M_get_stack_var();
118tmp1   = M_get_stack_var();
119tmp2   = M_get_stack_var();
120
121m_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
129nexp = aa->m_apm_exponent;
130tmpN->m_apm_exponent -= nexp;
131
132m_apm_to_string(sbuf, 15, tmpN);
133m_apm_set_double(guess, (1.0 / atof(sbuf)));
134
135tolerance = places + 4;
136dplaces   = places + 16;
137bflag     = FALSE;
138
139m_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
148ii = 0;
149
150while (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
184m_apm_round(rr, places, tmp1);
185rr->m_apm_exponent -= nexp;
186rr->m_apm_sign = aa->m_apm_sign;
187M_restore_stack(5);
188}
189/****************************************************************************/
190