高精度计算之大数据相加

§前言

高精度计算是算法较为基础的一部分。

由于现有计算编程语言的数据类型限制，对于大数据的存储能力与计算能力有限。故在需要进行大数据运算时，我们采用非常规的方法代替编程语言内置的算法，来进行计算。

大数据计算的一般思路为：将大数据拆分成多个小数据，使用编辑语言能够计算的小数据进行计算，再将小数据合并成大数据。

§大数加法

从自然数的加法开始学习。

首先要解决的是数据的存储。由于C++语言的长整型存储位数有限，存储大数据会出现溢出错误，我们将大数当作一个字符串进行存储。

然后将字符串分解成可以运算的小数，按照数据运算的一般规则来进行计算处理。

最后将多个小数组合成大数表示。

则对于大数加法有如下步骤：

• 存储。使用字符串存储大数，将大数从高位到低位依次存放于字符数组中。这符合数据表示习惯

• 转换。将字符数组从低位到高位依次转换成整型数字，并按下标从大到小依次存入整型数组(即将大数据的最低位向右对齐)。这符合数据计算习惯。

• 计算。按下标从大到小(即大数据从低位到高位)，依次进行单个整型的加法运算。如果满10则向高一个进1

• 转换并存储。按下标的从小到大，将整型数组元素依次存入字符数组。

过程比较简单。具体可参考代码和注释

string numAdd(const string& strA, const string& strB)
{

	//转换
	//////////////////////////////////////////////////////////////////////////
	int nLenA = strA.length();
	int nLenB = strB.length();

	//数据最大位数
	int nLenSum = nLenA > nLenB ? nLenA : nLenB;
	//由高位相加后可能会向前进一位
	++nLenSum;

	size_t sz = nLenSum * sizeof(short);

	//给分配相同大小(位数)的数据，方便对齐计算
	short* pSum = (short*)malloc(sz); memset(pSum,0,sz); //计算结果数组
	short* pA = (short*)malloc(sz); memset(pA,0,sz);	//加数A数组
	short* pB = (short*)malloc(sz); memset(pB,0,sz);	//加数B数组

	//按数组下标从大到小(数据位数从低到高)转换。
	for (int i = nLenA-1, j = nLenSum - 1; i>=0; i--,j--)
	{
		pA[j] = strA[i] - '0';
	}

	for (int i = nLenB-1, j = nLenSum - 1; i>=0; i--,j--)
	{
		pB[j] = strB[i] - '0';
	}

	//计算
	//////////////////////////////////////////////////////////////////////////
	for (int j = nLenSum - 1; j > 0; j--)
	{
		//计算
		pSum[j] += (pA[j] + pB[j])%10;
		//向前进位
		pSum[j-1] += (pA[j] + pB[j])/10;
	}

	//转换
	//////////////////////////////////////////////////////////////////////////
	char* pszSum  = (char*)malloc(sizeof(char) * (nLenSum + 1));

	int nFlag = 0;
	//去除前置0
	for (; nFlag<nLenSum; nFlag++)
	{
		if(pSum[nFlag] != 0)
			break;
	}

	int nszFlag = 0;
	//转换
	for (; nFlag < nLenSum; nFlag++, nszFlag++)
	{
		pszSum[nszFlag] = pSum[nFlag] + '0';
	}

	pszSum[nszFlag] = '\0';

	string strSum(pszSum);

	//释放资源
	free(pA);
	free(pB);
	free(pSum);
	free(pszSum);

	return strSum;
}