big_int_add.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdint.h>
#include <stdbool.h>

#define MAX(A, B) (((A) > (B))? (A) : (B))
#define MIN(A, B) (((A) < (B))? (A) : (B))

char *add(char *x, char *y);

typedef struct big_integer {
    uint64_t* data;
    size_t data_length;
} big_integer;

static size_t DIGITS_PER_UINT64 = 18;
static uint64_t MODULO = 1000000000000000000L;

big_integer* big_integer_create(const char* number_text)
{
    size_t integer_text_length = strlen(number_text);
    size_t data_length = integer_text_length / DIGITS_PER_UINT64 +
                        (integer_text_length % DIGITS_PER_UINT64 != 0 ? 1 : 0);
    
    uint64_t* data = calloc(data_length, sizeof(uint64_t));
    
    size_t chars_loaded = 0;
    size_t data_index = 0;
    uint64_t sum = 0;
    uint64_t factor = 1;
    
    for (int i = integer_text_length - 1; i >= 0; --i)
    {
        const char character = number_text[i];
        
        sum += factor * (character - '0');
        factor *= 10;
        
        if (++chars_loaded % DIGITS_PER_UINT64 == 0)
        {
            data[data_index++] = sum;
            sum = 0;
            factor = 1;
        }
    }
    
    if (chars_loaded % DIGITS_PER_UINT64 != 0)
    {
        data[data_index] = sum;
    }
    
    big_integer* result = malloc(sizeof *result);
    result->data = data;
    result->data_length = data_length;
    return result;
}

void big_integer_free(big_integer* big_int)
{
    free(big_int->data);
    free(big_int);
}

void big_integer_print(big_integer* big_int, FILE* file)
{
    int start_index = (int) big_int->data_length - 1;
    
    if (big_int->data[start_index] == 0)
    {
        --start_index;
        
        if (start_index >= 0)
        {
            fprintf(file, "%llu", big_int->data[start_index]);
        }
        
        for (int i = start_index - 1; i >= 0; --i)
        {
            fprintf(file, "%018llu", big_int->data[i]);
        }
    }
    else
    {
        fprintf(file, "%llu", big_int->data[start_index--]);
        
        for (int i = start_index; i >= 0; --i)
        {
            fprintf(file, "%018llu", big_int->data[i]);
        }
    }
}

big_integer* big_integer_copy(big_integer* big_int)
{
    big_integer* ret = malloc(sizeof *ret);
    uint64_t* data = malloc(big_int->data_length * sizeof(uint64_t));
    ret->data_length = big_int->data_length;
    ret->data = data;
    memcpy(data, big_int->data, big_int->data_length * sizeof(uint64_t));
    return ret;
}

big_integer* big_integer_add(big_integer* a, big_integer* b)
{
    size_t a_length = a->data_length;
    size_t b_length = b->data_length;
    size_t data_length = MAX(a_length, b_length) + 1;
    uint64_t* data = calloc(data_length, sizeof(uint64_t));
    
    size_t end_index = MIN(a_length, b_length);
    int index = 0;
    uint64_t carry = 0;
    big_integer* result = malloc(sizeof *result);
    
    while (index != end_index)
    {
        uint64_t tmp = a->data[index] + b->data[index] + carry;
        
        if (tmp >= MODULO)
        {
            carry = 1;
            data[index] = tmp % MODULO;
        }
        else
        {
            carry = 0;
            data[index] = tmp;
        }
        
        ++index;
    }
    
    while (index < a_length)
    {
        uint64_t tmp = a->data[index] + carry;
        
        if (tmp >= MODULO)
        {
            carry = 1;
            data[index++] = tmp % MODULO;
        }
        else
        {
            carry = 0;
            data[index++] = tmp;
        }
    }
    
    while (index < b_length)
    {
        uint64_t tmp = b->data[index] + carry;
        
        if (tmp >= MODULO)
        {
            carry = 1;
            data[index++] = tmp % MODULO;
        }
        else
        {
            carry = 0;
            data[index++] = tmp;
        }
    }
    
    if (carry > 0) {
        data[data_length - 1] = 1;
    }
    
    result->data = data;
    result->data_length = data_length;
    return result;
}

int main(void)
{
    /*
    big_integer* a = big_integer_create("999999999999999999999");
    big_integer* b = big_integer_create("5");
    big_integer* r = big_integer_add(a, b);
    big_integer_print(r, stdout);
    puts("");
    exit(0);*/
    
    size_t nd = 200 * 1000 * 1000; // 2 hundred million digits
    clock_t ta = clock();
    char *x = (char *)malloc(nd + 1);
    char *y = (char *)malloc(nd + 1);
    
    if (!x || !y) {
        fputs("error: memory allocation failed.\n", stderr);
        if (x) free(x);
        if (y) free(y);
        return 1;
    }
    
    /* assign x and y */
    for (size_t i = 0; i < nd; i++) {
        x[i] = '9';
        y[i] = '9';
    }
    /* NUL-terminate the arrays */
    x[nd] = '\0';
    y[nd] = '\0';
    /* add x and y */
    
    /**********************************
     * JUST MEASURE THE ADD OPERATION! *
     **********************************/
    clock_t t1 = clock();
    char *z = add(x, y);
    clock_t t2 = clock();
    
    if (z) {
        //printf("x + y = %s\n", z);
        free(z);
    }
    
    if (x) free(x);
    if (y) free(y);
    
    clock_t tb = clock();
    
    fprintf(stdout, "time elapsed: %.4f, total time: %.4f\n",
            (double)(t2 - t1) / CLOCKS_PER_SEC,
            (double)(tb - ta) / CLOCKS_PER_SEC);
    
    ta = clock();
    
    x = (char *) malloc(nd + 1);
    y = (char *) malloc(nd + 1);
    
    for (size_t i = 0; i < nd; ++i)
    {
        x[i] = y[i] = '9';
    }
    
    x[nd] = y[nd] = '\0';
    
    big_integer* bi_a = big_integer_create(x);
    big_integer* bi_b = big_integer_copy(bi_a);
    
    /**********************************
     * JUST MEASURE THE ADD OPERATION! *
     **********************************/
    t1 = clock();
    big_integer* result = big_integer_add(bi_a, bi_b);
    t2 = clock();
    
    big_integer_free(bi_a);
    big_integer_free(bi_b);
    big_integer_free(result);
    
    tb = clock();
    
    fprintf(stdout,
            "coderodde time: %.4f, total time: %.4f\n",
            (double)(t2 - t1) / CLOCKS_PER_SEC,
            (double)(tb - ta) / CLOCKS_PER_SEC);
    return 0;
}

void ReverseArray(char *buf)
{
    char tmp, *ptr = buf + strlen(buf) - 1;
    while (buf < ptr) {
        tmp = *buf;
        *buf++ = *ptr;
        *ptr-- = tmp;
    }
}

char *add(char *x, char *y)
{
    /* store number of digits in size_t variables*/
    size_t xlen = strlen(x);
    size_t ylen = strlen(y);
    /* essential variables */
    char *z = NULL;
    int r = -1;
    int val, var = (xlen >= ylen);
    size_t n = 0;
    /* pointers to x and y */
    char *p1, *p2;
    char *t1, *t2;
    /* assign pointers according to the value of var */
    if (var) {
        p1 = x + xlen - 1;  t1 = x;
        p2 = y + ylen - 1;  t2 = y;
        z = (char *)malloc(xlen + 2);
    }
    else {
        p1 = y + ylen - 1;  t1 = y;
        p2 = x + xlen - 1;  t2 = x;
        z = (char *)malloc(ylen + 2);
    }
    /* check for allocation failure */
    if (!z) {
        fputs("error: memory allocation failed.\n", stderr);
        return NULL;
    }
    /* stage 1 */
    while (p2 >= t2)
    {
        if (r == -1) {
            val = (*p1-- - '0') + (*p2-- - '0');
        }
        else {
            val = (*p1-- - '0') + (*p2-- - '0') + 1;
        }
        if (val > 9) {
            r = val - 10;
            z[n++] = r + '0';
        }
        else {
            z[n++] = val + '0';
            r = -1;
        }
    }
    /* stage 2 */
    while (p1 >= t1)
    {
        if (r == -1) {
            z[n++] = *p1--;
        }
        else {
            val = (*p1-- - '0') + 1;
            if (val > 9) {
                r = val - 10;
                z[n++] = r + '0';
            }
            else {
                z[n++] = val + '0';
                r = -1;
            }
        }
    }
    /* stage 3 */
    if (r != -1) {
        z[n++] = 1 + '0';
    }
    z[n] = '\0';
    ReverseArray(z);
    return z;
}