C++大整数运算(三):乘法

C++大整数运算系列文章讲述了实现大整数四则运算的基本思路和方法,对算法做简单的介绍并采用C++代码做进一步说明。本文并不试图写成一篇教程,而是对实现过程进行整理和概括。实现过程中学习了 Donald E. Knuth 著作的 The Art of Computer Programming 中的相关内容,特此致敬。

本文是C++大整数运算系列文章的第三篇,主要介绍如何实现大整数运算的乘法运算。

目录

完成了加减运算,我们对数据存储的方式有了进一步的理解,否则就难以理解乘法的运算方法。

要完成乘法运算,我们能想到的最朴素的方法就是手工乘法,将某个因数的每个数位与另一个因数相乘,相乘的结果移位后相加得到最终结果。为了更清晰地表述,先介绍一个数位乘因数的方法。

vector<unsigned> multi_one(vector<unsigned> x, unsigned y)
{
    unsigned long long r = 0;
    vector<unsigned> z(x.size());
    for(size_t i = 0; i < x.size(); ++i) // >
    {
        r   += unsigned long long(y) * x[i];
        z[i] = unsigned(r);
        r  >>= 32;
    }
    if(r) z.push_back(r);
    return std::move(z);
}

有了一位数乘法,两个大数之间的乘法也就很好实现了,可以先算一位乘法,再将结果相加。这里将乘法过程和加法过程结合在一起,节省了一部分时间和空间。

vector<unsigned> multi(vector<unsigned> x, vector<unsigned> y)
{
    unsigned long long r;
    size_t lenx = x.size(), leny = y.size();
    vector<unsigned> result(lenx + leny, 0); // 预先分配空间
    for(size_t i = 0; i < leny; ++i)
    {
        r = 0;
        size_t j, k;                         // k为移位的个数
        for(j = 0, k = i; j < lenx; ++j, ++k) // > 20171211修正,"k = 0"应为"k = i"
        {
            r        += unsigned long long(y[i]) * x[j] + result[k];
            result[k] = unsigned(r);
            r       >>= 32;
        }
        result[k] = unsigned(r);
    }
    return std::move(result);
}

这样,模拟手工乘法的操作基本完成了,由于预先分配了空间,可能result中会有一个前导零需要处理。朴素乘法的时间复杂度为O(lenx * leny),对于手工计算来说这已经很简洁了,但对计算机来说,还有更快的方法。

分治法

使用分治的方法计算大整数的乘法的原理是这样的:首先假设两个因数的长度都是n,基数设为base,则两个因数都可以表示成
\(x = x_1 \times base^{n/2} + x_2\)
的形式,其中x1、x2分别为x的高n-n/2位和低n/2位。令 m=base^(n/2),则
\(
x \times y = (x_1 \times m + x_2) \times (y_1 \times m + y_2) \\
= x_1 \times y_1 \times m^2 + (x_1 \times y_2 + x_2 \times y_1) \times m + x_2 \times y_2 \\
= x_1 \times y_1 \times m^2 + ((x_1+x_2) \times (y_1+y_2)-x_1 \times y_1 – x_2 \times y_2) \times m + x_2 \times y_2
\)
其中m是基数的幂次,乘m可以通过移位操作实现,上述最后一步变换将乘法的操作次数从4次降低到了3次,算法的时间复杂度就从O(n^2)降到了O(n^1.59),具体计算过程略去。

采用分治的方法计算乘法有较低的时间复杂度,但其引入的分割高低位以及多出的加法和减法操作也会花费一部分时间和空间,因此当因数很小的时候,采用朴素乘法可能有更快的速度。在这里可以采用实验的方法,找到一个阈值K,当n小于K的时候采用朴素乘法,当n大于K的时候采用分治乘法。经过验证,这种方法在实践中有较好的效果。

本文讲述了大整数乘法中的朴素乘法和分治方法,为了简洁而忽略了一些细节,且限于篇幅没有给出分治乘法的详细代码,有需要的读者请到这里查看完整的代码。下一节将介绍大整数除法的相关内容。

发表评论

电子邮件地址不会被公开。 必填项已用*标注