大整数乘法问题

巡山小妖精
675次浏览
2021年01月11日 09:44
最佳经验
本文由作者推荐

性价比车-文章赏析

2021年1月11日发(作者：盛可继)


2.4 大整数乘法问题
算法设计思想：
(1) 大整数的存储
我们知道，在编译系统中，整型数据类型的最大存储空间为8字节，也就是最大能
存储2
32< br>的数据。即使使用双精度浮点数据类型（double），也只能存储最大1.798×10
30 8
的数据。如果需要计算10
200
数量级的整数的乘法，利用的现有的数据类型就无 法实现了。
所以，为了实现大整数的乘法，需要自己定义一种数据类型，以及对应的基本运算。
在该算法中，为了调试和处理方便，我们采用静态整型数组来存放大整数，即用数
组的每一个元素存放 大整数一位上的数字。然后，分别定义用数组存放的大整数的加法、
减法和移位运算。这样，我们就可以 用定义的大整数进行后面分治乘法的运算。
(2) 分治思想
将位数是2的次幂的n位的十 进制大整数X和Y各分为2段，每段的长为n2位。
则有，X=A×10
n2
+B ，Y=C×10
n2
+D。这样，乘积问题变为这样的分治问题：
XY=( A×10
n2
+B)(C×10
n2
+D)=AC×10
n
+(AD+CB)×10
n2
+BD ①
如果按①式计算XY，我 们可得时间复杂度T(n)=O(n
2
)（详细论证在课本上）。显然，用
①式来计算 X和Y的乘积并不比乘法竖式更有效。为了改进算法的计算复杂性，我们把XY
写成另一种形式：
XY=AC×10
n
+[(A-B)(D-C)+AC+BD]×10n2
+BD ②
用解递归方程的套用公式 法可得②式的时间复杂度T(n)=O(n
log3
)=O(n
1.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];
int length;
};
*两个整数的乘法类*
class Multiply
{
public:
Multiply(char *in, char *out);
~Multiply();
void OutputProduct();
protected:
short CharToInt(char ch);
int AddDigit(Integer &X, Integer &Y);
void InitialInteger(Integer &integer, ifstream &in);
void OutputInteger(Integer integer);
void ClearZero(Integer &integer);
bool PositiveXGreaterThanY(Integer X, Integer Y);
bool EqualsToZero(Integer integer);
Integer Zero();
Integer GetAbsolute(Integer integer);
Integer GetNegative(Integer integer);
Integer GetLeft(Integer integer);
Integer GetRight(Integer integer);
整数的正负
整数的各位数字，下标从0开始
整数的位数
构造函数
析构函数
输出大整数的乘积
将数字字符转化成整型
将位数补充到相同2的次幂位
文件初始化大整数
输出大整数integer
去除大整数高位多余的0
判断是否非负X大于非负Y
判断是否等于0
返回大整数0
返回大整数integer的绝对值
返回大整数integer的负值
取大整数integer左一半
取大整数integer右一半


Integer LeftShifting(Integer integer, int digit);
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);
Integer FreeMultiply(Integer X, Integer Y);
Integer NDigitsMultiply(Integer X, Integer Y, int n);
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);
(100, 'n');
InitialInteger(integer_Y, fin);
();
if( !fout )
throw 输出文件无法打开！n
}
catch(char *string)
{
cout << string;
system(
exit(0);
}
}
Multiply::~Multiply()
{
if(fout)
();
大整数向左移digit位，低位补0
大整数加法
大整数减法
同号大整数加法
同号大整数减法
非负1位大整数乘法
任意大整数乘法
2的n次幂乘法，高位补0
数组存储的大整数
输出结果文件
非法输入检测
文件初始化大整数integer_X
冲掉回车
文件初始化大整数integer_Y
关闭文件


}
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 输入存在非数字字符！n
if(temp >= SCALE)
throw 输入不符合数制！n
return temp;
}
int Multiply::AddDigit(Integer &X, Integer &Y)
{
int digit = 0;
if( > )
digit =
else
digit =
int i;
for(i = 0; pow(2.0, i) < digit; i++);
digit = (int)pow(2.0, i);
取二者最大位数
取满足二者的最小2的次幂


for(i = digit-1; i >= ; i--)
[i] = 0;
for(i = digit-1; i >= i--)
[i] = 0; 高位补0，使位数达到2的次幂
= = digit; 改变二者的位数
return digit; 返回2的次幂
}
void Multiply::InitialInteger(Integer &integer, ifstream &in)
{
if(() == '-')
{
();
ve = false;
}
else
ve = true;
int i;
char temp[Max];
for(i = 0; () != 'n' && !(); i++) 读到回车处或文件结束
in >> temp[i];
= i;
for(i = 0; i < i++)
[i] = CharToInt(temp[ - i - 1]);将每一位字符转化为整型
}
void Multiply::OutputInteger(Integer integer)
{
if( == 0) 结果为0
fout << [0];
else
{
if(ve == false) 结果为负数
fout << '-';
for(int i = - 1; i > -1; i--)
fout << [i];
}
}
void Multiply::ClearZero(Integer &integer)
{
for(int i = -1; [i] == 0 && i >= 0; i--)
--;


}
bool Multiply::PositiveXGreaterThanY(Integer X, Integer Y)
{
if( > )
return true;
else if( < )
return false;
else
for(int i = -1; i >= 0; i--)
if([i] > [i])
return true;
else if([i] < [i])
return false;
return true;
}
bool Multiply::EqualsToZero(Integer integer)
{
for(int i = -1; i >= 0; i--)
if([i] != 0)
return false;
return true;
}
Integer Multiply::Zero()
{
Integer temp;
= 0;
ve = true;
[0] = 0;
return temp;
}
Integer Multiply::GetAbsolute(Integer integer)
{
if(ve == false)
ve = true;
return integer;
}
Integer Multiply::GetNegative(Integer integer)
{
if(ve == true)
ve = false;
X位数大于Y
X位数小于Y
从高位逐位比较
某一位X大于Y
某一位X小于Y
X=Y返回true
0的位数定义为0
0的第一位默认为0


else
ve = true;
return integer;
}
Integer Multiply::GetLeft(Integer integer)
{
Integer temp;
= 2; 位数为一半
ve = true; 默认是正数
for(int i = 0; i < i++) 取原整数左一半
[i] = [i+];
ClearZero(temp); 去除高位多余的0
return temp;
}
Integer Multiply::GetRight(Integer integer)
{
Integer temp;
= 2; 位数为一半
ve = true; 默认是正数
for(int i = 0; i < i++) 取原整数右一半
[i] = [i];
ClearZero(temp); 去除高位多余的0
return temp;
}
Integer Multiply::LeftShifting(Integer integer, int digit)
{
if(!EqualsToZero(integer))
{
for(int i = + digit - 1; i >= digit - 1; i--)
[i] = [i-digit];
for(int i = digit - 1; i >= 0; i--)
[i] = 0;
= + digit;
}
return integer;
}
Integer Multiply::Plus(Integer X, Integer Y)
{


if(ve == ve)
return SameSignPlus(X, Y);




原有位向高位移digit位
低位补0
位数加digit
同号








else
if(ve)
{
Y = GetNegative(Y);
return SameSignSubtract(X, Y);
}






异号
X正Y负
Y取负得正
else Y正X负
{
X = GetNegative(X); X取负得正
return SameSignSubtract(Y, X);
}
}
Integer Multiply::Subtract(Integer X, Integer Y)
{
if(ve == ve) 同号
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 < && i < i++)
{
if([i] + [i] + carry_flag > SCALE-1) 当为加法需要进位
{
[i] = ([i] + [i] + carry_flag) % SCALE;
carry_flag = 1;
}
else
{
[i] = [i] + [i] + carry_flag;
carry_flag = 0;
}
}
if(i < ) 被加数位数大于加数










































{
while(i < )
{
if([i] + carry_flag > SCALE-1) 需要进位
{
[i++] = ([i] + carry_flag) % SCALE;
carry_flag = 1;
}
else
{
[i++] = [i] + carry_flag;
carry_flag = 0;
}
}
}
else if(i < ) 加数位数大于被加数
{
while(i < )
{
if([i] + carry_flag > SCALE-1) 需要进位
{
[i++] = ([i] + carry_flag) % SCALE;
carry_flag = 1;
}
else
{
[i++] = [i] + carry_flag;
carry_flag = 0;
}
}
}
if(carry_flag == 1) 最高位存在进位
{
[i] = 1;
= i+1;
}
else
{
= 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 < i++)
{
if([i] - carry_flag < [i]) 需要向高位借位
{
[i] = ([i] - carry_flag + SCALE - [i]);
carry_flag = 1;
}
else
{
[i] = [i] - carry_flag - [i];
carry_flag = 0;
}
if([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) 最高位存在借位
{
[i] = [i] - carry_flag;


if([i] == 0 && first_0)
top_digit_0 = i;
}
if(top_digit < - 1)
top_digit =
if(top_digit_0 && top_digit_0 > top_digit)
= top_digit_0;
return X;
}
else
{
X = SameSignSubtract(Y, X);
X = GetNegative(X);
return X;
}
}
Integer Multiply::OneDigitMultiply(Integer X, Integer Y)
{
Integer temp;
ve = true;
int product;
product = [0] * [0];
int i;
for(i = 0; product != 0; i++)
{
[i] = product % SCALE;
product = SCALE;
}
= i;
return temp;
}
Integer Multiply::FreeMultiply(Integer X, Integer Y)
{
bool sign;
if(ve == ve)
sign = true;
else
sign = false;
X = GetAbsolute(X);
Y = GetAbsolute(Y);
如果被减数更高位还有数字
top_digit_0==0表示没有改变
调整结果的位数
如果X先用Y-X
再去负值
乘积
存储到数组中
乘积符号
同号
乘积是正数
同号
乘积是负数
取两数绝对值












if(EqualsToZero(X) || EqualsToZero(Y))
return Zero();
Integer temp;
if( == 1 && == 1)
temp = OneDigitMultiply(X, Y);
else
{
int n = AddDigit(X, Y);
temp = NDigitsMultiply(X, Y, n);
}
如果有0，乘积为0






只剩1位乘法
返回1位乘积






X和Y位数补充到2的次幂位
分治法得到乘积
ve = 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, n2); 返回A*D+B*C左移n2位结果
return Plus(Plus(AxC_2n, AxDtBxC_2n2), BxD); 函数返回一次乘法结果
}
*主函数文件 *

#include 大数乘法问题.h
int main()
{
char *in =
char *out =
Multiply multiply(in, out);
Product();
return 0;
}




















输入文件
输出文件
文件初始化SCALE进制大整数
计算并输出大整数的乘积

凉菜拼盘-八年级语文练习册答案


秦康-战争给人类带来的灾难


狂风为我们呐喊-我还是我


再见孝琳-成功名言


喝碳酸饮料的坏处-密西西比河风光


笔记本无线网络-三月三图片


髀肉复生-我的中国梦ppt


立军-鞠躬