home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / intercal.zip / pit / pi.doc < prev    next >
Internet Message Format  |  1994-04-25  |  4KB
  1. From howell@grover.llnl.gov (Louis Howell) Fri Jan  3 12:31:20 1992
  2. From: howell@grover.llnl.gov (Louis Howell)
  3. Path: snark!cbmvax!uunet!uunet!spool.mu.edu!agate!bionet!raven.alaska.edu!lll-winken!grover.llnl.gov!howell
  4. Newsgroups: alt.lang.intercal
  5. Subject: pi.doc
  6. Message-ID: <114696@lll-winken.LLNL.GOV>
  7. Date: 3 Jan 92 17:31:20 GMT
  8. Date-Received: 4 Jan 92 11:08:10 GMT
  9. Sender: usenet@lll-winken.LLNL.GOV
  10. Distribution: world
  11. Organization: Lawrence Livermore National Laboratory
  12. Nntp-Posting-Host: grover.llnl.gov
  13. Lines: 91
  14.  
  15. Those of you who've bothered to actually run the "mystery program" I
  16. posted last week will have realized that it prints out digits of pi.
  17. If you didn't get it, never fear.  Eric is putting it into his new
  18. 0.8 release, which he is eager to finish soon.  The program is pi.i,
  19. and the stuff below this line is pi.doc:
  20.  
  21. ---------------
  22.  
  23. pi.i is easily the most twisted and obscure INTERCAL program I've yet
  24. written.  I say that because even I don't fully understand why it
  25. works.  The program writes in one number from the input, then prints
  26. out that many digits of pi.  There are no fancy INTERCAL tricks here;
  27. all it does is simple integer arithmetic.
  28.  
  29. The algorithm used comes from an old TECO macro that was recently
  30. discussed on alt.lang.teco.  Mark Henderson posted a translation
  31. into C, which at least made it easier to read, if not much easier to
  32. understand.  I played around with that program a bit, fixed a couple
  33. of minor bugs which may or may not have existed in the original TECO,
  34. and modified it a bit to put in into a form that would be easy to
  35. translate into INTERCAL.  That modified program, which corresponds
  36. closely to the algorithm in pi.i, is reproduced at the end of this
  37. file.
  38.  
  39. The INTERCAL version has only been tested up to a hundred digits,
  40. which took almost 30 minutes on a Sparc 1.  The C version below,
  41. with variables declared unsigned short to correspond to the INTERCAL,
  42. gives up to 535 accurate digits and then starts printing garbage,
  43. presumably because of an overflow.  If the declarations are changed
  44. to short only the first 262 digits are accurate, while using int
  45. yields thousands of accurate digits.  Though I don't understand
  46. what the inner loop is doing, it looks like the largest numbers
  47. encountered are O(n), where n is the number of digits requested.
  48. If, as I expect, the present INTERCAL version does fail after about
  49. 535 digits, it could easily be converted to a 32-bit form which
  50. would run as long as almost anyone would desire.
  51.  
  52. The only feature likely to be of utility in other INTERCAL programs
  53. is the new (2030) routine, which performs a 16-bit division with
  54. remainder.  It is faster than the (1040) routine for two reasons:
  55. First, it is a true 16-bit version, whereas the (1040) routine just
  56. shifts over its operands and then calls the 32-bit division routine
  57. (1550).  Second, the (1550) routine generates a remainder as part of
  58. the computation, but then simply throws it away.  I needed the
  59. remainder, so I have my (2030) routine return it in .4 and the
  60. quotient in .3.  In other respects this is just a 16-bit translation
  61. of the (1550) routine.
  62.  
  63.                 Louis Howell
  64.                 December 30, 1991
  65.  
  66.  
  67.  
  68. #include <stdio.h>
  69. unsigned short line[10000];
  70. main(argc,argv)
  71. int argc;
  72. char *argv[];
  73. {
  74.    unsigned short n, a, i, q, v, dummy, h=0, w=0;
  75.    
  76.    if (argc==2)
  77.      n=atoi(argv[1]);
  78.    else
  79.      n=20;
  80.  
  81.    n+=2;
  82.  
  83.    for (i=(n*10)/3 ; i > 0 ; i--) {
  84.      line[i-1] = 2;
  85.    }
  86.  
  87.    for (dummy=0; dummy < n; dummy++) {
  88.       q=0;
  89.       for (i=(n*10)/3 ; i > 0 ; i--) {
  90.          a = line[i-1] * 10 + (q*i);
  91.          q=a/(i*2-1);
  92.          line[i-1] = a%(i*2-1);
  93.       }
  94.       v = w;
  95.       w = h+(q/10);
  96.       h = q%10;
  97.       if (w==10) {
  98.          w=0;
  99.          v++;
  100.       }
  101.       if (dummy!=0)
  102.          printf("%d", v);
  103.    }
  104.    printf("\n");
  105. }
  106.  
  107.  
  108.