17784Swpaul 27784Swpaul/* 37784Swpaul * M_APM - mapm_rcp.c 47784Swpaul * 57784Swpaul * Copyright (C) 2000 - 2007 Michael C. Ring 67784Swpaul * 77784Swpaul * Permission to use, copy, and distribute this software and its 87784Swpaul * documentation for any purpose with or without fee is hereby granted, 97784Swpaul * provided that the above copyright notice appear in all copies and 107784Swpaul * that both that copyright notice and this permission notice appear 117784Swpaul * in supporting documentation. 127784Swpaul * 137784Swpaul * Permission to modify the software is granted. Permission to distribute 147784Swpaul * the modified code is granted. Modifications are to be distributed by 157784Swpaul * using the file 'license.txt' as a template to modify the file header. 167784Swpaul * 'license.txt' is available in the official MAPM distribution. 177784Swpaul * 187784Swpaul * This software is provided "as is" without express or implied warranty. 197784Swpaul */ 207784Swpaul 217784Swpaul/* 227784Swpaul * $Id: mapm_rcp.c,v 1.7 2007/12/03 01:46:46 mike Exp $ 237784Swpaul * 247784Swpaul * This file contains the fast division and reciprocal functions 257784Swpaul * 267784Swpaul * $Log: mapm_rcp.c,v $ 277784Swpaul * Revision 1.7 2007/12/03 01:46:46 mike 287784Swpaul * Update license 297784Swpaul * 307784Swpaul * Revision 1.6 2003/07/21 20:20:17 mike 3150476Speter * Modify error messages to be in a consistent format. 327784Swpaul * 337784Swpaul * Revision 1.5 2003/05/01 21:58:40 mike 347784Swpaul * remove math.h 3579538Sru * 367784Swpaul * Revision 1.4 2003/03/31 22:15:49 mike 377784Swpaul * call generic error handling function 387784Swpaul * 397784Swpaul * Revision 1.3 2002/11/03 21:32:09 mike 407784Swpaul * Updated function parameters to use the modern style 4168962Sru * 427784Swpaul * Revision 1.2 2000/09/26 16:27:48 mike 4357731Ssheldonh * add some comments 4457731Ssheldonh * 457784Swpaul * Revision 1.1 2000/09/26 16:16:00 mike 467784Swpaul * Initial revision 477784Swpaul */ 48140293Sru 49140293Sru#include "m_apm_lc.h" 507784Swpaul 5157731Ssheldonh/****************************************************************************/ 5257731Ssheldonhvoid m_apm_divide(M_APM rr, int places, M_APM aa, M_APM bb) 5357731Ssheldonh{ 5457731SsheldonhM_APM tmp0, tmp1; 557784Swpaulint sn, nexp, dplaces; 567784Swpaul 5732302Sstevesn = aa->m_apm_sign * bb->m_apm_sign; 58140567Sru 597784Swpaulif (sn == 0) /* one number is zero, result is zero */ 607784Swpaul { 617784Swpaul if (bb->m_apm_sign == 0) 627784Swpaul { 637784Swpaul M_apm_log_error_msg(M_APM_RETURN, "\'m_apm_divide\', Divide by 0"); 647784Swpaul } 657784Swpaul 667784Swpaul M_set_to_zero(rr); 677784Swpaul return; 687784Swpaul } 697784Swpaul 7057731Ssheldonh/* 7157731Ssheldonh * Use the original 'Knuth' method for smaller divides. On the 7257731Ssheldonh * author's system, this was the *approx* break even point before 7357731Ssheldonh * the reciprocal method used below became faster. 747784Swpaul */ 757784Swpaul 767784Swpaulif (places < 250) 777784Swpaul { 787784Swpaul M_apm_sdivide(rr, places, aa, bb); 797784Swpaul return; 807784Swpaul } 8113744Smpp 827784Swpaul/* mimic the decimal place behavior of the original divide */ 837784Swpaul 8413744Smppnexp = aa->m_apm_exponent - bb->m_apm_exponent; 857784Swpaul 867784Swpaulif (nexp > 0) 877784Swpaul dplaces = nexp + places; 887784Swpaulelse 897784Swpaul dplaces = places; 907784Swpaul 917784Swpaultmp0 = M_get_stack_var(); 9268962Srutmp1 = M_get_stack_var(); 937784Swpaul 947784Swpaulm_apm_reciprocal(tmp0, (dplaces + 8), bb); 957784Swpaulm_apm_multiply(tmp1, tmp0, aa); 967784Swpaulm_apm_round(rr, dplaces, tmp1); 9732302Ssteve 9889362SruM_restore_stack(2); 997784Swpaul} 1007784Swpaul/****************************************************************************/ 10168962Sruvoid m_apm_reciprocal(M_APM rr, int places, M_APM aa) 1027784Swpaul{ 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