高精度计算之大数据相加
§前言
高精度计算是算法较为基础的一部分。
由于现有计算编程语言的数据类型限制，对于大数据的存储能力与计算能力有限。故在需要进行大数据运算时，我们采用非常规的方法代替编程语言内置的算法，来进行计算。
大数据计算的一般思路为：将大数据拆分成多个小数据，使用编辑语言能够计算的小数据进行计算，再将小数据合并成大数据。
§大数加法
从自然数的加法开始学习。
首先要解决的是数据的存储。由于C++语言的长整型存储位数有限，存储大数据会出现溢出错误，我们将大数当作一个字符串进行存储。
然后将字符串分解成可以运算的小数，按照数据运算的一般规则来进行计算处理。
最后将多个小数组合成大数表示。
则对于大数加法有如下步骤：
- 存储。使用字符串存储大数，将大数从高位到低位依次存放于字符数组中。这符合数据表示习惯
- 转换。将字符数组从低位到高位依次转换成整型数字，并按下标从大到小依次存入整型数组(即将大数据的最低位向右对齐)。这符合数据计算习惯。
- 计算。按下标从大到小(即大数据从低位到高位)，依次进行单个整型的加法运算。如果满10则向高一个进1
- 转换并存储。按下标的从小到大，将整型数组元素依次存入字符数组。
过程比较简单。具体可参考代码和注释
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
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; } |