2014/06/14
6,039
§前言
高精度计算是算法较为基础的一部分。
由于现有计算编程语言的数据类型限制,对于大数据的存储能力与计算能力有限。故在需要进行大数据运算时,我们采用非常规的方法代替编程语言内置的算法,来进行计算。
大数据计算的一般思路为:将大数据拆分成多个小数据,使用编辑语言能够计算的小数据进行计算,再将小数据合并成大数据。
§大数加法
从自然数的加法开始学习。
首先要解决的是数据的存储。由于C++语言的长整型存储位数有限,存储大数据会出现溢出错误,我们将大数当作一个字符串进行存储。
然后将字符串分解成可以运算的小数,按照数据运算的一般规则来进行计算处理。
最后将多个小数组合成大数表示。
则对于大数加法有如下步骤:
- 存储。使用字符串存储大数,将大数从高位到低位依次存放于字符数组中。这符合数据表示习惯
- 转换。将字符数组从低位到高位依次转换成整型数字,并按下标从大到小依次存入整型数组(即将大数据的最低位向右对齐)。这符合数据计算习惯。
- 计算。按下标从大到小(即大数据从低位到高位),依次进行单个整型的加法运算。如果满10则向高一个进1
- 转换并存储。按下标的从小到大,将整型数组元素依次存入字符数组。