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 /****************************************************************************/
m_apm_divide(M_APM rr,int places,M_APM aa,M_APM bb)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 /****************************************************************************/
m_apm_reciprocal(M_APM rr,int places,M_APM aa)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 /****************************************************************************/
190