From 18d02b08d397b1b8f02c94fa11155fb696ec44dc Mon Sep 17 00:00:00 2001
From: Kyle K <kylek389@gmail.com>
Date: Fri, 1 Jul 2011 19:43:49 -0500
Subject: add a pi benchmark and a linked list example

---
 pi_bbp.c | 169 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 169 insertions(+)
 create mode 100644 pi_bbp.c

(limited to 'pi_bbp.c')

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;
+}
+
-- 
cgit v1.2.3