mpMul  다배장 정수끼리의 곱셈

void mpMul(int *ret, int *a, int *b);

ret   (출력) 다배장 정수끼리의 곱셈의 결과(a * b)
a, b  (입력) 다배장 정수

없음

#define N 10000

void mpMul(int *ret, int *a, int *b)
{
    int  i, j;
    int  la, lb;
    int  *aa;
    int  ca = 1;
    long x;

    la = *a;
    lb = *b;

    for (i = la + lb; i > 0; i--) *(ret + i) = 0;

    for (j = 1; j <= lb; j++) {
        ca = 0;
        for (i = 1, aa = a; i <= la; i++) {
            x = *++aa;
            x = x * *++b + *(ret + i + j - 1) + ca;
            *(ret + i + j - 1) = x % N;
            ca = x / N;
        }
        *(ret + i + j - 1) = ca;
    }
    
    *ret = (ca ! = 0) ?  la + lb : la + lb - 1;
}

이 방법에서는, b의 n어를 각각 a의 m어에 걸므로, m*n회의 반복 된다. 따라서, 계산에 필요한 시간은 O(mn)이다.