home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / PI8.NFO < prev    next >
Text File  |  1997-07-05  |  7KB  |  188 lines
  1. +++Date last modified: 05-Jul-1997
  2.  
  3. This info file is placed into the public domain by its author, Carey
  4. Bloodworth, on Sept 24, 1996.  This info file just describes some of the
  5. thoughts I had while writing the arctangent pi program.
  6.  
  7.  
  8. PI programs are  a  carefull  collection  of  compromises.  It's not
  9. possible to write a single program that will  be  suitable  for  all
  10. circumstances.
  11.  
  12. There are a number  of  things  you  need  to think about before you
  13. actually  start  writing  the  program.   And  many  of   them   are
  14. inter-related.
  15.  
  16. Questions like:
  17.  
  18. What  is  the maximum size of the calculation?  It's not possible to
  19. make it so generic that  it  will  be  convenient for a few thousand
  20. digits, but still be capable of generating millions.
  21.  
  22. Are other people going to have to understand  the  program?   People
  23. who perhaps have little to no pi programming experience?
  24.  
  25. What type of hardware will the program be run on?  How powerful?
  26.  
  27. What formula should you use?
  28.  
  29. What base will you work in?
  30.  
  31. Do  you want to print out the digits while the calculation is going,
  32. or wait until it's done?
  33.  
  34. What language will  the  program  be  in?   Some  languages are more
  35. suitable than others, and some formulas are more suitable  for  some
  36. languages than others.
  37.  
  38. What will the failure point be?
  39.  
  40.  
  41. Okay....
  42.  
  43. It has to be fully in C, since that would make it portable.
  44.  
  45. We've got a variety  of  bases,  work  sizes, and formulas to choose
  46. from.
  47.  
  48. For  the base, I'm going to work in some power of 10.  That makes it
  49. easy  to  print.   It does take a bit more memory than some power of
  50. two, but since we are  working  in  C,  there  is  no  advantage  to
  51. actually  working in either one.  So, I might as well go with what's
  52. easy to print.
  53.  
  54. In an effort to  keep  things  simple,  that limits the selection to
  55. mostly arctangent formulas.
  56.  
  57. For the arctangent formulas, I'm going to use:
  58.  
  59. pi=16arctan(1/5)-4arctan(1/239)
  60. pi=32arctan(1/10)-4arctan(1/239)-16arctan(1/515)
  61. pi=8arctan(1/3)+4arctan(1/7)
  62. pi=16arctan(1/5)-4arctan(1/70)+4arctan(1/99)
  63. pi=12arctan(1/4)+4arctan(1/20)+4arctan(1/1985)
  64.  
  65. That should provide enough  cross  checking  so  the user can always
  66. verify their calculations.  They  aren't  the  most  efficient,  but
  67. arctangents are O(n^2) anyway.
  68.  
  69.  
  70. To calculate the limit of the formula, we have to consider  that  we
  71. are working in C, and that our variables need to be able to hold the
  72. maximum divisor times the base size.  Formula wise, it would be:
  73.  
  74.                BASE*MaxDivisor=MaxUint
  75.  
  76. For a 16 bit integer and our base of 10, it'd be:
  77.  
  78.                10*MaxDivisor=65535
  79.                MaxDivisor=6553
  80.  
  81. To  determine  how  many  digits this would be capable of generating
  82. that are 'guaranteed' correct, you  use the relationship between the
  83. divisor and the number of digits.
  84.  
  85.                NumDigits=MaxDivisor*log10(term)
  86.  
  87. The  'term'  is the lowest part of the arctangent relationship.  For
  88. the classic pi=16arctan(1/5)-4arctan(1/239),  we'd  use the 5, since
  89. that is the part that will require the most number of divisions  and
  90. be the part to most likely overflow.
  91.  
  92. (Note: This formula could be recast to calculate what the MaxDivisor
  93.  would be.  If you do, you'd need to add 4.  That won't be exact, but
  94.  it'll be 'close enough for government work'.)               
  95.  
  96.  
  97. So, let's calculate a few limits.
  98.  
  99. 16 bit integers:
  100. For base 10, the max divisor would be 6553
  101. So, the number of digits possible would be:
  102.  3: log10(3) * 6553 = 3126
  103.  4: log10(4) * 6553 = 3945
  104.  5: log10(5) * 6553 = 4580
  105. 10: log10(10)* 6553 = 6553
  106.  
  107. That's way too low.  With assembler, or careful coding, it would  be
  108. possible to go all the way up to  a  max  divisor  size  of  65,535,
  109. allowing about 64k digits  with  the arctan(10) formula.  But that's
  110. still too low.
  111.  
  112. 32 bit integers:
  113.  
  114. For base 10, the max divisor would be 429496729
  115. So, the number of digits possible would be:
  116.  3: log10(3) * 429496729 = 204,922,018
  117.  4: log10(4) * 429496729 = 258,582,797
  118.  5: log10(5) * 429496729 = 300,205,330
  119. 10: log10(10)* 429496729 = 429,496,729
  120.  
  121. That's more than what I  need!   So,  let's try a larger base.  Say,
  122. 100
  123.  
  124. 32 bit integers:
  125. For base 100, the max divisor would be 42949672
  126. So, the number of digits possible would be:
  127.  3: log10(3) * 42949672 = 20,492,201
  128.  4: log10(4) * 42949672 = 25,858,279
  129.  5: log10(5) * 42949672 = 30,020,533
  130. 10: log10(10)* 42949672 = 42,949,672
  131.  
  132. That's still more than I really need.  It would work,  but  it  just
  133. seems a shame to waste the extra space that I'm not going to use.
  134.  
  135. 32 bit integers:
  136. For base 10,000, the max divisor would be 429496
  137. So, the number of digits possible would be:
  138.  3: log10(3) * 429496 = 204,922
  139.  4: log10(4) * 429496 = 258,582
  140.  5: log10(5) * 429496 = 300,205
  141. 10: log10(10)* 429496 = 429,496
  142.  
  143. That's not enough.  It would certainly work for most situations, but
  144. I did sort of set that  arbitrary  limit  of being able to reach one
  145. million.
  146.  
  147. So, it looks like the best we can do with 32 bit integers is to have
  148. a base of 100.  And of course, a base of 100 fits into an char.
  149.  
  150.  
  151. Just for curosity, I'm going to try it with the floating point type.
  152. There  wouldn't  be any point in doing it with a 'float', since that
  153. has only 24 bits of mantissa.  Double's though might be useful.
  154.  
  155. C's 'double' type, with 53 bits of mantissa.
  156. For base 10,000 the max divisor would be 9e11
  157. So, the number of digits possible would be:
  158.  3: log10(3) * 9e11 = 4e11
  159.  4: log10(4) * 9e11 = 5e11
  160.  5: log10(5) * 9e11 = 6e11
  161. 10: log10(10)* 9e11 = 9e11
  162.  
  163. That's _way_ too many.  So I'm going to go for a base a 1e9.  That's
  164. the largest power of 10 that will fit into a long integer.
  165.  
  166. C's 'double' type, with 53 bits of mantissa.
  167. For base 1,000,000,000 the max divisor would be 9,007,199
  168. So, the number of digits possible would be:
  169.  3: log10(3) * 9,007,199 = 4,297,526
  170.  4: log10(4) * 9,007,199 = 5,422,874
  171.  5: log10(5) * 9,007,199 = 6,295,761
  172. 10: log10(10)* 9,007,199 = 9,007,199
  173.  
  174. Alright!   That  looks a lot better!  We are getting a lot of digits
  175. from each piece of 'work' that  we  do, and the limit is high enough
  176. to be useful, but low enough to not be rediculous.
  177.  
  178.  
  179. Well...!   It looks like we have two possibilities.  32 bit integers
  180. and a base of 100, or  use  the  FPU  and a base of 1e9.  Well, most
  181. computers do have a FPU.  And the larger base  would  make  it  more
  182. efficient.   But  that  would  penalize the few computers that don't
  183. have a FPU.
  184.  
  185. Fortunately, I don't have to actually decide!  As long as I keep the
  186. code generic, and limit  the  number  of  optimizations, I should be
  187. able to do _both_ forms, selectable with a compile time 'define'!
  188.