C++大整数8位乘法

默认分类 | 2020-02-26 15:06:12 | 阅读 1059 次 | 评论(0)

分段多位数乘法4千乘以4千与4千乘以8位的原则是一样的,从左到右相乘,最高位相乘后,往后位的进位与前位相加。不想再设计了,这里只做描述和一个8位相乘的代码例子记录,估计的虽说堪舆傅里叶变换快速乘法媲美,还是觉得稍逊一点。同样的道理可用加法、减法、除法,其重点就是对进位用加法进行处理,而一次可以处理多位,受数据类型位数的限制,只能取其位数的一半-1位作为乘法,加法、减法、除法则可达18位推理的位数。
从低位往高位算也是一样的原则,(有一点区别就是要让进位暂存,等运算完成后再用加法计算进位。)从程序写作来说,从高位往低位进行运算写程序比较方便。
说白了就是传统的算法把多位数当作1位数看待即可,原来的模拟传统算法程序稍加修改就可以了,不过还是要注意对0的处理。
 
使用数值数组比使用字符串数组速度要快,避免了数据类型转换,当循环很多时,数据类型转来转去不容小觑。

void 字符转数值8位(char* 数, long long* 数组)
{
	long long 环 = strlen(数), 序 = 0, 积 = 0, 取 = 0;
	while (++序 <= 环)if ((序 % 8))
		积 = 积 * 10 + (数[序 - 1] - '0');
	else
		积 = 积 * 10 + (数[序 - 1] - '0'), 数组[取++] = 积, 积 = 0;
	数组[取++] = 积;
}
void 大整数8位乘法(char* 因数, char* 数)
{
	long long 模 = 10, 序 = 0, 环 = 0, 取 = 0, 零 = 0, 被乘数[9999]{0}, 乘数[9999]{0};
	string 补零 = "";
	字符转数值8位(因数, 被乘数);
	字符转数值8位(数, 乘数);
	取 = 被乘数[序];
	while (被乘数[序])
		if (取 /= 10)
			模 *= 10;
		else if (乘数[环])
			被乘数[序] *= 乘数[环], (序 ? 被乘数[序 - 1] += 被乘数[序] / 模, 被乘数[序] %= 模 : 0), ++环;
		else
			(被乘数[序] < 模 / 10 ? 零 = 模 / 10 : 0), 模 = 10, 取 = 被乘数[++序], 环 = 0;
		if (零)while (零 /= 10)if (被乘数[环])++环, 补零 += "0"; else 补零 += "0";
		序 = 0; while (被乘数[序])
			cout << (序 >= (环 - 1) ? 补零 : "") << 被乘数[序++]; cout << endl;
}

8位大数乘法.png (上传于2020-02-26 15:15:11)
8位大数乘法.png

8位大数乘法.png (上传于2020-02-26 15:15:39)
8位大数乘法.png

8位大数乘法.png (上传于2020-02-26 15:06:12)
8位大数乘法.png

8位大数乘法.png (上传于2020-02-26 15:08:13)
8位大数乘法.png




文章评论,共0条
游客请输入验证码