C++ 大数乘法

C++ 大数乘法 分别包括 普通大数乘法、分治法大数乘法、改进的分治法大数乘法。

#include
#include
#include
#include
#include
using namespace std;

int randint(int a, int b);
int* rand_num(int n);
void show_num(int* c, int n);
void multiply_normal(int* c1, int* c2, int n, int flag);
void multiply_n(int* c1, int* c2, int n, int flag);
int bit_number(int* c, int n);
int* high_num_2(int* c, int n);
int* low_num_2(int* c, int n);
void add_list(int* c1, int* c2, int n, int m);
int* multiply_partition(int* c1, int* c2, int n);
int* x_y(int c1, int c2);
void multiply_p(int* c1, int* c2, int n, int f);
void sub_list(int* c1, int* c2, int n, int m);

int* multiply_partition_enhanced(int* c1, int* c2, int n);
void multiply_p_e(int* c1, int* c2, int n, int f);

int main()
{

	cout << "输入数字位数 n = ";
	int n;
	cin >> n;
	cout << endl;
	//生成两个随机 n 位数
	int* c1 = NULL;
	int* c2 = NULL;
	c1 = rand_num(n);
	c2 = rand_num(n);
	//show_num(c1, n);
	//show_num(c2, n);
	//cout <<"正确乘积： " << bit_number(c1, n) * bit_number(c2, n) << endl;
	//int a1[] = { 1, 2, 3, 4, 5, 6 };
	//int a2[] = { 3,6,8 };
	//show_num(a1, 6);
	//show_num(a2, 3);
	//sub_list(a1, a2, 3, 1);
	//show_num(a1, 6);
	cout << "是否显示乘积结果？ 是：1； 否：0  ";
	int flag = 0;
	cout<< "flag = ";
	cin >> flag;
	cout << endl;

	multiply_n(c1, c2, n, flag);
	multiply_p(c1, c2, n, flag);
	multiply_p_e(c1, c2, n, flag);

	delete[]c1;
	delete[]c2;
	return 0;
}



int randint(int a, int b)
{
	random_device rd;
	default_random_engine eng(rd());
	uniform_int_distribution distr1(a, b);//均匀分布的方式产生随机数
	return distr1(eng);
}

int* rand_num(int n)
{
	int* c = new int[n];
	for (int i = 0; i < n - 1; i++)
	{
		c[i] = randint(0, 9);
	}
	c[n - 1] = randint(1, 9);
	return c;
}

void show_num(int* c, int n)
{
	
	if (c[n - 1] != 0)
	{
		cout << c[n - 1];
	}
	for (int j = n - 2; j >= 0; j--)
	{
		cout << c[j];
	}
	cout << endl;
}

void multiply_normal(int* c1, int* c2, int n, int flag)
{
	clock_t start = clock();      //获取当前系统时间

	int* c = new int[2 * n];
	int x = 0;
	for (int i = 0; i < 2 * n; i++)
	{
		c[i] = 0;
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			x = c[i + j] + c1[i] * c2[j];
			c[i + j] = x % 10;
			c[i + j + 1] += x / 10;
		}
	}

	clock_t end = clock();
	double programTimes = ((double)end - start) / CLOCKS_PER_SEC;
	if (flag)
	{
		cout << "Result." << setw(26) << "普通大数乘法乘积：";
		show_num(c, 2 * n);
	}
	cout << "Time." << setw(28) << "普通大数乘法时间：" << programTimes << " 秒" << endl << endl;
	delete[]c;
}

void multiply_n(int* c1, int* c2, int n, int flag)
{
	multiply_normal(c1, c2, n, flag);
}

int bit_number(int* c, int n)
{
	int x = 0;
	for (int i = 0; i < n; i++)
	{
		x += c[i] * pow(10, i);
	}
	return x;
}


int* x_y(int c1, int c2)
{
	int x = 0;
	int* c = new int[2];
	x = c1 * c2;
	c[0] = x % 10;
	c[1] = x / 10;
	return c;
}

int* high_num_2(int* c, int n)
{
	int* k = new int[n / 2];
	for (int i = 0; i < n / 2; i++)
	{
		k[i] = c[i + n / 2];
	}
	return k;
}

int* low_num_2(int* c, int n)
{
	int* k = new int[n / 2];
	for (int i = 0; i < n / 2; i++)
	{
		k[i] = c[i];
	}
	return k;
}

void add_list(int* c1, int* c2, int n, int m) //n为c2的长度，m为c2的进位
{
	int x = 0;
	for (int i = 0; i < n; i++)
	{
		x = c1[i + m] + c2[i];
		c1[i + m] = x % 10;
		if (x / 10 != 0)
			c1[i + m + 1] += x / 10;
	}
}

int* multiply_partition(int* c1, int* c2, int n)
{
	if (n == 1)
	{
		return x_y(c1[0], c2[0]);
	}
	int* x = NULL;
	int* y = NULL;
	if (n % 2 != 0)
	{
		x = new int[n + 1];
		y = new int[n + 1];
		for (int i = 0; i < n; i++)
		{
			x[i] = c1[i];
			y[i] = c2[i];
		}
		x[n] = 0;
		y[n] = 0;
		n += 1;
	}
	else
	{
		x = new int[n];
		y = new int[n];
		for (int i = 0; i < n; i++)
		{
			x[i] = c1[i];
			y[i] = c2[i];
		}
	}
	int* a1 = high_num_2(x, n);
	int* a0 = low_num_2(x, n);
	int* b1 = high_num_2(y, n);
	int* b0 = low_num_2(y, n);
	int* p = multiply_partition(a1, b1, n / 2);
	int n_p = p[n - 1] == 0 ? n - 1 : n;
	int* q = multiply_partition(a1, b0, n / 2);
	int n_q = q[n - 1] == 0 ? n - 1 : n;
	int* r = multiply_partition(a0, b1, n / 2);
	int n_r = r[n - 1] == 0 ? n - 1 : n;
	int* s = multiply_partition(a0, b0, n / 2);
	int n_s = s[n - 1] == 0 ? n - 1 : n;

	delete[]x;
	delete[]y;
	delete[]a1;
	delete[]a0;
	delete[]b1;
	delete[]b0;

	int* c = new int[2 * n];
	for (int i = 0; i < 2 * n; i++)
	{
		c[i] = 0;
	}
	add_list(c, p, n_p, n);
	add_list(c, r, n_r, n / 2);
	add_list(c, q, n_q, n / 2);
	add_list(c, s, n_s, 0);

	delete[]p;
	delete[]q;
	delete[]r;
	delete[]s;

	return c;
}

void multiply_p(int* c1, int* c2, int n, int flag)
{
	clock_t start = clock();      //获取当前系统时间
	int* c = multiply_partition(c1, c2, n);
	clock_t end = clock();
	double programTimes = ((double)end - start) / CLOCKS_PER_SEC;

	if (flag)
	{
		cout << "Result." << setw(26) << "分治法大数乘法乘积：";
		show_num(c, 2 * n);
	}
	cout << "Time." << setw(28) << "分治法大数乘法时间：" << programTimes << " 秒" << endl << endl;
	delete[]c;
}


void sub_list(int* c1, int* c2, int n, int m)
{
	for (int i = 0; i < n; i++)
	{
		if (c1[i + m] < c2[i])
		{
			c1[i + m] = c1[i + m] + 10 - c2[i];
			c1[i + m + 1] -= 1;
		}
		else
			c1[i + m] -= c2[i];
	}
	if (c1[n + m] < 0)
	{
		for (int i = 0;;i++)
		{
			c1[n + m + i] += 10;
			c1[n + m + i + 1] -= 1;
			if (c1[n + m + i + 1] >= 0)
				break;
		}
	}

}

int* multiply_partition_enhanced(int* c1, int* c2, int n)
{
	if (n == 1)
	{
		return x_y(c1[0], c2[0]);
	}
	int* x = NULL;
	int* y = NULL;
	if (n % 2 != 0)
	{
		x = new int[n + 1];
		y = new int[n + 1];
		for (int i = 0; i < n; i++)
		{
			x[i] = c1[i];
			y[i] = c2[i];
		}
		x[n] = 0;
		y[n] = 0;
		n += 1;
	}
	else
	{
		x = new int[n];
		y = new int[n];
		for (int i = 0; i < n; i++)
		{
			x[i] = c1[i];
			y[i] = c2[i];
		}
	}
	int* a1 = high_num_2(x, n);
	int* a0 = low_num_2(x, n);
	int* b1 = high_num_2(y, n);
	int* b0 = low_num_2(y, n);

	int* p = multiply_partition_enhanced(a1, b1, n / 2);
	int n_p = p[n - 1] == 0 ? n - 1 : n;
	int* a2 = new int[n / 2 + 1];
	int* b2 = new int[n / 2 + 1];
	for (int i = 0; i < n / 2 + 1; i++)
	{
		a2[i] = 0;
		b2[i] = 0;
	}
	add_list(a2, a1, n / 2, 0);
	add_list(a2, a0, n / 2, 0);
	add_list(b2, b1, n / 2, 0);
	add_list(b2, b0, n / 2, 0);

	int m = n / 2;
	if (a2[n / 2] != 0 || b2[n / 2] != 0)
	{
		m = n / 2 + 1;
	}
	int* q = multiply_partition_enhanced(a2, b2, m);	// 如果 n = 2, m = 1 or 2  66*77		12*14 = 168 nq = 3		n / 2 = 1
	int n_q = q[2 * m - 1] == 0 ? 2 * m - 1 : 2 * m;
	int* s = multiply_partition_enhanced(a0, b0, n / 2);
	int n_s = s[n - 1] == 0 ? n - 1 : n;
	delete[]x;
	delete[]y;
	delete[]a1;
	delete[]a0;
	delete[]b1;
	delete[]b0;
	delete[]a2;
	delete[]b2;

	int* c = new int[2 * n + 1];
	for (int i = 0; i < 2 * n + 1; i++)
	{
		c[i] = 0;
	}
	add_list(c, p, n_p, n);
	add_list(c, q, n_q, n / 2);
    add_list(c, s, n_s, 0);
	sub_list(c, p, n_p, n / 2);
	sub_list(c, s, n_s, n / 2);

	delete[]p;
	delete[]q;
	delete[]s;

	return c;
}

void multiply_p_e(int* c1, int* c2, int n, int flag)
{
	clock_t start = clock();      //获取当前系统时间
	int* c = multiply_partition_enhanced(c1, c2, n);
	clock_t end = clock();
	double programTimes = ((double)end - start) / CLOCKS_PER_SEC;

	if (flag)
	{
		cout << "Result." << setw(26) << "改进的分治法大数乘法乘积：";
		show_num(c, 2 * n);
	}
	cout << "Time." << setw(28) << "改进的分治法大数乘法时间：" << programTimes << " 秒" << endl << endl;
	delete[]c;
}