add a pi benchmark and a linked list example

2 files changed, 216 insertions, 0 deletions

diff --git a/linked_list.c b/linked_list.c
new file mode 100644
index 0000000..a9d3089
--- /dev/null
+++ b/linked_list.c
@@ -0,0 +1,47 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+struct Node
+{
+    int id;
+    struct Node *next;
+};
+typedef struct Node Node_t;
+
+Node_t *head = NULL;
+Node_t *tail = NULL;
+
+int main(void)
+{
+    int i;
+    for (i = 0; i < 10; i++)
+    {
+        if (head == NULL)
+        {
+            printf("head, adding id: %d\n", i);
+            head = (Node_t *) malloc(sizeof(Node_t));
+            head->id = i;
+            head->next = NULL;
+            tail = head;
+        }
+        else
+        {
+            printf("tail, adding id: %d\n", i);
+            Node_t *tmp = (Node_t *) malloc(sizeof(Node_t));
+            tmp->id = i;
+            tmp->next = NULL;
+            head->next = tmp;
+            head = head->next;
+        }
+    }
+
+    while (tail != NULL)
+    {
+        printf("tail: %d\n", tail->id);
+        tail = tail->next;
+    }
+
+    return 0;
+}
+
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;

+}

+