big_calculate.c

//
//  main.c
//  c_review
//
//  Created by liudanking on 4/25/14.
//  Copyright (c) 2014 liudanking. All rights reserved.
//

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

char *base_add(const char *a, const char *b);
char *base_minus(const char *a, const char *b);
char *big_add(const char *a, const char *b);
char *big_minus(const char *a, const char *b);
char *big_multiply(const char *a, const char *b);
void align_big(const char *a, char *out);



int main(void)
{
    char *ret, *ret2;
    char a[100], b[100], c[100], d[100];

    
    strcpy(a, "99");
    strcpy(b, "1001");
    
    //printf("%d, %s, %02x; %d, %s, %02x\n", sizeof(a)/sizeof(a[0]),a, a, sizeof(b)/sizeof(b[0]),b,b);

    
    
    ret = big_add(a, b);
    printf("%s\n", ret);
    if (ret)
        free(ret);

    strcpy(c, "99");
    strcpy(d, "1001");
    ret2 = big_minus(c, d);
    printf("%s\n", ret2);
    if (ret2)
        free(ret2);

//    ret = big_multiply(a, b);
//    printf("%s\n", ret);
//    if (ret)
//        free(ret);
//    printf("fuck you\n");
    return 0;
}

void align_big(const char *a, char *out)
{
    int i;
    for (i=0; i < strlen(a); i++)
    {
        if (a[i] != '0')
        {
            if (a[i] != '\0')
            {
                strcpy(out+99-strlen(a+i), a+i);
            }
            else
            {
                strcpy(out+98, "0");
            }
            break;
        }
    }
}

char *base_add(const char *a, const char *b)
{
    char _a[100], _b[100];
    char *ret, *ret_align;
    int i, carry, sum_one;
    
    ret = (char*)malloc(101);
    if (ret == NULL)
    {
        printf("malloc failed");
    }
    memset(_a, '0', sizeof(_a));
    memset(_b, '0', sizeof(_b));
    memset(ret, '0', 101);
    ret[100] = '\0';
    
    // align a and b
    align_big(a, _a);
    align_big(b, _b);
    
    carry = 0;
    for (i=98; i>=0; i--)
    {
        
        sum_one = _a[i] - '0' + _b[i] - '0' + carry;
        carry = sum_one/10;
        sum_one = sum_one % 10;
        *(ret+i+1) = sum_one + '0';
    }
    
    for (i=0; i< 100; i++)
    {
        if (ret[i] != '0')
        {
            ret_align = (char*)malloc(120-i);
            if (ret[i] != '\0')
                strcpy(ret_align, ret+i);
            else
                strcpy(ret_align, "0");
            free(ret);
            break;
        }
    }
    
    return ret_align;
}

char *base_minus(const char *a, const char *b)
{
    char _a[100], _b[100];
    char *ret, *ret_align;
    int i, borrow, tmp;
    
    memset(_a, '0', sizeof(_a));
    memset(_b, '0', sizeof(_b));
    ret = (char*)malloc(100);
    memset(ret, '0', 100);
    ret[99] = '\0';
    
    // align a and b
    strcpy(_a+(99-strlen(a)), a);
    strcpy(_b+(99-strlen(b)), b);
    
    borrow = 0;
    for (i=98; i>=0; i--)
    {
        tmp = _a[i] - _b[i] - borrow;
        if (tmp >= 0)
        {
            ret[i] = tmp + '0';
            borrow = 0;
        }
        else
        {
            ret[i] = tmp + 10 + '0';
            borrow = 1;
        }
    }
    
    for (i=0; i< 100; i++)
    {
        if (ret[i] != '0')
        {
            ret_align = (char*)malloc(100-i);
            if (ret[i] != '\0')
                strcpy(ret_align, ret+i);
            else
                strcpy(ret_align, "0");
            free(ret);
            break;
        }
    }
    
    return ret_align;
    
}


char *big_add(const char *a, const char *b)
{
    char *ret, *p, *tp;
    char _a[100], _b[100];
    
    memset(_a, '0', sizeof(_a));
    memset(_b, '0', sizeof(_b));
    
    
    if (a[0] != '-' && b[0] != '-')
    {
        printf("%s+%s\n", a,b);
        return base_add(a, b);
    }
    printf("%d:%d:%d\n", a[0]!='-', b[0]=='-', a[0]!='-' && b[0]=='-');
    if (a[0]!='-' && b[0]=='-')
    {
        // align a and b
        printf("%d\n", strlen(a));
        strcpy(_a+99-strlen(a), a);
        strcpy(_b+(99-strlen(b)+1), b+1);
        if (strcmp(_a, _b) >= 0)
        {
            return base_minus(_a, _b);
        }
        else
        {
            p = base_minus(_b, _a);
            ret = (char*)malloc(102);
            ret[0] = '-';
            strcpy(ret+1, p);
            free(p);
            return ret;
        }
    }
    if (a[0] == '-' && b[0] != '-')
    {
        // align a and b
        strcpy(_a+(99-strlen(a)+1), a+1);
        strcpy(_b+(99-strlen(b)), b);
        if (strcmp(_a, _b) > 0)
        {
            p = base_minus(_a, _b);
            ret = (char*)malloc(102);
            ret[0] = '-';
            strcpy(ret+1, p);
            free(p);
            return ret;
        }
        else
        {
            return base_minus(_b, _a);
        }
        
    }
    if (a[0] == '-' && b[0] == '-')
    {
        p = base_add(a+1, b+1);
        ret = (char*)malloc(102);
        ret[0] = '-';
        strcpy(ret+1, p);
        free(p);
        return ret;
    }
    
    // return result
    return ret;
}

char *big_minus(const char *a, const char *b)
{
    char _b[100];
    
    memset(_b, '0', sizeof(_b));
    
    if (b[0] == '-')
    {
        return big_add(a, b+1);
    }
    else
    {
        _b[0] = '-';
        strcpy(_b+1, b);
        return big_add(a, _b);
    }
    
    return NULL;
}

char *big_multiply(const char *a, const char *b)
{
    char *ret, *p, *mid_ret;
    char _a[100], _b[100];
    int i, j, carry, sign, tmp;
    

    ret = (char*)malloc(202);
    p = (char*)malloc(202);
    memset(_a, '0', sizeof(_a));
    memset(_b, '0', sizeof(_b));
    memset(ret, '0', 202);
    ret[201]='\0';
    
    sign = 0;
    if (a[0] == '-')
    {
        sign++;
        strcpy(_a+99-strlen(a)+1, a+1);
    }
    else
    {
        strcpy(_a+99-strlen(a), a);
    }
    if (b[0] == '-')
    {
        sign++;
        strcpy(_b+99-strlen(b)+1, b+1);
    }
    else
    {
        strcpy(_b+99-strlen(b), b);
    }
    
    carry = 0;
    for (i=98; i>=0; i--)
    {
        memset(p, '0', 202);
        p[201]='\0';
        for (j=98; j>=0; j--)
        {
            tmp = (_b[i] - '0') * (_a[j] - '0') + carry;
            carry = tmp / 10;
            *(p+200+i-98 + j - 98) = tmp % 10 + '0';
        }
        mid_ret = big_add(ret, p);
        strcpy(ret, mid_ret);
        free(mid_ret);
    }
    
    free(p);
    return ret;
}