高精度运算
拔丝地瓜
  2022-06-06 10:25:04 2022-06-06 10:25    

基础数据处理函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void moveFrontZero(string &a){//去除一个字符串的前导0
	a.erase(0,a.find_first_not_of('0'));
	if(a.empty()){
        a = "0";
    }
}

void align(string &a, string &b){//让两个字符串变成相同的长度，长度小的补0
	int a_size = a.size();
	int b_size = b.size();
	if(a_size < b_size){
		for(int i = 1; i <= b_size - a_size; i++){
			a = "0" + a;
		}
	}else{
		for(int i = 1; i <= a_size-b_size; i++){
			b = "0" + b;
		}
	}
}

高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string add(string addent, string adder){
	moveFrontZero(addent);
	moveFrontZero(adder);
	string answer = "";
	align(addent,adder);
	int temp = 0, carry = 0;//temp表示当前对位相加结果，carry表示进位
	for(int i = addent.size() - 1; i >= 0; i--){
		temp = addent[i] - '0' + adder[i] - '0' + carry;
		carry = temp/10;
		temp %= 10;
		answer = (char)(temp + '0') + answer;
	}
	if(carry){//处理最高位相加可能产生的进位
        answer = (char)(carry + '0') + answer;
    }
	moveFrontZero(answer);
	return answer;
}

高精度减法

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
string sub(string subtrahend, string subtractor){//顺序是被减数和减数
	moveFrontZero(subtrahend);
	moveFrontZero(subtractor);
	align(subtrahend,subtractor);
	bool is_minus = false;
	if(subtrahend < subtractor){
		is_minus = true;
		subtrahend.swap(subtractor);//确保大数减小数
	}
	string answer = "";
	int temp = 0,carry = 0;//temp表示当前对位相减结果，carry表示借位
	for(int i = subtrahend.size() - 1; i >= 0; i--){
		if(subtrahend[i] - carry < subtractor[i]){//被减数不够减的情况
			temp = subtrahend[i] - carry + 10 - subtractor[i];
			carry = 1;
			answer = (char)(temp +'0') + answer;
		}else{//被减数够减
			temp = subtrahend[i] - carry - subtractor[i];
			carry = 0;
			answer = (char)(temp +'0') + answer;
		}
	}
	moveFrontZero(answer);
	if(is_minus)answer = "-"+answer;
	return answer;
}

高精度乘法（需要依赖高精度加法）

乘法的主要思想是把乘法转化为加法进行运算。以下面具体的例子说明：

等式（1）​说明，多位数乘一位数，可以直接使用加法完成。

等式（2）说明，多位数乘形如的数，可以转换成多位数乘一位数来处理。

等式（3）说明，多位数乘多位数，可以转换为若干个多位数乘形如的数与多位数乘一位数之和。

因此，多位数乘多位数最终可以全部用加法来实现。

1
2
3
4
5
6
7
8
9
10
11
12
string mul(string multiplicand, string multiplier){
    //multiplicand表示被乘数，即上面例子中的12345，multiplier是乘数，即上面例子的24
    string answer = "0";//answer必须初始化为“0”
    for (int i = (int) multiplier.length() - 1; i >= 0 ; i--) {
        for (char c = '1'; c <= multiplier[i]; c++) {
            answer = add(answer, multiplicand);
        }
        multiplicand = multiplicand + "0";
    }
    moveFrontZero(answer);
	return answer;
}

高精度除法（需要依赖高精度减法）

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
//试商法
string div(string dividend, string divisor){
	moveFrontZero(dividend);
	moveFrontZero(divisor);
	string answer = "";
	string reminder = "";
	reminder.append(dividend,0,divisor.size()-1);//截取被除数从首位到除数位数的前一位
	for(int i = divisor.size() - 1; i < dividend.size(); i++){
		reminder = reminder + dividend[i];
		moveFrontZero(reminder);
		for(char j = '9';j >= '0'; j--){
			string temp = "";
			temp = temp + j;
			temp = mul(divisor,temp);
			align(temp,reminder);
			if(temp <= reminder){
				answer = answer + j;
				reminder = sub(reminder,temp);
				break;
			}
		}
	}	
    moveFrontZero(answer);
	//cout  <<  "reminder="  <<  reminder  <<  endl;
	return answer;
}

高精度阶乘（利用高精度减法和乘法实现）

1
2
3
4
5
6
7
8
string factorial(string a){//高精度阶乘（最大可运行出10000左右的阶乘）
    moveFrontZero(a);
	if(a == "1"){
		return a;
    }
	else 
		return mul(a,factorial(sub(a,"1")));//即利用递归转化为a*(a-1)!
}