6.大数乗算

32ビットワード長のマシンでは、約20億を超えるとintタイプでは表現できませんが、int 64タイプを選択することができますが、どのように拡張しても、固定された整数タイプには常に表現の限界があります!スーパー大整数を正確に演算するとしたら?1つの簡単な方法は、既存のタイプのみを使用するが、大きな整数の演算をいくつかの小さな整数の演算、すなわち「ブロック法」に解くことである.
ブロック乗算の原理を図【1.jpg】に示す.大数を多段(ここでは2段)の小数に分け、小数の複数回の演算の組み合わせで大数を表すことができます.intの荷重能力に応じて小ブロックの大きさを規定することができ、例えばintを2段に分けると、小ブロックは10000を上限値とすることができる.なお、小ブロックは縦加算後、キャリー補正が必要である.以下のコードはブロック乗算の原理(乗数,被乗数ともに2段に分ける)を示す.

#include

void bigmul(int x, int y, int r[])
{
	int base = 10000;
	int x2 = x / base;
	int x1 = x % base; 
	int y2 = y / base;
	int y1 = y % base; 

	int n1 = x1 * y1; 
	int n2 = x1 * y2;
	int n3 = x2 * y1;
	int n4 = x2 * y2;

	r[3] = n1 % base;
	r[2] = n1 / base + n2 % base + n3 % base;
	r[1] = n3/base+n2/base+n4%base; //   r[1] = ________; 
	r[0] = n4 / base;
	
	r[1] +=r[2]/base;              //   r[1] += ________; 
	r[2] = r[2] % base;
	r[0] += r[1] / base;
	r[1] = r[1] % base;
}


int main(int argc, char* argv[])
{
	int x[] = {0,0,0,0};

	bigmul(87654321, 12345678, x);

	printf("%d%d%d%d
", x[0],x[1],x[2],x[3]);

	return 0;
}