Grade School

c언어로 grade school algorithm 구현

Grade School 알고리즘이란?

흔히 하는 직접 곱셈이다.
단점 : 계산 시간이 많이 느리다.

구현

char 형 포인터(숫자 1, 숫자 2)를 받아 곱하고, char형 포인터를 return한다.

char * grade_school(char * num1, char * num2)
{
    int len1 = strlen(num1);
    int len2 = strlen(num2);
    int plus;
    int total = len1+len2;
    int ans[total];
    char * ans_ret = (char *)calloc(total+1, sizeof(char));
    int i, j, k=0;
    for(i=0; i<total; i++)
    {
        ans[i]=0;
    }
    // do down digit first
    for(j=len2; j>0; j--)
    {
        // plus = upgrade forward digit
        plus = 0;
        for(i=len1; i>0; i--)
        {
            // ans = multiply + upgrade digit
            ans[i+j-1] += (num1[i-1]-'0')*(num2[j-1]-'0') + plus;
            // next generation upgrade digit = now ans/10
            plus = ans[i+j-1]/10;
            // after making plus, ans % 10
            ans[i+j-1] = ans[i+j-1]%10;     
        }
        // after doing all calculation for one j, set most left side digit 
        ans[j-1] = plus;
    }
    while(i<total)
    {
        // ex. 00123, we should remove 0
        if(ans[i]!=0)
        {
            break;
        }
        i++;
    }
    // k : setting i to make new string
    k=i;
    while(i<total)
    {
        // cause ans_ret needs to start from 0 point
        ans_ret[i-k] = ans[i]+'0';
        i++;
    }
    // return string
    return ans_ret;
}