Revisions to Super calculator in C - Code Review Stack Exchange

Bounty Awarded with 50 reputation awarded by machine_1

occurred Jan 31, 2017 at 14:55

added 364 characters in body

Source Link

edited Jan 28, 2017 at 9:10

32.3k
15
79
205

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

If I count creation and freeing the big integers, your program is faster by the factor of 2. HoweverNow, when I measured onlyrun my demo program (see the addition operationsGist above) with -O3 optimization flag, I got following figures:get something like

time elapsed: 21.34501515, total time: 1.4847
coderodde time: 0.27092157, total time: 1.2360

Note I have updated the code once again in the linked gist. Make sure you are up-to-date.

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_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;
}

If I count creation and freeing the big integers, your program is faster by the factor of 2. However, when I measured only the addition operations, I got following figures:

time elapsed: 2.3450
coderodde time: 0.2709

Note I have updated the code in the linked gist. Make sure you are up-to-date.

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

Now, when I run my demo program (see the Gist above) with -O3 optimization flag, I get something like

time elapsed: 1.1515, total time: 1.4847
coderodde time: 0.2157, total time: 1.2360

Note I have updated the code once again in the linked gist. Make sure you are up-to-date.

added 695 characters in body

Source Link

edited Jan 27, 2017 at 17:51

coderodde

32.3k
15
79
205

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 =
      uint64_t* data (uint64_t*)= 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 = (big_integer*) 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 end;start_index = (int) big_int->data_length - 1;
    
    if (big_int->data[0]>data[start_index] == 0)
    {
        end--start_index;
 = 0;
    }  
    else    if (start_index >= 0)
        {
        end =   fprintf(file, "%llu", big_int-1;>data[start_index]);
        }
        
        for (int i = big_int->data_lengthstart_index - 1; i >>= end;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_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 = (uint64_t*) calloc(data_length, sizeof(uint64_t));
    
    intsize_t end_index = MIN(a_length, b_length);
    int index = 0;
    booluint64_t carry = false;0;
    big_integer* result = malloc(sizeof *result);
    
    while (index != end_index)
    {
        uint64_t tmp = a->data[index] + b->data[index] + (carry ? 1 : 0);carry;
        
        if (tmp >>= MODULO)
        {
            carry = true;1;
            data[index] = tmp % MODULO;
        }
        else
        {
            carry = false;0;
            data[index] = tmp;
        }
        
        ++index;
    }
    
    ifwhile (index < a_length)
    {
        uint64_t tmp = a->data[index] + carry;
        
        if (carrytmp >= MODULO)
        {
            data[index++]++;carry = 1;
        }
    data[index++] = tmp % MODULO;
        while}
 (index != a_length)     else
        {
            data[index]carry = a->data[index];0;
            index++;data[index++] = tmp;
        }
    }
    else 
 if   while (index < b_length)
    {
        uint64_t tmp = b->data[index] + carry;
        
        if (carrytmp >= MODULO)
        {
            data[index++]++;carry = 1;
        }
    data[index++] = tmp % MODULO;
        while}
 (index != b_length)     else
        {
            data[index]carry = b->data[index];0;
            index++;data[index++] = tmp;
        }
    }
    
    big_integer*if ret(carry => (big_integer*0) malloc(sizeof{
 *ret);       data[data_length - 1] = 1;
    ret}
    
    result->data = data;
    retresult->data_length = data_length;
    return ret;result;
}

Hope that helps.

Note I have updated the code in the linked gist. Make sure you are up-to-date.

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 =
        (uint64_t*) 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 = (big_integer*) 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 end;
    
    if (big_int->data[0] == 0)
    {
        end = 0;
    }
    else
    {
        end = -1;
    }
    
    for (int i = big_int->data_length - 1; i > end; --i) {
        fprintf(file, "%llu", big_int->data[i]);
    }
}

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 = (uint64_t*) calloc(data_length, sizeof(uint64_t));
    
    int end_index = MIN(a_length, b_length);
    int index = 0;
    bool carry = false;
    
    while (index != end_index)
    {
        uint64_t tmp = a->data[index] + b->data[index] + (carry ? 1 : 0);
        
        if (tmp > MODULO)
        {
            carry = true;
            data[index] = tmp % MODULO;
        }
        else
        {
            carry = false;
            data[index] = tmp;
        }
        
        ++index;
    }
    
    if (index < a_length)
    {
        if (carry)
        {
            data[index++]++;
        }
        
        while (index != a_length)
        {
            data[index] = a->data[index];
            index++;
        }
    }
    else if (index < b_length)
    {
        if (carry)
        {
            data[index++]++;
        }
        
        while (index != b_length)
        {
            data[index] = b->data[index];
            index++;
        }
    }
    
    big_integer* ret = (big_integer*) malloc(sizeof *ret);
    ret->data = data;
    ret->data_length = data_length;
    return ret;
}

Hope that helps.

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_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;
}

Hope that helps.

Note I have updated the code in the linked gist. Make sure you are up-to-date.

Post Undeleted by coderodde

occurred Jan 27, 2017 at 17:50

Post Deleted by coderodde

occurred Jan 27, 2017 at 16:21

Source Link

answered Jan 27, 2017 at 15:02

coderodde

32.3k
15
79
205

You can pack 18 digits into a uint64_t. If you do it right, you will obtain a substantial speed-up for your addition operation:

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 =
        (uint64_t*) 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 = (big_integer*) 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 end;
    
    if (big_int->data[0] == 0)
    {
        end = 0;
    }
    else
    {
        end = -1;
    }
    
    for (int i = big_int->data_length - 1; i > end; --i) {
        fprintf(file, "%llu", big_int->data[i]);
    }
}

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 = (uint64_t*) calloc(data_length, sizeof(uint64_t));
    
    int end_index = MIN(a_length, b_length);
    int index = 0;
    bool carry = false;
    
    while (index != end_index)
    {
        uint64_t tmp = a->data[index] + b->data[index] + (carry ? 1 : 0);
        
        if (tmp > MODULO)
        {
            carry = true;
            data[index] = tmp % MODULO;
        }
        else
        {
            carry = false;
            data[index] = tmp;
        }
        
        ++index;
    }
    
    if (index < a_length)
    {
        if (carry)
        {
            data[index++]++;
        }
        
        while (index != a_length)
        {
            data[index] = a->data[index];
            index++;
        }
    }
    else if (index < b_length)
    {
        if (carry)
        {
            data[index++]++;
        }
        
        while (index != b_length)
        {
            data[index] = b->data[index];
            index++;
        }
    }
    
    big_integer* ret = (big_integer*) malloc(sizeof *ret);
    ret->data = data;
    ret->data_length = data_length;
    return ret;
}

(The entire demonstration program here.)

If I count creation and freeing the big integers, your program is faster by the factor of 2. However, when I measured only the addition operations, I got following figures:

time elapsed: 2.3450
coderodde time: 0.2709

Hope that helps.

Stack Exchange Network

Return to Answer