高精度算法

写在前面

其实写这个只是给自己稍微总结一下学到的一些东西。由于本人过于菜鸡，所以都是很基础的算法，复杂的我也学不会。

自己尽量会写的正确点＆易懂点，但仍可能会有错误，所以…带个人思考的看…?

高精度加法

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

string add(string a, string b) {
	bool flag = 0;		//是否进位，0为否
	string result;		//最后结果
	int tmp;

	//将a,b补成相同的长度
	if (a.length() > b.length()) {
		int tmp = a.length() - b.length();
		for (int i = 1; i <= tmp; i++) b = '0' + b;
	}
	else {
		int tmp = b.length() - a.length();
		for (int i = 1; i <= tmp; i++) a = '0' + a;
	}
	//从后往前逐位相加
	for (int i = a.length() - 1; i >= 0; i--) {
		tmp = a[i] - '0' + b[i] + flag;
		//处理进位
		if (tmp > '9') {
			result = char(tmp - 10) + result;
			flag = 1;
		}
		else {
			result = char(tmp) + result;
			flag = 0;
		}
	}
	//处理最前面的进位
	if (flag) {
		result = '1' + result;
	}
	return result;
}

注意：仅适用于a,b>0；

感觉高精度加法没什么好说的，很基础的做法，效率也不错。

高精度减法

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

string subtract(string a, string b) {
	int flag = 0;	//判断是否要借位，0为否
	int tmp;
	string result;

	//因为结果可能为负数，因此先判断a,b的大小
	bool bigger = 0;
	//位数大的一定更大
	if (a.length() > b.length())	bigger = true;
	//位数相同则比较字典序
	else if (a.length() == b.length() && a >= b) bigger = true;
	
	//确保a更大
	if (!bigger) {
		string tmp = a;
		a = b;
		b = tmp;
	}

	//将位数补齐
	while (a.length() - b.length()) {
		b = '0' + b;
	 }
	
	//从后往前做减法
	for (int i = a.length() - 1; i >= 0; i--) {
		tmp = a[i] - b[i] - flag;
		//判断是否需要借位
		if (tmp < 0)  flag = 1;
		else flag = 0;
		result = char(tmp + flag * 10 + '0') + result;		//需要借位的话需要将tmp+10
	}
	
	//去除前导0
	int i = 0;
	while (result[i] == '0') {
		i++;
	 }
	//结果为0时，应保留一个0
	if (i == result.length())i--;
	result = result.substr(i);

	//输出负号
	if (!bigger) result = '-' + result;

	return result;
}

注意：仅适用于a,b＞0

可能的踩坑点：

1. a<b时应该为负数，要额外加个“-“
2. 前导0的问题。100-99不加处理的话会变成001；
3. 结果为0的问题。如果删除前导0时不考虑这种情况，那么9-9将什么都不会输出

高精度乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int tmp[50000];
string mutiply(string a, string b) {
	string result ="";
	int a_len = a.length();
	int b_len = b.length();
	//按乘法原理逐位相乘
	for (int i = a_len - 1; i >= 0; i--) {
		for (int j = b_len - 1; j >= 0; j--) {
			tmp[a_len + b_len - i - j - 1] += (a[i] - '0') * (b[j] - '0');
		}
	}
	//处理进位
	int tmp_len = a_len + b_len;
	for (int i = 1; i < tmp_len; i++) {		//两数相乘结果的位数一定小于等于两数位数
		if (tmp[i] > 9) {
			tmp[i + 1] += tmp[i] / 10;
			tmp[i] %= 10;
		}
	}
	//去除前导0,否则10*0结果为00
	while (tmp[tmp_len] == 0 && tmp_len > 1)	tmp_len--;
	for (int i = 1; i <=tmp_len; i++) result = char(tmp[i] + '0') + result;
	return result;
}

注意：仅适用于a,b≥0

TO DO:高精度除法

高精度阶乘

以下代码并不适用于所有情况。实测当len = 200,N = 10e14;时能计算出2!1000，结果后附供校对。

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

#define len 200
#define N 100000000000000

long long a[len] = { 1 }, result[len];
int factorial(int n) {	//返回result的位数
	long long carry = 0;	//表示进位
	for (int i =1; i <= n; i++) {
		//高精度乘法：高精度*int
		for (int j = 0; j < len; j++) {
			a[j] = a[j] * i + carry;
			//除以N而不是除以10是为了尽可能的利用int的空间(~2^10)，下面同理
			carry = a[j] / N;
			a[j] = a[j] % N;
		}
		//高精度加法
		carry = 0;
		for (int j = 0; j < len; j++) {
			result[j] = result[j] + a[j] + carry;
			carry = result[j] / N;
			result[j] = result[j] % N;
		}
	}
	//判断位数
	int lenth = len;
	while (result[lenth - 1] == 0 && lenth > 1)	lenth--;
	return lenth;
}
//注意最后输出时应该是逆序输出
for (int i = factorial(n) - 1; i >= 0; i--)	cout << result[i];

附录

1000!=4027905053122345768670558292183044930441094551528966419334642920075902370082550849878938111228748403226643957277673191284838468927263989687905690103501897786554341544337696514461654951538851077440410165819782073475583082079396504111380884916810768467471317168913183948275897490803646698793846190852594417739671786914563472162093180956284720843607311204509397095907530114810381703803860648328656344389023077975647748628886817466804724858587747840936784462436173977429991182753207302348016538494642001301432395279726745538178727708503090870745742249581124437084158031806471602854863650302741825130214652788342621283870175833906572656890104432413095171095723550851047360182700817666447833459792895738687627176555413740711174766651230998067853988678687826290258453911823151931683552388541377672034266969531263032928282242353491346302800844806465049776475547382410225945312773007777753106311513876495252759709844538004644399754092588008693631793342176842492508470741481293232916674588623413722692302481346190036322599946452493522794764716794743441163713920351740437121423299823949395456232332776903915931443305369962856388265027346155623332543302943446674383336948488594760969564013979720883843849399863648257295093077791964440615462408422804298527057377454368956529809230106268980768907112031757851014218189279824719907145202202917270740068875898030570292381329154485173914211657597582497807598793035565731652297925769886549168450867091163868402442018371341022143349409418974223779315401317123760884519266468022552657218233256445396109179244871088667489725189928143289796681735238195169437018438329910965407841035648914496097727448032065520547484257131085876715457907964421551419900383259923263102068452820395581311114047307468681426051322892063650122841004997271652977702547274337834459757112850838135183696311712170990224739928697694772853140476802033735594574707189941820656793611572800671948131128109558012358679446259496244143021997936801273888393124129184635058327016137044640473948916935678249463650959768200928958728748330673454723995492137365682778815741591206707652159624635871844554339227025068139536377423837689642266483656100701688393247498969109923908046589884791076785625508448585145127624556376778630678216900832228344056133887091191887194791815281908368889081528457290215134916585865098894556135702731215416389951458945610799992135000761012487815006429790911980447363257291071445797682737767437164395575815572538782046473911765828511673121820261887951566200568565033492247479478684738621107994804323593105039052556442336528920420940313