大数乗算問題(C++版)

最近1つの筆記試験に参加して、大きい数の乗算の問題に出会って、これは1つの経典のアルゴリズムの問題です.大数乗算問題とは、2つの整数を入力し、この2つの数の積を出力することを要求することである.入力された数字は、コンピュータ内の任意のデータの格納範囲を超える可能性があります.ここで主に注意しなければならない点は、文字列または文字配列を使用して、この2つの大きな数とその結果を格納する必要があり、乗算計算中に乗算ビットと加算ビットが存在することです.
私はまず自分で答えを書いてみました.考えは手書き縦乗算をシミュレートすることです.

static string MYMULTIPLY(const string &number1, const string &number2)
{
    int length1 = number1.size();
    int length2 = number2.size();
    string result = "";

    if (length1 == 0 || length2 == 0)
    {
        result = "error";
        return result;
    }

    int *iresult;
    iresult = (int*)malloc(sizeof(int) * (length1 + length2 + 1));
    memset(iresult, 0, sizeof(int) * (length1 + length2 + 1));

    for(int i = length1 - 1, x = 0; i >= 0; i--, x++)
    {
        int numA = number1[i] - 48;
        int value1 = 0;
        int value2 = 0;
        int multiFlag = 0;//     
        int addFlag = 0;//     

        for(int j = length2 - 1, y = 0; j >= 0; j--, y++)
        {
            int numB = number2[j] - 48;
            value1 = numA * numB + multiFlag;
            multiFlag = value1 / 10;
            value1 = value1 % 10;
            value2 = (iresult[x+y]) + value1 + addFlag;
            addFlag = value2 / 10;
            iresult[x+y] = (value2 % 10); 
        }
        iresult[x + length2] += (multiFlag + addFlag);
    }

    //  
    int i = 0;
    for(i = length1 + length2 - 1; i >= 0; i--)
    {
        if(iresult[i] != 0)
            break;
    }

    for(; i >= 0; i--)
    {
        result = result + (char)(iresult[i]+48);
    }

    free(iresult);

    return result;
}

この方法は結果を出すことができるが,特に各人が乗算した結果とキャリーのコードを計算するのは見苦しい.その後、私はこのコードを改善して、各ビット間の乗算とキャリー計算を分けました.

static string MULTIPLY(string number1, string number2)
{
    int i, j;
    int *iresult;
    int length1 = number1.size();
    int length2 = number2.size();
    string result = "";

    reverse(number1.begin(), number1.end());
    reverse(number2.begin(), number2.end());

    if (length1 == 0 || length2 == 0)
    {
        result = "error";
        return result;
    }

    iresult = (int*)malloc(sizeof(int) * (length1 + length2 + 1));
    memset(iresult, 0, sizeof(int) * (length1 + length2 + 1));

        //     
    for(i = 0; i < length1; i++)
    {
        for(j = 0; j < length2; j++)
        {
            iresult[i+j] += ((number1[i] - 48) * (number2[j] - 48));
        }
    }

        //    
    int carry = 0;
    for(i = 0; i < length1 + length2; i++)
    {
        int value = iresult[i] + carry;
        iresult[i] = value % 10;
        carry = value / 10;
    }

    for(i = length1 + length2 - 1; i >= 0; i--)
    {
        if(iresult[i] != 0)
        break;
    }

    for(; i >= 0; i--)
    {
        result = result + (char)(iresult[i]+48);
    }

    free(iresult);

    if(result == "") result = "0";
    return result;
}

もちろんこの問題には分治乗算、高速フーリエなどのアルゴリズムがありますが、これは筆記試験や面接で速く書けるものではありません.興味があれば、皆さんは引き続き深く理解することができます.