home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3542 < prev    next >
Encoding:
Text File  |  1993-01-21  |  2.3 KB  |  71 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!newsgate.watson.ibm.com!yktnews2.watson.ibm.com!yktnews!admin!flu!lowry
  3. From: lowry@watson.ibm.com (Andy Lowry)
  4. Subject: Re: how to calculate PI
  5. Sender: news@watson.ibm.com (NNTP News Poster)
  6. Message-ID: <LOWRY.93Jan21133303@rotor.watson.ibm.com>
  7. In-Reply-To: lowry@watson.ibm.com's message of Thu, 21 Jan 1993 17:45:21 GMT
  8. Date: Thu, 21 Jan 1993 18:33:03 GMT
  9. Disclaimer: This posting represents the poster's views, not necessarily those of IBM
  10. References: <peterd.727508100@tscc2> <LOWRY.93Jan20104500@rotor.watson.ibm.com>
  11.     <c8h3xpm@rpi.edu> <bosullvn.727615765@unix1.tcd.ie>
  12.     <LOWRY.93Jan21124521@rotor.watson.ibm.com>
  13. Nntp-Posting-Host: rotor.watson.ibm.com
  14. Organization: IBM T.J. Watson Research Center
  15. Lines: 54
  16.  
  17. In article <LOWRY.93Jan21124521@rotor.watson.ibm.com> lowry@watson.ibm.com (Andy Lowry) writes:
  18.  > A straightforward implementation does the following to compute
  19.  > atan(1/x):
  20.  
  21. Oops... I should have called it a "straightforward but incorrect
  22. implementation." :-)
  23.  
  24. The algorithm I presented would compute f(x) = x - x^3/3 + x^5/3*5 -
  25. x^7/3*5*7 + ...
  26.  
  27. The correct algorithm, expressed this time in something similar to C,
  28. is as follows (the type "extended" is intended to mean an extended
  29. precision fixed point number, represented as a vector of ints with an
  30. implied decimal point between the 1st and 2nd elements; both division
  31. of an extended by a normal int, and addition or subtraction of two
  32. extended's can be performed in O(n) time, as indicated in my earlier
  33. post, where n is the size of the vector representing an extended
  34. value):
  35.  
  36. extended atanrecip(x) /* compute atan(1/x) */
  37. int x;
  38. {
  39.   extended sum, t1, t2;
  40.   int i;
  41.  
  42.   sum = 0;
  43.   t1 = x;
  44.   i = 1;
  45.   while (t1 != 0) {
  46.     t1 /= x^2;
  47.     t2 = t1;
  48.     t2 /= (2*i-1);
  49.     if (i%2 == 0)
  50.       sum -= t2;
  51.     else
  52.       sum += t2;
  53.     i += 1;
  54.   }
  55.   return sum;
  56. }
  57.  
  58. Then you compute pi via:
  59.  
  60.   extended pi;
  61.   pi = 4*(4*atanrecip(5)-atanrecip(239));
  62.  
  63. The running time is, as it was for the algorithm I first posted,
  64. O(n^2), and if variable i in atanrecip needs to become an extended the
  65. running time becomes O(n^3).  (OK... i would never really be an
  66. extended, since its presumed decimal point would not be between the
  67. 1st and 2nd vector elements... but you know what I mean!)
  68. --
  69. Andy Lowry, lowry@watson.ibm.com, (914) 784-7925
  70. IBM Research, P.O. Box 704, Yorktown Heights, NY  10598
  71.