eule16

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?
--------------------

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct _digit {
    int base;
    char val;
    struct _digit *next;
} digit;


digit *create_digit(char *d)
{
    digit *head;
    digit *node, *pnode=NULL;
    int i;

    for (i=strlen(d)-1; i >= 0 ; i--) {
        node = malloc(sizeof(digit));
        node->val = d[i];
        node->next = NULL;

        if (pnode) {
            pnode->next = node;
            pnode = node;
        } else {
            pnode = node;
            head = node;
        }
    }

    return head;
}

digit *mul2(const digit *n)
{
    digit *result = NULL;
    const digit *pn = n;
    int carry = 0;
    digit *node, *pnode = NULL;

    for (; pn; pn = pn->next) {

        carry += (pn->val - '0') * 2;

        node = malloc(sizeof(digit));
        node->val = (carry%10) + '0';
        node->next = NULL;

        if (pnode) {
            pnode->next = node;
            pnode = node;
        } else {    /* first node */
            result = node;
            pnode = node;
        }

        carry /= 10;
    }

    while (carry) {
        node = malloc(sizeof(digit));
        node->val = (carry%10) + '0';
        node->next = NULL;

        pnode->next = node;
        pnode = node;

        carry /= 10;
    }


    return result;
}

void free_digit(digit *p)
{
    digit *node=p;

    while (node) {
        digit *next = node->next;
        free(node);
        node = next;
    }
}

/* invert output */
void output_digit(digit *head)
{
    digit *node = head;

    if (!head)
        return;

    output_digit(head->next);
    putchar(node->val);
}

#define N 1000
int main(int argc, const char *argv[])
{
    digit *p;
    digit *mul;
    int i;
    long long sum = 0;


    mul = create_digit("2");
    for (i = 1; i<N; i++) {
        p = mul;
        mul = mul2(mul);
        free_digit(p);
    }

    output_digit(mul);
    putchar('\n');

    p = mul;
    while(p) {
        sum += (p->val - '0');
        p = p->next;
    }

    printf("sum: %lld\n", sum);

    free(mul);
    return 0;
}

效率比bc要慢。计算2^100000, bc几乎是瞬时完成的，而这个程序消耗了2m22s。
在N>10000时，感觉明显,采用预分配而不是每次malloc()?
考虑如何实现任意精度的两个数相乘？