home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 13199 < prev    next >
Encoding:
Text File  |  1992-10-14  |  2.4 KB  |  88 lines

  1. Path: sparky!uunet!seismo!darwin.sura.net!jvnc.net!princeton!ginger.princeton.edu!tao
  2. From: tao@ginger.princeton.edu (Terry Tao)
  3. Newsgroups: sci.math
  4. Subject: Re: Calculating pi: help!
  5. Message-ID: <1992Oct14.194009.27975@Princeton.EDU>
  6. Date: 14 Oct 92 19:40:09 GMT
  7. References: <Bw304E.LKu@mentor.cc.purdue.edu> <7557@charon.cwi.nl> <stephen.719088307@mont>
  8. Sender: news@Princeton.EDU (USENET News System)
  9. Organization: Princeton University
  10. Lines: 74
  11. Originator: news@nimaster
  12. Nntp-Posting-Host: ginger.princeton.edu
  13.  
  14. In article <stephen.719088307@mont>, stephen@mont.cs.missouri.edu (Stephen Montgomery-Smith) writes:
  15. |> In <7557@charon.cwi.nl> dik@cwi.nl (Dik T. Winter) writes:
  16. |> 
  17. |> >int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;for(;d=0,g=c*2;c
  18. |> >-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}
  19. |> 
  20. |> 
  21. |> I would be very interested to know how this program works.
  22. |> 
  23. |> Stephen
  24. |> 
  25.  
  26. One note about the program: it assumes that b, d, e, and g are initialized to 0.
  27.  
  28. in pseudo code the rather compact program does the following:
  29.  
  30. set a as the constant 10000
  31. set c as 2800
  32.  
  33. set f[b] = a/5 for all b from 0 to c-1
  34.  
  35. while c is positive
  36.   set b = c, d = 0, g = 2*c
  37.   while b is positive
  38.     d is multipled by b
  39.     d is incremented by a*f[b]
  40.     f[b] becomes d mod g-1
  41.     d is divided by g-1
  42.     g is decremented by 2
  43.     b is decremented by 1
  44.   end while
  45.   subtract 14 from c
  46.   print as four digits the integer part of e+d/a
  47.   e becomes d mod a
  48. end while
  49.  
  50. in BASIC the program is equivalent to (note: don't try to run this program!)
  51.  
  52. DEFINT A-E
  53. DEFDDBL P,X
  54. DIM F(2800)
  55.  
  56. CONST DIGIT_CHUNK 4
  57. CONST A = 10^DIGIT_CHUNK
  58. CONST DIGITS = 800
  59. CONST CMAX = DIGITS/DIGIT_CHUNK * 14
  60. X = 1/A
  61.  
  62. FOR B = 0 TO CMAX-1: F(B) = A/5: NEXT B
  63.  
  64. FOR C = CMAX TO 0 STEP -14
  65.   D=0
  66.   FOR B = C TO 1 STEP -1
  67.     D = D * B
  68.     D = D + A*F(B)
  69.     F[B] = D MOD (2*B-1)
  70.     D = INT(D/(2*B-1))
  71.   NEXT B
  72.   PI = PI + D*X 
  73.   X = X/A
  74. NEXT C
  75. ?PI
  76.  
  77.   
  78. However, the actual device used to calculate pi here is still obscure to me.
  79. After eliminating the clever mechanisms for dealing with remainders of fractions
  80. with integers, I think when you come right down to it we are using a formula of
  81. the form (I've probably made a few minor mistakes, but this is what it should be)
  82.  
  83. pi = \sum_{c = 1}^\infty 1/5 \prod_{b = 1}^{c*14} b / (2*b-1)
  84.  
  85. But I've never heard of this formula or anything like it! why the 14 and the 5?
  86.  
  87. Terry
  88.