diff options
-rw-r--r-- | Makefile | 7 | ||||
-rw-r--r-- | pi_bbp.c | 340 |
2 files changed, 175 insertions, 172 deletions
@@ -1,11 +1,12 @@ BINS = ascii class depipe_strings dup fpipe pipe realloc strpbrk strsep \ - tokenizer getopt prime_mask + tokenizer getopt prime_mask linked_list pi_bbp CC = gcc +CFLAGS = -Wall -std=gnu99 -pedantic DBGFLAGS = -g -O0 ifdef DEBUG - CFLAGS = $(DBGFLAGS) -D DEBUG -std=gnu99 -Wall -pedantic + CFLAGS += $(DBGFLAGS) -D DEBUG else - CFLAGS = -O2 -std=gnu99 -Wall -pedantic + CFLAGS += -O2 -mtune=native -march=native endif LDFLAGS = -lm @@ -1,169 +1,171 @@ -/*
- * 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;
-}
-
+/* + * 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: %u.%u seconds\n", seconds_n, milliseconds_n); +} + +int do_calc(char **argv) +{ + long unsigned int i, j, 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 -1; + + 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 %lu'th decimal point finished\n" + "\tTotal Time: %u.%u seconds\n", digits_n, seconds_n, milliseconds_n); + + return 1; +} + +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; +} + |