大整数乘法问题

算法设计思想：

(1) 大整数的存储

我们知道，在编译系统中，整型数据类型的最大存储空间为8字节，也就是最大能存储232的数据。即使使用双精度浮点数据类型（double），也只能存储最大1.798×10308的数据。如果需要计算10200数量级的整数的乘法，利用的现有的数据类型就无法实现了。所以，为了实现大整数的乘法，需要自己定义一种数据类型，以及对应的基本运算。

在该算法中，为了调试和处理方便，我们采用静态整型数组来存放大整数，即用数组的每一个元素存放大整数一位上的数字。然后，分别定义用数组存放的大整数的加法、减法和移位运算。这样，我们就可以用定义的大整数进行后面分治乘法的运算。

(2) 分治思想

将位数是2的次幂的n位的十进制大整数X和Y各分为2段，每段的长为n/2位。则有，X=A×10n/2+B ，Y=C×10n/2+D。这样，乘积问题变为这样的分治问题：

                XY=(A×10n/2+B)(C×10n/2+D)=AC×10n+(AD+CB)×10n/2+BD            ①

如果按①式计算XY，我们可得时间复杂度T(n)=O(n2)（详细论证在课本上）。显然，用①式来计算X和Y的乘积并不比乘法竖式更有效。为了改进算法的计算复杂性，我们把XY写成另一种形式：

                    XY=AC×10n+[(A-B)(D-C)+AC+BD]×10n/2+BD                         ②

用解递归方程的套用公式法可得②式的时间复杂度T(n)=O(nlog3)=O(n1.59)，该结果有效地减小了算法的时间复杂度。因此，根据②式，我们得到了大整数相乘的分治算法。

(3) 高位补0的位数处理方法

我们提出的分治思想在理论上是可行的，但是在算法具体实现中，程序的递归过程要求每次进行分治计算，即带入②式的大整数X和Y有如下要求：

1．X和Y的位数相同。

2．X和Y的位数是2的次幂。

按照这样的，我们只能计算n×n位（n=1,2,4,8,16...）的整数乘法。显然，这样的算法有很大的局限性，它不能处理像132×12758这样更为普遍的问题。

因此，我们在算法里采用这样的处理方法：当大整数需要进行分治乘法时，在两个乘数的高位补0，使它们的位数达到相同的2的次幂；分治结束后，将得到的乘积的高位多余的0去除，进行加减等非分治算法运算；以此类推。

采用这种高位补0的位数处理方法，实现了任意位大整数的乘法。 

    除了上述三点之外，程序对鲁棒性做了增强，对非法输入和文件错误进行了检测。

程序设计代码： 

/*头文件 大数乘法问题.h*/

#ifndef KNAP_H

#define KNAP_H

#include

#include

#include

using namespace std;

/*定义数制，范围2到10*/

#define SCALE 10

/*整数的最大位数*/

const int Max = 1000;

/*表示整数的结构体*/

struct Integer

{

    bool positive;                                    //整数的正负

    short num[Max];                                //整数的各位数字，下标从0开始

    int length;                                    //整数的位数

};

/*两个整数的乘法类*/

class Multiply

{

public:

    Multiply(char *in, char *out);                        //构造函数

    ~Multiply();                                    //析构函数

    void OutputProduct();                            //输出大整数的乘积

protected:

    short CharToInt(char ch);                        //将数字字符转化成整型

    int AddDigit(Integer &X, Integer &Y);                 //将位数补充到相同2的次幂位

    void InitialInteger(Integer &integer, ifstream &in);    //文件初始化大整数

    void OutputInteger(Integer integer);                //输出大整数integer

    void ClearZero(Integer &integer);                    //去除大整数高位多余的0

    bool PositiveXGreaterThanY(Integer X, Integer Y);        //判断是否非负X大于非负Y

    bool EqualsToZero(Integer integer);                //判断是否等于0

    Integer Zero();                                    //返回大整数0

    Integer GetAbsolute(Integer integer);                //返回大整数integer的绝对值

    Integer GetNegative(Integer integer);                //返回大整数integer的负值

    Integer GetLeft(Integer integer);                    //取大整数integer左一半

    Integer GetRight(Integer integer);                    //取大整数integer右一半

    Integer LeftShifting(Integer integer, int digit);        //大整数向左移digit位，低位补0

    Integer Plus(Integer X, Integer Y);                    //大整数加法

    Integer Subtract(Integer X, Integer Y);                //大整数减法

    Integer SameSignPlus(Integer X, Integer Y);            //同号大整数加法

    Integer SameSignSubtract(Integer X, Integer Y);        //同号大整数减法

    Integer OneDigitMultiply(Integer X, Integer Y);        //非负1位大整数乘法

    Integer FreeMultiply(Integer X, Integer Y);            //任意大整数乘法

    Integer NDigitsMultiply(Integer X, Integer Y, int n);    //2的n次幂乘法，高位补0

private:

    Integer integer_X, integer_Y;                        //数组存储的大整数

    ofstream fout;                                    //输出结果文件

};

#endif

/*函数实现文件 大数乘法问题.cpp*/

#include "大数乘法问题.h"

Multiply::Multiply(char *in, char *out) : fout(out)

{

    try                                            //非法输入检测

    {

        ifstream fin(in);

        if( !fin )

            throw "输入文件无法打开！\\n";

        InitialInteger(integer_X, fin);                    //文件初始化大整数integer_X

        fin.ignore(100, '\\n');                        //冲掉回车

        InitialInteger(integer_Y, fin);                    //文件初始化大整数integer_Y

        fin.close();                                //关闭文件

        if( !fout )

            throw "输出文件无法打开！\\n";

    }

    catch(char *string)

    {

     cout << string;

        system("pause");

        exit(0);

    }

}

Multiply::~Multiply()

{

    if(fout)

        fout.close();

}

void Multiply::OutputProduct()

{

    Integer temp = FreeMultiply(integer_X, integer_Y);

    ClearZero(temp);

    OutputInteger(temp);

}

short Multiply::CharToInt(char ch)

{

    short temp;

    switch(ch)

    {

    case '0' : temp = 0; break;

    case '1' : temp = 1; break;

    case '2' : temp = 2; break;

    case '3' : temp = 3; break;

    case '4' : temp = 4; break;

    case '5' : temp = 5; break;

    case '6' : temp = 6; break;

    case '7' : temp = 7; break;

    case '8' : temp = 8; break;

    case '9' : temp = 9; break;

    default : temp = -1; break;

    }

    if(temp == -1)

        throw "Error : 输入存在非数字字符！\\n";

if(temp >= SCALE)

        throw "Error : 输入不符合数制！\\n";

    return temp;

}

int Multiply::AddDigit(Integer &X, Integer &Y)

{

    int digit = 0;

if(X.length > Y.length)

        digit = X.length;

    else

        digit = Y.length;                            //取二者最大位数

    int i;

for(i = 0; pow(2.0, i) < digit; i++);

    digit = (int)pow(2.0, i);                            //取满足二者的最小2的次幂

for(i = digit-1; i >= X.length; i--)

        X.num[i] = 0;

for(i = digit-1; i >= Y.length; i--)

        Y.num[i] = 0;                                //高位补0，使位数达到2的次幂

    X.length = Y.length = digit;                        //改变二者的位数

    return digit;                                    //返回2的次幂

}

void Multiply::InitialInteger(Integer &integer, ifstream &in)

{

    if(in.peek() == '-')

    {

        in.get();

        integer.positive = false;

    }

    else

        integer.positive = true;

    int i;

    char temp[Max];

    for(i = 0; in.peek() != '\\n' && !in.eof(); i++)            //读到回车处或文件结束

     in >> temp[i];

    integer.length = i;

for(i = 0; i < integer.length; i++)

        integer.num[i] = CharToInt(temp[integer.length - i - 1]);//将每一位字符转化为整型

}

void Multiply::OutputInteger(Integer integer)

{

    if(integer.length == 0)                            //结果为0

     fout << integer.num[0];

    else

    {

        if(integer.positive == false)                    //结果为负数

         fout << '-';

     for(int i = integer.length - 1; i > -1; i--)

         fout << integer.num[i];

    }

}

void Multiply::ClearZero(Integer &integer)

{

for(int i = integer.length-1; integer.num[i] == 0 && i >= 0; i--)

        integer.length--;

}

bool Multiply::PositiveXGreaterThanY(Integer X, Integer Y)

{

if(X.length > Y.length)                            //X位数大于Y

        return true;

else if(X.length < Y.length)                        //X位数小于Y

        return false;

    else

     for(int i = X.length-1; i >= 0; i--)                //从高位逐位比较

         if(X.num[i] > Y.num[i])                    //某一位X大于Y

                return true;

         else if(X.num[i] < Y.num[i])                //某一位X小于Y

                return false;

    return true;                                    //X=Y返回true

}

bool Multiply::EqualsToZero(Integer integer)

{

for(int i = integer.length-1; i >= 0; i--)

        if(integer.num[i] != 0)

            return false;

    return true;

}

Integer Multiply::Zero()

{

    Integer temp;

    temp.length = 0;                                //0的位数定义为0

    temp.positive = true;

    temp.num[0] = 0;                                //0的第一位默认为0

    return temp;

}

Integer Multiply::GetAbsolute(Integer integer)

{

    if(integer.positive == false)

        integer.positive = true;

    return integer;

}

Integer Multiply::GetNegative(Integer integer)

{

    if(integer.positive == true)

        integer.positive = false;

    else

        integer.positive = true;

    return integer;

}

Integer Multiply::GetLeft(Integer integer)

{

    Integer temp;

    temp.length = integer.length / 2;                    //位数为一半

    temp.positive = true;                            //默认是正数

for(int i = 0; i < temp.length; i++)                    //取原整数左一半

        temp.num[i] = integer.num[i+temp.length];

    ClearZero(temp);                                //去除高位多余的0

    return temp;

}

Integer Multiply::GetRight(Integer integer)

{

    Integer temp;

    temp.length = integer.length / 2;                    //位数为一半

    temp.positive = true;                            //默认是正数

for(int i = 0; i < temp.length; i++)                    //取原整数右一半

        temp.num[i] = integer.num[i];

    ClearZero(temp);                                //去除高位多余的0

    return temp;

}

Integer Multiply::LeftShifting(Integer integer, int digit)

{

    if(!EqualsToZero(integer))

    {

     for(int i = integer.length + digit - 1; i >= digit - 1; i--)

            integer.num[i] = integer.num[i-digit];        //原有位向高位移digit位

     for(int i = digit - 1; i >= 0; i--)

            integer.num[i] = 0;                        //低位补0

        integer.length = integer.length + digit;            //位数加digit

    }

    return integer;

}

Integer Multiply::Plus(Integer X, Integer Y)

{

    if(X.positive == Y.positive)                        //同号

        return SameSignPlus(X, Y);

    else                                            //异号

        if(X.positive)                                //X正Y负

        {

            Y = GetNegative(Y);                        //Y取负得正

            return SameSignSubtract(X, Y);

        }

        else                                        //Y正X负

        {

            X = GetNegative(X);                        //X取负得正

            return SameSignSubtract(Y, X);

        }

}

Integer Multiply::Subtract(Integer X, Integer Y)

{

    if(X.positive == Y.positive)                        //同号

        return SameSignSubtract(X, Y);

    else

    {

        Y = GetNegative(Y);                            //Y取负得正

        return SameSignPlus(X, Y);

    }

}

Integer Multiply::SameSignPlus(Integer X, Integer Y)

{

    int i;

    int carry_flag = 0;                                //进位

for(i = 0; i < X.length && i < Y.length; i++)

    {

        if(X.num[i] + Y.num[i] + carry_flag > SCALE-1)    //当为加法需要进位

        {

            X.num[i] = (X.num[i] + Y.num[i] + carry_flag) % SCALE;

            carry_flag = 1;

        }

        else

        {

            X.num[i] = X.num[i] + Y.num[i] + carry_flag;

            carry_flag = 0;

        }

    }

if(i < X.length)                                    //被加数位数大于加数

    {

     while(i < X.length)

        {

         if(X.num[i] + carry_flag > SCALE-1)            //需要进位

            {

                X.num[i++] = (X.num[i] + carry_flag) % SCALE;

                carry_flag = 1;

            }

            else

            {

                X.num[i++] = X.num[i] + carry_flag;

                carry_flag = 0;

            }

        }

    }

else if(i < Y.length)                                //加数位数大于被加数

    {

     while(i < Y.length)

        {

         if(Y.num[i] + carry_flag > SCALE-1)            //需要进位

            {

                X.num[i++] = (Y.num[i] + carry_flag) % SCALE;

                carry_flag = 1;

            }

            else

            {

                X.num[i++] = Y.num[i] + carry_flag;

                carry_flag = 0;

            }

        }

    }

    if(carry_flag == 1)                                //最高位存在进位

    {

        X.num[i] = 1;

        X.length = i+1;

    }

    else

    {

        X.length = i;

    }

    return X;

}

Integer Multiply::SameSignSubtract(Integer X, Integer Y)

{

    if(PositiveXGreaterThanY(X, Y))                    //如果绝对值X>=Y

    {

        int i;

        int carry_flag = 0;                            //借位

        bool first_0 = true;                            //高位第一次出现0

        int top_digit_0 = 0;                            //记录结果最高位+1的下标

        int top_digit = 0;                            //记录结果最高位下标

     for(i = 0; i < Y.length; i++)

        {

         if(X.num[i] - carry_flag < Y.num[i])            //需要向高位借位

            {

                X.num[i] = (X.num[i] - carry_flag + SCALE - Y.num[i]);

                carry_flag = 1;

            }

            else

            {

                X.num[i] = X.num[i] - carry_flag - Y.num[i];

                carry_flag = 0;

            }

            if(X.num[i] == 0)                        //高位出现0

            {

                if(first_0)                            //且是第一次出现0

                {

                    first_0 = false;                    //再出现0则不是第一次出现0

                    top_digit_0 = i;                //记录结果最高位+1的下标

                }

            }

            else

            {

                first_0 = true;

                top_digit = i;

            }

        }

        if(carry_flag == 1)                            //最高位存在借位

        {

            X.num[i] = X.num[i] - carry_flag;

            if(X.num[i] == 0 && first_0)

                top_digit_0 = i;

        }

     if(top_digit < X.length - 1)                    //如果被减数更高位还有数字

            top_digit = X.length;

     if(top_digit_0 && top_digit_0 > top_digit)        //top_digit_0==0表示没有改变

            X.length = top_digit_0;                    //调整结果的位数

        return X;

    }

    else                                            //如果X    {

        X = SameSignSubtract(Y, X);                    //先用Y-X

        X = GetNegative(X);                            //再去负值

        return X;

    }

}

Integer Multiply::OneDigitMultiply(Integer X, Integer Y)

{

    Integer temp;

    temp.positive = true;

    int product;                                    //乘积

    product = X.num[0] * Y.num[0];

    int i;

    for(i = 0; product != 0; i++)                        //存储到数组中

    {

        temp.num[i] = product % SCALE;

        product /= SCALE;

    }

    temp.length = i;

    return temp;

}

Integer Multiply::FreeMultiply(Integer X, Integer Y)

{

    bool sign;                                        //乘积符号

    if(X.positive == Y.positive)                        //同号

        sign = true;                                //乘积是正数

    else                                            //同号

        sign = false;                                //乘积是负数

    X = GetAbsolute(X);

    Y = GetAbsolute(Y);                                //取两数绝对值

    if(EqualsToZero(X) || EqualsToZero(Y))                //如果有0，乘积为0

        return Zero();

    Integer temp;

    if(X.length == 1 && Y.length == 1)                    //只剩1位乘法

        temp = OneDigitMultiply(X, Y);                //返回1位乘积

    else

    {

        int n = AddDigit(X, Y);                        //X和Y位数补充到2的次幂位

        temp = NDigitsMultiply(X, Y, n);                //分治法得到乘积

    }

    temp.positive = sign;                            //赋符号

    return temp;                                    //返回递归结果

}

Integer Multiply::NDigitsMultiply(Integer X, Integer Y, int n)

{

    Integer A = GetLeft(X);                            //返回X的左一半

    Integer B = GetRight(X);                            //返回X的右一半

    Integer C = GetLeft(Y);                            //返回Y的左一半

    Integer D = GetRight(Y);                            //返回Y的右一半

    Integer AxC = FreeMultiply(A, C);                    //返回A*C

    Integer BxD = FreeMultiply(B, D);                    //返回B*D

    Integer A_B = Subtract(A, B);                        //返回A-B

    Integer D_C = Subtract(D, C);                        //返回D-C

    Integer A_BxD_C = FreeMultiply(A_B, D_C);            //返回(A-B)*(D-C)

    Integer AxDtBxC = Plus(A_BxD_C, Plus(AxC, BxD));    //返回A*D+B*C

    Integer AxC_2n = LeftShifting(AxC, n);                //返回A*C左移n位结果

    Integer AxDtBxC_2n2 = LeftShifting(AxDtBxC, n/2);    //返回A*D+B*C左移n/2位结果

    return Plus(Plus(AxC_2n, AxDtBxC_2n2), BxD);        //函数返回一次乘法结果

}

/*主函数文件 test.cpp*/

#include "大数乘法问题.h"

int main()

{

    char *in = "input.txt";                            //输入文件

    char *out = "output.txt";                        //输出文件

    Multiply multiply(in, out);                        //文件初始化SCALE进制大整数

    multiply.OutputProduct();                        //计算并输出大整数的乘积

    return 0;

}