home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / C / BK-SC1_1.DMS / in.adf / Examples.Lha / Pi / pi.c < prev   
Encoding:
C/C++ Source or Header  |  1996-02-22  |  2.8 KB  |  154 lines
  1. /*
  2.  
  3. Programm für den Tröpfel-Algorithmus von PI
  4.  
  5. Algorithmus aus: Spektrum der Wissenschaft 12/1995, Mathematische Unterhaltungen
  6.  
  7. Originalversion von: Martin Knapmeyer, 03.01.1996
  8.  
  9. Umsetzung nach StormC: HAAGE & PARTNER GmbH, 16.02.1996
  10.  
  11. Mit 32 bit Integers kann man auch sehr viele Dezimalen berechnen, mit 16 bit
  12. Integers wäre 10000 Dezimalen etwa die Grenze.
  13.  
  14. Allerdings hat der Algorithmus quadratische Ordnung: doppelte Anzahl Stellen,
  15. vierfache Zeit. Schon 10000 Stellen brauchen auf einem A3000 etwa 2 Stunden.
  16.  
  17. */
  18.  
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21. #include <time.h>
  22.  
  23. int n; // Anzahl der Nachkommastellen
  24. int klen;
  25.  
  26. int *result; // Zeiger auf ein Feld mit n int
  27. int *chain;  // Zeiger auf ein Feld mit klen == 10 * n / 3 int
  28. int *temp;   // Zeiger auf ein Feld mit n int
  29.  
  30. #ifndef NDEBUG
  31. void write_chain(void)
  32. {
  33.     int i;
  34.     for (i = 0; i < klen; i++)
  35.         printf("%ld ",chain[i]);
  36.     printf("\n");
  37. }
  38. #endif
  39.  
  40. void write_result(void)
  41. {
  42.     int i;
  43.     printf("PI:\n");
  44.     for (i = 1; i < n; i++)
  45.     {
  46.         printf("%ld",result[i]);
  47.         if (i % 50 == 0)
  48.             printf("\n");
  49.     };
  50.     printf("\n");
  51. }
  52.  
  53. void init_chain(void)
  54. {
  55.     int i;
  56.     for (i = 0; i < klen; i++)
  57.         chain[i] = 2;
  58. }
  59.  
  60. void drop(void)
  61. {
  62.     int vcnt = 0, ecnt = 0;
  63.     int i,j;
  64.     div_t qr;
  65.     for (i = 0; i < n; i++)
  66.     {
  67.         for (j = 0; j < klen; j++)
  68.             chain[j] *= 10;
  69.         for (j = klen - 1; j >= 1; j--)
  70.         {
  71.             qr = div(chain[j],(2*j + 1));
  72.             chain[j] = qr.rem;
  73.             chain[j - 1] += qr.quot*j;
  74.         };
  75.         qr = div(chain[0],10);
  76.         chain[0] = qr.rem;
  77.         if (qr.quot != 9 && qr.quot != 10)
  78.         {
  79.             for (j = 0; j <= vcnt; j++)
  80.             {
  81.                 #ifndef NDEBUG
  82.                     printf("%ld. Stelle: %ld\n",ecnt-1,temp[j]);
  83.                 #endif
  84.                 result[ecnt] = temp[j];
  85.                 ecnt++;
  86.                 temp[j] = 0;
  87.             };
  88.             vcnt = 0;
  89.             temp[vcnt] = qr.quot;
  90.         }
  91.         else
  92.         {
  93.             if (qr.quot == 9)
  94.             {
  95.                 vcnt++;
  96.                 temp[vcnt] = qr.quot;
  97.             }
  98.             else // if (qr.quot == 10)
  99.             {
  100.                 qr.quot = 1;
  101.                 for (j = vcnt; j >= 0; j--)
  102.                 {
  103.                     temp[j] += qr.quot;
  104.                     qr = div(temp[j],10);
  105.                     temp[j] = qr.rem;
  106.                 };
  107.                 for (j = 0; j <= vcnt; j++)
  108.                 {
  109.                     #ifndef NDEBUG
  110.                         printf("%ld. Stelle: %ld\n",ecnt-1,temp[j]);
  111.                     #endif
  112.                     result[ecnt] = temp[j];
  113.                     ecnt++;
  114.                     temp[j] = 0;
  115.                 };
  116.                 vcnt = 0;
  117.                 temp[0] = 0;
  118.             }
  119.         };
  120.     };
  121. }
  122.  
  123. void main(void)
  124. {
  125.     clock_t timestart,timeend;
  126.     printf("Berechnung von PI\n");
  127.     for (;;)
  128.     {
  129.         printf("Stellenanzahl (0 für Ende):"); fflush(stdout);
  130.         scanf("%ld",&n);
  131.         if (n < 1)
  132.             exit(0);
  133.         klen = (n * 10) / 3;
  134.         result = (int *) malloc(n*sizeof(int));
  135.         chain = (int *) malloc(klen*sizeof(int));
  136.         temp = (int *) malloc(n*sizeof(int));
  137.         if (result == NULL || chain == NULL || temp == NULL)
  138.         {
  139.             printf("no memory, no pi.\n");
  140.             exit(100);
  141.         };
  142.         init_chain();
  143.         timestart = clock();
  144.         drop();
  145.         timeend = clock();
  146.         printf("Zeitbedarf für %ld Stellen: %lds\n",n,
  147.             (timeend-timestart) / CLOCKS_PER_SEC);
  148.         write_result();
  149.         free(result);
  150.         free(chain);
  151.         free(temp);
  152.     };
  153. }
  154.