2-算法思想之分治法-大整数乘法问题

|

算法–分治法之大整数乘法

问题描述

在计算机上处理一些大数据相乘时，由于计算机硬件的限制，不能直接进行相乘得到想要的结果。可以将一个大的整数乘法分而治之，将大问题变成小问题，变成简单的小数乘法再进行合并，从而解决上述问题。

问题分析

分析：大数据可以分解称高位和地位，比如1534268973可以表示为15342*10^5+68973，那么两个大数据都进行拆解后，可以通过十字相乘获得4个相对较小的乘法，将4个乘法的结果相加即可得到大数据相乘的结果。4个相对较小的乘法各自可以继续分解称4个更小的乘法，再进行合并。

举个例子： 3278×41926

​ =(32×10^2+78)×(419×10^2+26)

​ =32×419×10^4 + 32 × 26 × 10^2 + 78×419×10^2 + 78×26

继续拆分：

​ 32×419×10^4

​ =(3×10+2)×(41×10+9)×10^4

​ =3×41×10^6 + 3×9×10^5 + 2×41×10^5 + 2×9×10^4

​ =123×10^6 + 27×10^5 + 82×10^5 + 18×10^4

​ =13408×10^4

算法实现

算法分析

实现大整数相乘需要三个主体函数，分解函数、乘法函数以及加法函数，分解函数负责将大整数分解成高位和低位，然后乘法函数负责将两个数据的高位和地位十字相乘获得各自的值，加法函数负责将4个相乘的值相加。分解函数需要4个参数——需要分解的大整数src，分解后的相对小的整数的空间des，开始分解的起始位置Start以及分解的长度length。乘法函数同样需要3个参数——两个大整数multiplierA、multiplierB和用来存储结果的数的空间answer。加法函数与乘法函数相同，需要3个参数——两个大整数augend、addend和用来存储结果的数的空间。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <stdlib.h>
#include <cstring>
#include <iostream>

using namespace std;

#define M 100
char string_largeInteger_A[1000];
char string_largeInteger_B[1000];

typedef struct _Node
{
	int data[M];
	int length;
	int pow;
}Node, *pNode;

void Multiplie(pNode pa, pNode pb, pNode ans);
void Decompose(pNode src, pNode des, int Start, int length);
void Add(pNode pa, pNode pb, pNode ans);

int main()
{
	Node answer, largeInteger_A, largeInteger_B;
	int digit;
	
	cout << "输入大整数 a: " << endl;
	cin >> string_largeInteger_A;
	cout << "输入大整数 b: " << endl;
	cin >> string_largeInteger_B;

	digit = 0;
	largeInteger_A.length = strlen(string_largeInteger_A);
	for (int i = largeInteger_A.length - 1; i >= 0; i--)
	{
		largeInteger_A.data[digit++] = string_largeInteger_A[i] - '0';
	}
	largeInteger_A.pow = 0;

	digit = 0;
	largeInteger_B.length = strlen(string_largeInteger_B);
	for (int i = largeInteger_B.length - 1; i >= 0; i--)
	{
		largeInteger_B.data[digit++] = string_largeInteger_B[i] - '0';
	}
	largeInteger_B.pow = 0;

	Multiplie(&largeInteger_A, &largeInteger_B, &answer);
	cout << "最终结果是：";
	for (int i = answer.length - 1; i >= 0; i--)
		cout << answer.data[i];
	cout << endl;
	return 0;
}

void Multiplie(pNode multiplierA, pNode multiplierB, pNode answer)
{
	//【1】定义函数实现所需要的变量
	Node multiplierA_highDigit, multiplierA_lowDigit, multiplierB_highDigit, multiplierB_lowDigit;
	Node temp_AhBh, temp_AhBl, temp_AlBh, temp_AlBl, temp_answer;
	pNode swap_temp;
	int bisection_A, bisection_B;
	int single_digit, answer_digit, remainder;

	//【2】对数据二等分进行预处理，选取二等分点
	remainder = 0;
	bisection_A = multiplierA->length >> 1;
	bisection_B = multiplierB->length >> 1;

	//【3】乘法函数的终止条件，当a或b中某个值的基数是个位数的时候，开始直接计算
	if (bisection_A == 0 || bisection_B == 0)
	{
		if (bisection_A == 0)
		{
			swap_temp = multiplierA;
			multiplierA = multiplierB;
			multiplierB = swap_temp;
		}
		answer->pow = multiplierA->pow + multiplierB->pow;

		single_digit = multiplierB->data[0];
		for (answer_digit = 0; answer_digit < multiplierA->length; answer_digit++)
		{
			answer->data[answer_digit] = (multiplierA->data[answer_digit] * single_digit + remainder) % 10;
			remainder = (multiplierA->data[answer_digit] * single_digit + remainder) / 10;
		}
		if (remainder) answer->data[answer_digit++] = remainder;
		answer->length = answer_digit;
		return;
	}

	//【4】根据二等分点将大整数a拆成高位和低位，大整数b拆成高位和低位
	Decompose(multiplierA, &multiplierA_highDigit, bisection_A, multiplierA->length - bisection_A);
	Decompose(multiplierA, &multiplierA_lowDigit, 0, bisection_A);
	Decompose(multiplierB, &multiplierB_highDigit, bisection_B, multiplierB->length - bisection_B);
	Decompose(multiplierB, &multiplierB_lowDigit, 0, bisection_B);

	//【5】将大整数a的高位、地位，大整数b的高位、地位进行两两相乘
	Multiplie(&multiplierA_highDigit, &multiplierB_highDigit, &temp_AhBh);
	Multiplie(&multiplierA_highDigit, &multiplierB_lowDigit, &temp_AhBl);
	Multiplie(&multiplierA_lowDigit, &multiplierB_highDigit, &temp_AlBh);
	Multiplie(&multiplierA_lowDigit, &multiplierB_lowDigit, &temp_AlBl);

	//【6】将十字相乘的四个值相加，获得最终结果
	Add(&temp_AlBh, &temp_AlBl, answer);
	Add(&temp_AhBl, answer, &temp_answer);
	Add(&temp_AhBh, &temp_answer, answer);
}

void Decompose(pNode src, pNode des, int Start, int length)
{
	for (int i = Start, j = 0; i < Start + length; i++, j++)
	{
		des->data[j] = src->data[i];
	}
	des->length = length;
	des->pow = Start + src->pow;
}

void Add(pNode augend, pNode addend, pNode answer)
{
	//【1】定义函数实现所需要的变量
	pNode swap_temp;		//用于被加数和加数的交换的临时变量

	int augend_digit, addend_digit, max_digit;		//用于记录被加数的位数、加数的位数和两个数中更长的数的位数
	int remainder;		//用于记录余数实现进位
	int augendx_temp, addendx_temp;		//被加数按位计算时所用的临时变量加数按位计算时所用的临时变量
	int answer_digit;		//用于记录结果的位数
	int pow_difference;		//用于记录被加数与加数次幂之差

	//【2】将次幂更小的作为加数，次幂更大的作为被加数以实现统一化的操作，避免分类讨论
	if (augend->pow < addend->pow)
	{
		swap_temp = augend;
		augend = addend;
		addend = swap_temp;
	}

	//【3】确定结果的次幂，取次幂更小的加数的次幂作为结果的次幂
	answer->pow = addend->pow;

	//【4】设置结果的位数为被加数和加数中位数更高的
	augend_digit = augend->pow + augend->length;
	addend_digit = addend->pow + addend->length;
	max_digit = (augend_digit > addend_digit) ? augend_digit : addend_digit  ;

	pow_difference = augend->pow - addend->pow;
	remainder = 0;
	for (answer_digit = 0; answer_digit < max_digit - answer->pow; answer_digit++)
	{
		//【5.1】被加数的次幂高于加数的次幂，所以在次幂差的几位中，被加数都为0; 而当被加数的位数低于加数的位数时，前面不够位数的要补0; 其余按位赋值
		if (answer_digit < pow_difference || answer_digit >= augend->length + pow_difference) augendx_temp = 0;		
		else augendx_temp = augend->data[answer_digit - pow_difference];
		
		//【5.2】加数的次幂更低，不存在次幂差，所以当加数的位数低的时候直接按位赋值，当加数的位数不够位数时要补0
		if (answer_digit < addend->length) addendx_temp = addend->data[answer_digit];
		else addendx_temp = 0;
		
		//【5.3】被加数、加数和余数按位相加，多出的进位
		answer->data[answer_digit] = (augendx_temp + addendx_temp + remainder) % 10;
		remainder = (augendx_temp + addendx_temp + remainder) / 10;
	}
	if (remainder) answer->data[answer_digit++] = remainder;
	answer->length = answer_digit;
}