diff options
Diffstat (limited to 'pi_bbp.c')
| -rw-r--r-- | pi_bbp.c | 169 |
1 files changed, 169 insertions, 0 deletions
diff --git a/pi_bbp.c b/pi_bbp.c new file mode 100644 index 0000000..c51944f --- /dev/null +++ b/pi_bbp.c @@ -0,0 +1,169 @@ +/*
+ * http://www.cut-the-knot.org/Curriculum/Algorithms/SpigotForPi.shtml
+ *
+ * Original code is available in public domain
+ * Pi Decimal Point Calculation using BBP (named after Bailey-Borwein-Plouffe)
+ *
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <wchar.h>
+#include <time.h>
+#include <sys/time.h>
+
+/* globals */
+int printed = 0;
+int line = 1;
+int mulof2 = 1;
+
+/* function prototypes */
+inline void out_dig(long unsigned, struct timeval *);
+inline void printTime(struct timeval *);
+int do_calc(char **);
+
+inline void out_dig(long unsigned dig, struct timeval *before)
+{
+ putchar(dig);
+ printed++;
+
+ if ((printed % 50) == 0)
+ {
+ if ((line % (20 * mulof2)) == 0)
+ {
+ printf("\n%dK: ", mulof2);
+ mulof2 *= 2;
+
+ printTime(before);
+ }
+
+ printf("\nd %06d: ", 50 * line);
+ line++;
+ }
+ else if ((printed % 10) == 0)
+ putchar(' ');
+}
+
+inline void printTime(struct timeval *before)
+{
+ struct timeval after;
+ gettimeofday(&after, 0);
+ long unsigned int elapsed_ms = (after.tv_sec - before->tv_sec) * 1000 +
+ (after.tv_usec - before->tv_usec) / 1000;
+ unsigned int seconds_n = elapsed_ms / 1000;
+ unsigned int milliseconds_n = elapsed_ms % 1000;
+
+ printf("time elapsed: %lu.%lu seconds\n", seconds_n, milliseconds_n);
+}
+
+int do_calc(char **argv)
+{
+ long unsigned int i, j, k, nines, predigit;
+ long unsigned int q, x, digits_n, len;
+ long unsigned int *pi;
+ long unsigned int alloc;
+
+ digits_n = atol(argv[1]);
+ if (digits_n < 1)
+ return 0;
+
+ len = (digits_n * 10) / 3;
+ alloc = sizeof(long unsigned int) * (len+1);
+
+ pi = (long unsigned int *) malloc(alloc);
+ if (!pi)
+ {
+ perror("malloc");
+ exit(-1);
+ }
+ else
+ printf("\n\tPi Decimal Digit Calculation\n"
+ "allocated %ldKb of heap memory\n", alloc / 1024);
+
+ for (i = 0; i < len; i++)
+ pi[i] = 2;
+
+ /* wchar_t pi_c = 0x03c0; */
+ printf("Pi value: 3.");
+
+ nines = 0;
+ predigit = 0;
+
+ struct timeval before;
+ gettimeofday(&before, 0);
+
+ for (j = 0; j <= digits_n; j++)
+ {
+ q = 0;
+
+ for (i = len; i > 0; i--)
+ {
+ x = 10 * pi[i] + q * i;
+ pi[i] = x % (2 * i - 1);
+ q = x / (2 * i - 1);
+ }
+
+ pi[1] = q % 10;
+ q = q / 10;
+
+ if (q == 9)
+ nines++;
+ else if (q == 10)
+ {
+ out_dig('1' + predigit, &before);
+
+ while (nines)
+ {
+ out_dig('0', &before);
+ nines--;
+ }
+
+ predigit = 0;
+ fflush(stdout);
+ }
+ else
+ {
+ if (j > 1)
+ out_dig('0' + predigit, &before);
+
+ while (nines)
+ {
+ out_dig('9', &before);
+ nines--;
+ }
+
+ predigit = q;
+ fflush(stdout);
+ }
+ }
+
+ out_dig(predigit + '0', &before);
+ puts("");
+ free(pi);
+
+ struct timeval after;
+ gettimeofday(&after, 0);
+ long unsigned int elapsed_ms = (after.tv_sec - before.tv_sec) * 1000 +
+ (after.tv_usec - before.tv_usec) / 1000;
+ unsigned int seconds_n = elapsed_ms / 1000;
+ unsigned int milliseconds_n = elapsed_ms % 1000;
+
+ printf("\nPi calculation to %d'th decimal point finished\n"
+ "\tTotal Time: %lu.%lu seconds\n", digits_n, seconds_n, milliseconds_n);
+}
+
+int main(int argc, char *argv[])
+{
+ if (argc < 2)
+ {
+ fprintf(stderr, "%s <number of decimal digits to compute>\n", argv[0]);
+ return 1;
+ }
+
+ if (!do_calc(argv))
+ printf("do_calc() failed to execute\n");
+
+ return 0;
+}
+
|