● 关于高精度 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: kaman (天外飞仙), 信区: ACMICPC
标  题: 关于高精度
发信站: 荔园晨风BBS站 (2005年03月05日10:34:44 星期六), 站内信件

    今早突然醒起答应过xsosx要贴些高精度相关的东西，临时整理了一下。因为现在不在

学校，资料不大完整，待回校再补全。

    说到高精度，在GDCPC之类的比赛中可算是一道美味小炒，吃多了不腻。因为这类题目

难度一般不大，拿分相对容易，不过其中也有对时间复杂度要求非常非常高的极品题，而

这类题目就要具体问题具体分析了，当然，这类问题不在本文讨论范围之内。

    下面简要介绍一下高精度运算中运用得比较多的加减乘除各法。

    1、加减：加减法没什么好讲的，用数组或字符串贮存起操作数，操作时用个循环处理

一下，注意对准位和进位（借位）就差不多了。

    有个办法可以提高一点速度，在32位int里，用数组处理高精度加减法的，可以用一个

数组单元贮存8位数来处理，当然这样只能达到常数级的优化。

    2、乘法：乘法相对复杂点。网上有段描述得简洁点的如下：

    ①、数据的接收和存储

    采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符
    串转化为数值，将A、B中的每一位数字分别存储在A、B两个数组中，最低位在第一
    个单元中。

    ②、确定积的位数

    设LA为A的位数，LB为B的位数，乘积的位数最多为LA+LB，最少为LA+LB-1。所以，
    乘积的位数! 上限为LA+LB。

    ③、算法

    首先计算被乘数与乘数的个位数字的乘积，把结果保存到积数组中，然后再用被乘
    数去乘以乘数的十位数字，把结果退一位加到积数组中。每加一次乘积结果就进行
    一次进位处理，其方法与加法中的进位处理一样。

    3、除法：除法的高精度运算可以细分为三种：

    一、求A÷B的精确值

    由于A和B都是计算机允许的显示精度，故A、B均可使用数值变量来接收与存储。A
    ÷B精确值有两种情况：

    ①、A能被B整除，没有余数。

    ②、A不能被B整除，对余数进行处理。首先，我们知道，在做除法运算时，有一个
    不变的量和三个变化的量，不变的量是除数，三个变化的量分别是：被除数、商和
    余数。做除法运算时，每次都是用被除数减去商与除数的积，如果所得余数不为零
    ，则将其扩大10倍再次作为被除数，继续试除，直至余数为零或达到要求的精确度
    为止。最后，必须对精确度的后一位求商，然后判断其值而四舍五入得出最后的结
    果。

    二、求多精度A÷单精度B的商和余数。

    ①、数据的接收和存储

    采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符
    串转化为数值，将A中的每一位数字分别存储在A数组中，最低位在第一个单元中。
    B则可以用一般的整数变量来接收和存储。

    ②、算法

    首先，我们知道，在做除法运算时，有一个不变的量和三个变化的量，不变的量是
    除数，三个变化的量分别是：被除数、商和余数。做除法运算时，每次都是用被除
    数减去商与除数的积，如果所得余数不为零，则将其扩大10倍再次作为被除数，继
    续试除，直至余数为零或达到要求的精确度为止。

    三、求多精度A÷多精度B的商和余数。

    ①、数据的接收和存储

    采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符
    串转化为数值，将A、B中的每一位数字分别存储在A和B数组中，最低位在第一个单
    元中。

    ②、算法

    可以用减法代替除法运算：不断比较A[1..n]与B[1..n]的大小，如果A[1..n]>=
    B[1..n]，商C[1..n]+1→C[1..n]，然后就是一个减法过程：A[1..n]-B[1..n]→
    A[1..n]。由于简单的减法速度太慢，故必须进行优化。设置一个位置值J，当
    A[1..n]>B[1..n]时。B[1..n]左移→B[0..n]，j:=j+1，即令B[1..n]增大10倍。这
    样就减少了减法的次数。当j>0且A[1..n].n]时，B[0..n]右移→B[0..n]，j:=j-1
    ，即令B[1..n]缩小10倍。

    最后说说上一年GDCPC中唯一的一题高精度题目，

    题目主要是给出两个高精度二进制数，求它们的最大公约数（结果用二进制表示）

    当时这也算是最终成绩的其中一条分水岭，不过AC过UVA的128题的做这题应该不会花

    吹灰之力，当然，还要先读懂比赛中的英文原题。

        以上是处理高精度运算时的一般做法，下星期在CASE也有关于高精度的相关专题

    训练。有兴趣的同学可以前往讨论，其中还会涉及其它的算法的讨论。

        好，写到这就先算了，头痛虽然好了，不过还是先不要动太多脑了，呵呵。

--
Long long ago,there is a hero stand at the edge of the land,a sword in
hand.......
       ︵～`   ╭)                          ▁▁
      ︸ヾ)    (╯                        ▕天外▏
      ゞ7(  ︵  ))                        ▕飞仙▏
       ╰ ︶へ︶╯                          ▔▔
       ヅ╯  ジ〉
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 219.131.209.183]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店