【算法】大数四则运算

最近在写大数四则运算的作业，发现网上有很多相关的算法，有3位作四则运算的，也有仿造计算机做移位运算的，当然，有仿照手工运算的算法。

最好的算法应该可以参考python的大数运算，不过本人还是自己实现仿手工运算的算法：好用、简单。

/*****************************************************************
 *
 *  Big number add/minus/multiply/divide
 *  Copyright: Free
 *  Author: Hou Hongwei
 *
 *
 ****************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void reverse(char *in,char *out,int len)
{
    int i,j;
    i = 0;
    j = len;

    while (i < len && j >= 0)
    {
        out[i++] = in[--j];
    }
    out[len] = '';
    //printf("reverse from %s to %sn",in,out);
}

void trim(char *inout,int *len)
{
    int i;
    i = (*len) - 1;
    while (inout[i] == '0')
    {
        if(i > 0) inout[i] = 0;
        i--;
    }
    
    (*len) = i + 1;

}

int is_bigger(char *x,char *y)
{
    int i,j;
    int xlen,ylen;

    xlen = strlen(x);
    ylen = strlen(y);

    //Remove '0' in bigger space
    trim(x,&xlen);
    trim(y,&ylen);

    if (xlen > ylen)
    {
        return 1;
    }

    if (xlen == ylen)
    {
        for (i = xlen -1; i >= 0; i--)
        {
            if(x[i] > y[i]) return 1;
            else if (x[i] < y[i]) return 0;
        }
    }

    return 0;
}
/**************************************
 *
 *  out len should bigger than
 *  x len and y len,and even
 *  1 more than the biggest
 *
 * ***********************************
 */
int add(char *x,char *y,char *out)
{
    int xlen,ylen,outlen;
    int i,j;
    
    xlen = strlen(x);
    ylen = strlen(y);
   
    j = (xlen > ylen ? ylen : xlen);
    for (i = 0; i < j; i++)
    {
        out[i] = (x[i] -'0') + (y[i] - '0');

    }

    j = (xlen > ylen ? xlen : ylen);
    for (; i < j; i++)
    {
        out[i] = ((xlen > ylen ? x[i] : y[i]) - '0');

    }

    out[j] = 0;
    for (i = 0; i < j; i++)
    {
        if (out[i] >= 10)
        {
            out[i+1] += 1;
            out[i] -= 10;
        }
        out[i] += '0';
    }

    if(out[i] > 0)  out[i] += '0';

    //printf("out: %sn",out);

}


/**************************************
 *
 *  This function assume that
 *  X is always bigger than Y
 *
 * ***********************************
 */
int _minus(char *x,j;
    int mark_ne;
    
    xlen = strlen(x);
    ylen = strlen(y);
    outlen = strlen(out);

    memset(out,outlen);
    //Check out len
    for (i = 0; i < ylen; i++)
    {
        out[i] = (x[i] -'0') - (y[i] - '0');

    }

    for (; i < xlen; i++)
    {
        out[i] = x[i] - '0';
    }

    for (i = 0; i < xlen - 1; i++)
    {
        if (out[i] < 0)
        {
            out[i+1] -= 1;
            out[i] += 10;
        }
        out[i] += '0';
    }

    if(out[i] > 0)
    {
        out[i] += '0';
    }
    else if (out[i] == 0)   //The biggest bit is 0
    {
        while (out[--i] == '0' && i >= 0)
        {
            out[i] = 0;
        }
        if(i == -1)
        {
            out[0] = '0';
        }
    }

}

int minus(char *x,char *out)
{
    int outlen,res;
    //Check if Y > X,if it is mark '-'
    if (is_bigger(y,x))
    {
        res = _minus(y,x,out);
        outlen = strlen(out);
        // Add flag '-'
        out[outlen] = '-';
        return res;
    }

    return _minus(x,y,out);
}

void multiply(char *x,j;
    
    xlen = strlen(x);
    ylen = strlen(y);

    for (i = 0; i < xlen; i++)
    {
        for (j = 0; j < ylen; j++)
        {
            out[i+j] += (x[i]-'0') * (y[j]-'0');
        }
    }

    for (i = 0; i < (xlen + ylen - 1); i++)
    {
        if (out[i] >= 10)
        {
            out[i+1] += out[i]/10;
            out[i] = out[i]%10;
        }
        out[i] += '0';
    }

    if(out[i] > 0)  out[i] += '0';
    
}

int divide(char *x,char *quotient,char *remainder)
{
    int xlen,ylen;
    int qlen,rlen;
    char *tmp_x,*tmp_out;
    int sum = 0;
    int i,j,k;

    xlen = strlen(x);
    ylen = strlen(y);

    // If Y > X,remainder is X and quotient is 0
    if (is_bigger(y,x))
    {
        quotient[0] = '0';
        strncpy(remainder,xlen);
        return 0;
    }

    //If X > Y
    //FIXME:
    qlen = xlen - ylen + 1;
    rlen = ylen;
    tmp_x = (char *)malloc(ylen + 1);
    tmp_out = (char *)malloc(ylen + 1);

    k = qlen - 1;

    strncpy(tmp_x,&x[xlen - ylen],ylen);
    memset(quotient,qlen);
    for (i = xlen -ylen; i >= 0; i--)
    {
        memset(tmp_out,'',strlen(tmp_out));
        strncpy(tmp_out,tmp_x,strlen(tmp_x));
        // tmp_x >= y
        if (!is_bigger(y,tmp_out))
        {
            do
            {
                memset(tmp_x,strlen(tmp_x));
                strncpy(tmp_x,tmp_out,strlen(tmp_out));
                memset(tmp_out,strlen(tmp_out));
                _minus(tmp_x,tmp_out);
                quotient[k] ++;
            }while(!is_bigger(y,tmp_out));  //tmp_out >= y
        }

        if(k > 0)
        {
            memset(tmp_x,strlen(tmp_x));
            tmp_x[0] = x[--k];
            //tmp_x = tmp_out << 1 + x[--k]
            strncat(tmp_x,(strlen(tmp_out) + 1));
        }
        else
        {
            strncpy(remainder,strlen(tmp_out));
            j = strlen(remainder);
            trim(remainder,&j);
            break;
        }
                
    }

    //Filter the 0
    k = qlen - 1;
    while (quotient[k] == 0) 
    {
        k--;
    }
    while (k >= 0)
    {
        quotient[k--] += '0';
    }

    free(tmp_x);
    free(tmp_out);
}

int main(int argc,const char *argv[])
{
    char in1[] = "60000000000000000000000000000000";
    char in2[] = "1234567890";
    char *x,*y,*out1,*out2;
    char *out3,*out4;
    int outlen;

    x = (char *)malloc(sizeof(in1));
    y = (char *)malloc(sizeof(in2));
    outlen = (sizeof(in1) > sizeof(in2) ? sizeof(in1) : sizeof(in2)) + 1;
    out1 = (char *)malloc(outlen);
    out2 = (char *)malloc(outlen);

    reverse(in1,strlen(in1));
    //printf("x: %sn",x);
    reverse(in2,strlen(in2));
    //printf("y: %sn",y);

    add(x,out1);
    //printf("out1: %sn",out1);
    reverse(out1,out2,strlen(out1));
    printf("%s + %s = %sn",in1,in2,out2);

    minus(x,out1);
    //printf("out1: %s,len: %dn",out1,strlen(out1));
    reverse(out1,strlen(out1));
    printf("%s - %s = %sn",out2);

    outlen = sizeof(in1) + sizeof(in2);

    out3 = (char *)malloc(outlen);
    out4 = (char *)malloc(outlen);
    multiply(x,out3);
    //printf("out3: %sn",out3);
    reverse(out3,out4,strlen(out3));
    printf("%s * %s = %sn",out4);

    memset(out1,strlen(out1));
    memset(out2,strlen(out2));
    memset(out3,strlen(out3));
    memset(out4,strlen(out4));
    divide(x,out2);
    reverse(out1,out3,strlen(out1));
    reverse(out2,strlen(out2));
    printf("%s / %s = %s mod %sn",out4);


    free(x);
    free(y);
    free(out1);
    free(out2);
    free(out3);
    free(out4);
    return 0;
}