21 July 2010

BigInteger using C

The following is a very simple implementation for the addition and subtraction of a Big Integer using C. Actually It was my solution for some problem in some compitions of ArabTeam2000 forums
note, I have compiled it under GCC (4.5)

//BigInteger.h

#ifndef BIG_INTEGER_H
#define BIG_INTEGER_H

typedef struct {
    char *data;
    size_t length;
    short sign; // 0 for positive (default value), otherwise for negative
} BigInteger;

// BigInteger interface functions

/**
* The char array are provided from right to left, for example if you want to reprensent the number 200, you
* should use array looks like:
* char arr[] = {0, 0, 2};
*/
BigInteger* construct(char[], size_t);
BigInteger* add(BigInteger*, BigInteger*);
BigInteger* subtract(BigInteger*, BigInteger*);
char* get(BigInteger*);
void print(BigInteger*);

// utility functions
static void intcpy(char*, char*, int);
static char** get_adjusted(BigInteger*, BigInteger*);


#endif



//BigInteger.c

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

#include "BigInteger.h"

BigInteger* construct(char data[], size_t length) {
    if (length > 40)
        return NULL;
    BigInteger* bi = malloc(sizeof(BigInteger*));
    bi->length = length;
    bi->data = malloc(bi->length*sizeof(char));
    intcpy(bi->data, data, bi->length);
    return bi;
}

BigInteger* add(BigInteger* x, BigInteger* y) {
    char* add_data(char*, char*, int*);
    
    int len = (x->length > y->length) ? x->length : y->length;
    
    char** resized = get_adjusted(x, y);
    char* tmp_x = resized[0];
    char* tmp_y = resized[1];
    
    char* ret = add_data(tmp_x, tmp_y, &len);
    if (ret == NULL)
        return NULL;
    
    BigInteger *b = construct(ret, len);
    
    return b;
}

BigInteger* subtract(BigInteger* x, BigInteger* y) {
    char** resized = get_adjusted(x, y);
    char *tmp_x = resized[0];
    char *tmp_y = resized[1];
    
    enum Sign {
        EQUAL = 0, POSITIVE = 1, NEGATIVE = 2
    };
    
    short ret_sign = EQUAL;
    
    int i;
    for (i = x->length - 1; i >= 0; i--) {
        if (tmp_x[i] == tmp_y[i])
            continue;
        else if (tmp_x[i] > tmp_y[i]) {
            ret_sign = POSITIVE;
            break;
        } else {
            ret_sign = NEGATIVE;
            break;
        }
        
    }
    // TODO: separate the following logic into its own utility function
    BigInteger* bi;
    if (ret_sign == EQUAL) {
        char ret[1] = {0};
        bi= construct(ret, 1);
    }else if (ret_sign == POSITIVE){
        char ret[x->length];
        for (i=0; i<x->length;i++){
            int tmp = tmp_x[i]-tmp_y[i];
            if (tmp <0){
                tmp_x[i+1]--;
                tmp = (tmp_x[i]+10)-tmp_y[i];
            }
            ret[i] = tmp;
        }
        bi=construct(ret, x->length);
    }else{
        char ret[y->length];
        for (i=0; i<y->length;i++){
            int tmp = tmp_y[i]-tmp_x[i];
            if (tmp <0){
                tmp_y[i+1]--;
                tmp = (tmp_y[i]+10)-tmp_x[i];
            }
            ret[i] = tmp;
        }
        bi=construct(ret, y->length);
        bi->sign = 1;
    }
    
    return bi;
}

char* get(BigInteger* bi) {
    return bi->data;
}

void print(BigInteger* bi) {
    char* d = bi->data;
    if (bi->sign) printf("%c", '-');
    int i;
    for (i = (bi->length)-1; i>=0; --i) {
        printf("%i", d[i]);
    }
    printf("\n");
}

char* add_data(char* x, char* y, int *len) {
    int i, reminder = 0;
    char *ret = malloc(sizeof(char) * *len);
    
    for (i = 0; i < *len; i++) {
        int tmp = x[i] + y[i] + reminder;
        ret[i] = tmp % 10;
        reminder = (tmp - ret[i]) / 10;
    }
    
    if (reminder) {
        if (i==40){
            fprintf(stderr, "Arithmetic OverFlown");
            return NULL;
        }else{
            ret[i] =reminder;
            (*len)++;
        }
    }
    return ret;
}

static void intcpy(char* dest, char* src, int l) {
    while (l-- > 0)
        *dest++ = *src++;
}

static char** get_adjusted(BigInteger* x, BigInteger *y) {
    char **ret = malloc(sizeof(char**));
    int len = (x->length > y->length) ? x->length : y->length;
    
    char *tmp_x = get(x);
    char *tmp_y = get(y);
    
    int diff;
    if ((diff = len - x->length) > 0) {
        intcpy(tmp_x, get(x), len);
        while (diff > 0) {
            tmp_x[x->length++] = 0;
            diff--;
        }
    } else if ((diff = len - y->length) > 0) {
        intcpy(tmp_y, get(y), len);
        while (diff > 0) {
            tmp_y[y->length++] = 0;
            diff--;
        }
    }
    ret[0] = tmp_x;
    ret[1] = tmp_y;
    return ret;
}



//main.c

#include <stdio.h>
#include "BigInteger.h"

void test_add1() {
    printf("Start Testing ADD n");
    char d1[] = { 1, 2};            // from right to left, so its value is 21
    char d2[] = { 5};                       // and this is 5
    
    BigInteger* bi1 = construct(d1, sizeof(d1) / sizeof(char));
    BigInteger* bi2 = construct(d2, sizeof(d2) / sizeof(char));
    print(bi1);
    print(bi2);
    BigInteger *ret = add(bi1, bi2);
    print(ret);
    printf("End Testing...n");
}
void test_add2() {
    printf("Start Testing ADD n");
    char d1[40];
    char d2[40];
    
    int i=0;
    for (i=0; i<40;i++){
        d1[i] = 3;
        d2[i] = 5;
    }
    
    BigInteger* bi1 = construct(d1, sizeof(d1) / sizeof(char));
    BigInteger* bi2 = construct(d2, sizeof(d2) / sizeof(char));
    print(bi1);
    print(bi2);
    BigInteger *ret = add(bi1, bi2);
    print(ret);
    printf("End Testing...n");
}

/**
* Will print "Arithmetic Overflow" and returns NULL
*/
void test_add3() {
    printf("Start Testing ADD n");
    char d1[40];
    char d2[40];
    
    int i=0;
    for (i=0; i<40;i++){
        d1[i] = 5;
        d2[i] = 5;
    }
    
    BigInteger* bi1 = construct(d1, sizeof(d1) / sizeof(char));
    BigInteger* bi2 = construct(d2, sizeof(d2) / sizeof(char));
    print(bi1);
    print(bi2);
    BigInteger *ret = add(bi1, bi2);
    if (ret == NULL)
        printf("NULLn");
    //print(ret);
    printf("End Testing...n");
}

void test_add4() {
    printf("Start Testing ADD n");
    char d1[] = { 9, 9};
    char d2[] = { 9, 9};
    
    BigInteger* bi1 = construct(d1, sizeof(d1) / sizeof(char));
    BigInteger* bi2 = construct(d2, sizeof(d2) / sizeof(char));
    print(bi1);
    print(bi2);
    BigInteger *ret = add(bi1, bi2);
    print(ret);
    printf("End Testing...n");
}

void test_add5() {
    printf("Start Testing ADD n");
    char d1[] = { 1, 2, 0, 0, 1, 2, 3, 4, 5, 9 ,3, 1, 3, 4, 4, 2, 1};               // from right to left, so its value is 21
    char d2[] = { 1, 3, 3, 4, 5, 5, 3, 0, 0, 0, 0, 0, 2, 1, 1, 1, 9};                       // and this is 5
    
    BigInteger* bi1 = construct(d1, sizeof(d1) / sizeof(char));
    BigInteger* bi2 = construct(d2, sizeof(d2) / sizeof(char));
    print(bi1);
    print(bi2);
    BigInteger *ret = add(bi1, bi2);
    print(ret);
    printf("End Testing...n");
}

void test_subtract1() {
    printf("Start Testing SUBTRACT n");
    char d1[] = { 1, 2};            // this is 21
    char d2[] = { 5, 2};            // and this is 25
    
    BigInteger* bi1 = construct(d1, sizeof(d1) / sizeof(char));
    BigInteger* bi2 = construct(d2, sizeof(d2) / sizeof(char));
    print(bi1);
    print(bi2);
    BigInteger *ret = subtract(bi1, bi2);
    print(ret);
    printf("End Testing...n");
}

void test_subtract2() {
    printf("Start Testing SUBTRACT n");
    
    char d1[] = { 9, 9};
    char d2[] = { 9, 9};
    
    BigInteger* bi1 = construct(d1, sizeof(d1) / sizeof(char));
    BigInteger* bi2 = construct(d2, sizeof(d2) / sizeof(char));
    print(bi1);
    print(bi2);
    BigInteger *ret = subtract(bi1, bi2);
    print(ret);
    printf("End Testing...n");
}

void test_subtract3() {
    printf("Start Testing SUBTRACT n");
    
    char d1[40];
    char d2[40];
    
    int i=0;
    for (i=0; i<40;i++){
        d1[i] = 3;
        d2[i] = 5;
    }
    
    BigInteger* bi1 = construct(d1, sizeof(d1) / sizeof(char));
    BigInteger* bi2 = construct(d2, sizeof(d2) / sizeof(char));
    print(bi1);
    print(bi2);
    BigInteger *ret = subtract(bi1, bi2);
    print(ret);
    printf("End Testing...n");
}

void test_subtract4() {
    printf("Start Testing SUBTRACT n");
    
    char d1[] = { 1, 2, 0, 0, 1, 2, 3, 4, 5, 9 ,3, 1, 3, 4, 4, 2, 1};               // from right to left, so its value is 21
    char d2[] = { 1, 3, 3, 4, 5, 5, 3, 0, 0, 0, 0, 0, 2, 1, 1, 1, 9};                       // and this is 5
    
    BigInteger* bi1 = construct(d1, sizeof(d1) / sizeof(char));
    BigInteger* bi2 = construct(d2, sizeof(d2) / sizeof(char));
    print(bi1);
    print(bi2);
    BigInteger *ret = subtract(bi1, bi2);
    print(ret);
    printf("End Testing...n");
}


int main(void) {
    test_add1();
    test_add2();
    test_add3();
    test_add4();
    test_add5();
    test_subtract1();
    test_subtract2();
    test_subtract3();
    test_subtract4();
    return 0;
}

How to compile the program:

1- copy the three above files to a new directory (say c_big_int)
ls -l
-rw-r--r-- 1 mhewedy mhewedy 4858 2011-04-05 22:41 main.c
-rw-r--r-- 1 mhewedy mhewedy 4440 2011-04-05 22:41 BigInteger.c
-rw-r--r-- 1 mhewedy mhewedy  712 2011-04-05 22:40 BigInteger.h

2- compile the BigInteger.c
cc -c BigInteger.c

3- make sure that the compilation process generated the object file:
ls -l
-rw-r--r-- 1 mhewedy mhewedy 3180 2011-04-05 22:48 BigInteger.o
-rw-r--r-- 1 mhewedy mhewedy 4858 2011-04-05 22:41 main.c
-rw-r--r-- 1 mhewedy mhewedy 4440 2011-04-05 22:41 BigInteger.c
-rw-r--r-- 1 mhewedy mhewedy  712 2011-04-05 22:40 BigInteger.h
4- Let's generate the binary file:
cc -o main main.c -L. BigInteger.o

5- Now you can run the program using the following command:
./main

**EDIT** The code has been reformatted, if it is no longer working please let me know in the comments
Posted by at
Labels: , , ,

2 comments:

Nehemiah said...

Seems your comments in test cases are wrong, all comments are saying 21 and 5 :)

September 6, 2011 at 8:03 AM
mhewedy said...

Yes... .)

Please Ignore comments in test cases

December 21, 2011 at 9:35 AM

Post a Comment

Subscribe to: Post Comments (Atom)