多精度计算
许剑伟 2006-10-31
一、多（高）精度数据表示法：
用字符型数组表示一个高精度的数，以下示范数据结构，左边为数组底端（或说内存底端），下表以底端高位（或说高端低位）权方式表示多精度数，反之，也可用底端低位（或说高端高位）方式表示多精度数。
数组脚标
0
1
2
3
4
5
对应位权
个位
10分位
100分位
1000分位
10的-4
10的-5
数组值
3
1
4
5
7
9
如上表所示，该数组表示的是3.14579。10分位的位权是0.1，100分位的位权是0.01。
二、使用中国小学算术教育指明的算法进行多精度四则运算。
（一）做乘法和加减法时，从建议最底位权处开始计算，这点很重要，不然做进位时会遇到一些麻烦。做除法时，从最高位权处开始计算。
（二）关于截断误差：用数组表示一个高精度数，仍然可能存在误差，由于数组位数有限，只好对小数5位以后的数做截断处理，从而产生误差，如数1/3=0.3333…. ，用上图数组表示为0.33333，总共6位精度（实有效数只有5个）。
（三）多精度算法。
1、多精度数加法（多对多加法）：逐位加法并做进位处理(取和与进位可同步处理，以提高速度)。
自从有了10进制等有效的数制问世之后，加法问题也随之得到有效的解决。人们通过九九加法表，很快的知道两个1位数的加法结果，如果是多位数，只需逐位相加并进位即可。
位权
个位
10分位
100分位
1000分位
10的-4
10的-5
数组1
3
1
4
5
7
9
数组2
6
6
5
8
2
2
数组结果
3+6=9
1+6=7
4+5=9
5+8=13
7+2=9
9+2=11
进位处理
9
8
0
4
0
1
2、多精度数与整数的乘法（1对多乘法）：逐位相乘并做进位处理。
这种法与加法差不多，但需要乘法口决表，对电脑而言，当然不需要口决表，它使用二进制计算(0和1)，所谓的口决只是有一个“乘数是1则结果是被乘数否则就是0”，这种乘法简单得不能再简单，如果是多位数乘法，则在相加之前要考虑移位。
令数组全部的值为0
位权
个位
10分位
100分位
1000分位
10的-4
10的-5
数组
3
1
4
5
7
9
整数
6
数组结果
3*6=18
1*6=6
4*6=24
5*6=30
7*6=42
9*6=54
进位处理
8(溢出1)
8
7
4
7
4
3、多精度数与整数的除法（多对1除法）：逐位除法并做余数处理(逐位求精)。
逐位求精算法可以比较完美的解决除数为整数(int类型)的问题，如果除数是一个高精度数，逐位求精算法不一定可行。
4、多精度数与多精度数的乘法：逐位相乘并做进位处理——硬乘法。
多位数与多位数的乘法要复杂很多。如果要考虑快速相乘，则会更加复杂。
这种算法是小学老师告诉我们的，那时教材里也给出这样的算法，该算法的明显好处是算法比较单，并且用笔和纸两个工具便可解决问题。然而离开了笔和纸，这种笔算与口算混合的算法的优势几乎完全失去，几乎成了最臭的乘法，远不如古代使用歌诀或珠算等方法，所以要在电脑中实现乘，需对算法稍做修改。小学算法主要问题在：每行都要作进位
处理，最后取总和时还要做进位处理，再次说，该算法占用至少了占用了N*N的空间（设两个乘数的位数都是N），做个10万位的二数相乘，可能把你的内存耗尽，再三，该算法总是从最最低位开始，乘法结果的最低位往往是要舍去的，我们却花了大量时间计算(如两个有效数字为5的数相乘，结果的精度也应该是5位，不是10位)，所以强硬将算法原原本本搬给电脑计算是很不科学的。
计算时请注意，按表格中示意纵向优先做乘法计算并取和进位，计算时从高端（底位权）开始，即第1轮在右边，这样你将不需要额外的数组空间，结果可直接填回原数组的相应位
置中，另外，这么做还可以很方便的做一次性纵列加法及进位，运算过程大大简化。原因很简单，第n位的值总是由乘数的第n1位和被乘数的第n2位相乘得到，且n1+n2=n+1，易得n1<=n且n2<=n，这就意未着要计算第n位的结果，需要的是n左边的数，不需要n右边的数，所以计算左边各位结果将不再需要当前位及其右边位的乘数与被乘数，当前位的空间可被利用。
这种算法的计算量为N*N/2，如果你进行全宽度完全乘法计算，其计算量为N*N。
乘法卷积
卷积过程就是交两两相乘后，同位权的取和，这个乘法过程与上述的纵列乘法计算相同
 
 
以下示例卷积过程
 
 
循环卷积(圆卷积)，循环卷积要做循环移位操作：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。