[アルゴリズムノート]大整数演算

1.大整数記憶

大整数は高精度整数とも呼ばれ、基本データ型ではその精度の整数を村に格納できず、int型配列d[1000]を配列記憶で定義し、配列の各ビットに整数の各ビットを格納し、整数の高位は配列の高位に格納し、整数の低位は配列の低位演算の際に低位から高位に格納して列挙し、整数は文字列タイプで読み込まれる(読み込んだときは逆順で反転する必要がある)

struct bign {
	int d[1000];
	int len;
	bign() {
		memset(d, 0, sizeof(d));
		len = 0;
	}
};
bign change(char str[]) {// bign
	bign a;
	a.len = strlen(str);
	for (int i = 0; i < a.len; i++) {
		a.d[i] = str[a.len - i - 1] - '0';
	}
	return a;
}
int compare(bign a, bign b) {// 
	if (a.len > b.len)return 1;
	else if (a.len < b.len)return -1;
	else {
		for (int i = a.len - 1; i >= 0; i--) {
			if (a.d[i] > b.d[i])return 1;
			else if (a.d[i] < b.d[i])return -1;
		}
		return 0;// 
	}
}**

2.大整数加算

どちらかを加算するには、そのビットに2つの数字を加算し、さらにキャリーを加算し、得られた数はそのビット結果として、残りを新しいキャリーとする.(一方が負数の場合は絶対値をとって減算し、両方が負の場合は絶対値を取って加算してからマイナスを加算します)

bign add(bign a, bign b) {
	bign c;
	int carry = 0;// 
	for (int i = 0; i < a.len || i < b.len; i++) {
		int temp = a.d[i] + b.d[i] + carry;
		c.d[c.len++] = temp % 10;
		carry = temp / 10;
	}
	if (carry != 0) {
		c.d[c.len++] = carry;
	}
	return c;
}

3.大整数減算

各位に対して、比較的に減らされてと減らされて、もし減らされていないならば、減らされた高位を1減らして、減らされて10プラスされて、もし十分に減らされて、直接減らして、最後に高位の余分な0を除去して、少なくとも1桁の数(減らす前に2つの数の大きさを比較して、もしa

bign sub(bign a, bign b) {
	bign c;
	for (int i = 0; i < a.len || i < b.len; i++) {
		if (a.d[i] < b.d[i]) {
			a.d[i + 1]--;
			a.d[i] += 10;
		}
		c.d[c.len++] = a.d[i] - b.d[i];
	}
	while (c.len - 1 >= 1 && c.d[c.len - 1] == 0) {// 0  
		c.len--;
	}
	return c;
}

4.大整数乗算（高進度*低精度）

对每一位，取bign的某位与int型整体相乘，再与进位相加，所得个位数作为该位结果，高位部分作为新的进位
（有负号取其绝对值，然后带入函数）

bign multi(bign a, int b) {
	bign c;
	int carry = 0;
	for (int i = 0; i < a.len; i++) {
		int temp = a.d[i] * b + carry;
		c.d[c.len++] = temp % 10;
		carry = temp / 10;
	}
	while (carry != 0) {
		c.d[c.len++] = carry % 10;
		carry /= 10;
	}
	return c;
}

5.大整数除算（高精度/低精度）

ステップ毎に、前ステップの剰余に10を乗じてそのステップのビットを加算し、仮の被除数を得て除数と比較し、除算が足りなければそのビットの商は0、除算が足りれば商は対応する商、剰余は対応する剰余となり、最後に減算と同様に上位の0を処理する

bign divide(bign a, int b,int &r) {
	bign c;
	c.len = a.len;
	for (int i = a.len - 1; i >= 0; i--) {
		r = r * 10 + a.d[i];
		if (r < b)c.d[i] = 0;
		else {
			c.d[i] = r / b;
			r = r % b;
		}
	}
	while (c.len - 1 >= 1 && c.d[c.len - 1] == 0) {// 0， 
		c.len--;
	}
	return c;
}