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

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

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

0 引言

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

1 乘法原理

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

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

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

表1 135*7的结果

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

表2 135*4的结果

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

表3 135*47最终结果

2 string和vector

大数的位数超出了基本数据类型的表示范围，因此不能够用基本数据类型来表示。string 是C++标准库的一个重要的部分，主要用于字符串处理。可以使用输入输出流方式直接进行string[3]操作，也可以通过文件等手段进行string 操作。同时，C++的算法库对string 类也有着很好的支持，并且string 类还和c 语言的字符串之间有着良好的接口。其[ ]操作符支持对字符的读写。利用string 来接受键盘输入的任意位数的字符串，这就满足了大数的任意多位的要求，string默认存储的是字符串，故需要减去‘0’才能得到真实的数值。

Vector[4]是同一种类型的对象集合，能够容纳许多其他类型相同的元素，因此又被称为容器。与string相同vector 同属于STL(Standard Template Library，标准模板库)中的一种自定义的数据类型，可以广义上认为是数组的增强版。在使用它时，需要包含头文件vector，#include<vector>，vector容器与数组相比其优点在于它能够根据需要随时自动调整自身的大小以便容下所要放入的元素。此外，vector 也提供了许多的方法来对自身进行操作。如push_back[5]操作，vector尾部加入一个数据；reserve()操作则告诉vector容器应该预留多少个元素的存储空间。vector 在容量不足时会足倍的增加容量。insert()[6] 函数有以下三种用法：iterator insert(iterator loc,const TYPE &val)，在指定位置loc 前插入值为val 的元素，返回指向这个元素的迭代器；void insert(iterator loc,size_type num,const TYPE &val)，在指定位置loc前插入num 个值为val的元素；void insert(iterator loc,input_iterator start,input_iterator end)，在指定位置loc 前插入区间[start,end)的所有元素。