一种C++中大数乘法程序

孔柱新

摘  要： 程序模拟了两数相乘的人工竖式算法，利用C++标准模板库中string类接收键盘输入的大数，并用标准模板库vector类存储大数和相乘，解决了基本数据类型表示大数位数有限的问题。

关键词： C++; 大数; string; vector

中图分类号：TP312          文献标识码：A     文章编号：1006-8228（2022）03-81-03

Abstract： The program simulates the artificial vertical calculation method of multiplication of two numbers， using the string class of C++ standard template library to receive the large number of keyboard input. The vector class of standard template library is used to store large numbers and multiply them， which solves the digits limiting problem for the basic data type to represent the large number.

Key words： C++; large number; string; vector

0 引言

随着科技的发展，计算机系统的性能越来越高，给人们的工作和生活带来了便利。虽然是如此，但计算机所能表示的数据范围还是有限制的。C++中long long的最大值[1]：9223372036854775807，long long的最小值：-9223372036854775808;unsigned long long的最大值：18446744073709551615;大数超出了计算机系统基本数据类型所能表达的范围，例如有的数据可能有成百上千位，如果这样的数据相乘就超出了基本数据类型所能表达的范围。本文探讨了一种利用C++程序編写两个大整数相乘的算法，希望起到抛砖引玉的效果。

1 乘法原理

首先看看两数相乘的算法[2]，模拟人工计算时的方法，也就是列竖式相乘，从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加，得出最后结果。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。

我们以135*47为例来说明计算过程：

⑴ 先算135*7，7*5得到35个1，7*3得到21个10，7*1得到7个100，如表1是存储结果的数组形式。

⑵ 接下来算135*4，4*5得到20个10，4*3得到12个100，4*1得到4个1000，如表2。

⑶ 乘法过程完毕。接下来从a[0]开始向高位逐位处理进位问题。a[0]留下5，把3加到a[1]上，a[1]变为44 后，应留下4，把4 加到a[2]上……最终使得a里的每个元素都是1位数，结果就算出来了，是6345。