/*
 * 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;
}