高精度（High Precision）

   

       每每遇到“大明小明的A+B”，总有一股淡淡的忧伤．．．

 

加+

      在所有运算中，加法可以说是最简单的，但要实现得好，还是很考验功力的。

      我最原始的思维是，开两个字符数组分别保存两个加数，数组的每一个元素存储一个数字，（一开始为了节省空间，没有将字符数组转换为整型数组，发现操纵字符数组比操作整型数组更容易出错），为了计算方便，字符数组转换为整型数组，然后就是对应位的数字相加，逢十进一就可以了。

       核心部分代码如下：

    int i;
    for(i = 0; i < LEN; i++)
        sum[i] = a[i] + b[i];
    for(i = 0; i < LEN; i++)
        if(sum[i] >= 10)
        {
            sum[i] -= 10;
            sum[i+1] += 1;
        }
    return sum;

      这样的代码一写出来，虽然是正确的，但感觉就不是很好，空间的浪费在所难免，但是一位一位数字计算，速度会有点慢。

      改进：数组每个元素存储4位数字，上面代码只需把10改为10^4就行了（虽然只是轻描淡写般一改，却是很难想到的，当然可以取10^3，10^5，但只有10^4这个数字对乘法运算有很大的意义——10^4^2不至于超过int表示范围）

 

减-

      （这个和加法差不多，如果涉及到结果为负数，稍复杂，但就此略过）

 

乘*

      依然是模拟手算，乘数i位和被乘数j位相乘，放在结果的i+j位，然后处理进位就ok了。

    for(i=a.len-1; i>=0; i--)
        for(j = b.len-1 ; j >=0 ; j--)
        {
            m = a.v[i]*b.v[j];
            res.v[i+j] += m % base;
            res.v[i+j+1] += m / base;
            if(res.v[i+j] >= base)
            {
                res.v[i+j+1]+=res.v[i]/base;
                res.v[i+j]%=base;
            }
        }
    res.len = a.len+b.len+5;
    while(res.len > 0 && res.v[res.len-1] == 0)res.len--;
    return res;

 

除/

      除法相对来说是最难的。

      一开始我想：除法是一种匹配，是看被除数最多可以分成多少个除数，这样就又转到减法上去了，每减一次除数，商就加1，直到不能再减，商也就出来了。

      但是，很容易想像：当被除数极大而除数极小的时候那个速度啊，真让人心惊胆战。

      可以这样改进：不再一次一次减，而是从最高位开始，每次减去10^n倍除数，当被除数剩下的值不够减去10^n倍除数的时候，改为减去10^(n-1)倍除数……

      代码很繁琐：

#include<iostream>
#include<cstring>
#define M 200
using namespace std;
//单次减法操作
int Substract(int *p1, int *p2, int len1, int len2)
{
    int i;
    if(len1 <len2)
        return -1;
    if(len1==len2)
    {
        for(i=len1-1; i>=0; i--)
        {
            if(p1[i]>p2[i])break;
            else if(p1[i]<p2[i]) return -1;
        }
    }
    for(i=0; i<len1; i++)
    {
        p1[i]-=p2[i];
        if(p1[i]<0)
        {
            p1[i]+=10;
            p1[i+1]-=1;
        }
    }
    for(i=len1-1; i>=0; i--)
    {
        if(p1[i])return i+1;//找到最高位第一个不为0
    }
    return 0;
}

int main()
{
    char a1[M],a2[M];
    int b1[M],b2[M],result[M];
    while(cin >> a1 >> a2 )
    {
        memset(b1,0,sizeof(a1));
        memset(b2,0,sizeof(a2));
        memset(result,0,sizeof(result));
        int len1 = strlen(a1);
        int len2 = strlen(a2);
        int i,j;
        for(j=0,i=len1-1; i>=0; i--)
            b1[j++]=a1[i]-'0';
        for(j=0,i=len2-1; i>=0; i--)
            b2[j++]=a2[i]-'0';
        if(len1<len2)
        {
            cout << "0\n"<< endl;
            continue;
        }
        int nTimes = len1-len2;
        if(nTimes>0)
        {
            for(i=len1-1; i>=nTimes; i--)
                b2[i]=b2[i-nTimes];
            for(; i>=0; i--)
                b2[i]=0;
            len2=len1;
        }
        for(j=0; j<=nTimes; j++)
        {
            int nTemp;
            //一直减到不够减为止
            //先减去若干个 a2×(10 的 nTimes 次方)，
            //不够减了，再减去若干个 a2×(10 的 nTimes-1 次方)，......
            while((nTemp = Substract(b1, b2+j, len1, len2-j)) >= 0)
            {
                len1 = nTemp;
                result[nTimes-j]++; //每成功减一次，则将商的相应位加1
            }
        }
        //输出部分
     for(i=M-1; (i>=0)&&(result[i]==0); i--);
        if(i>=0)
        {
            for(; i>=0; i--)
            {
                cout << result[i];
            }
        }
        else
        {
            cout << "0";
        }
        cout << endl;
    }
    return 0;
}

 

      至此，+-*/都完成了！！！确实值得庆祝，仔细想想，又悲从中来...

 

      加减乘除彼此之间不是相互独立的，而自己却没有利用好已经已完成的功能去实现未完成的功能，导致代码臃肿不堪，难成模版。要实现除法其实可以借助已经实现的乘法和加法。

 

 

做成模版吧

   

       C++提供了重载运算符的契机，再自定义一个bint类型，那就完胜了。自己又重写了一遍高精度，虽然比起以前有所进步，但是，看到“神的代码”，又感伤了。（搬一笑话来自虐：一菜鸟和老牛去实现同一个功能。老牛很神气地说：你的代码运行比我的快吗？菜鸟不以为然地回答：你的代码有我的长吗？）

 

      （代码有点长，贴于博文最后）

 

 

高精度小数

 

      我的思路：把小数分成整数部分和小数部分分别处理，然后处理小数进位情况，再处理整数部分。

      想着挺简单的，但写过之后会发现，高精度小数是最令人神伤的。进位的处理，前导零、末尾零的处理都要比整数来得精确。以下是自己曾经遇到的bug：

      1.   1.1 + 0.9 = 2.     （小数点没判断好）

      2.   0.1 + 0.2 = .3     （自己任性地把所有前导0都消掉了）

      3.   0.5 + 0.6 = 0.1   （小数部分和整数部分没有衔接好）

      4.   0.01 + 0.09 = 0.10  （末尾0没处理）

      

 

总结：

 

      以前总依赖java提供的BigDecimal和BigInteger类，自己却从没有真正去思考去动手实现，后来这两个类用着用着，自己感到特不爽，不管哪个运算，都得用一个函数去完成，哪有运算符号来得直观。所以一怒之下，就敲开了。

      这是一门数字控制艺术，必须全神贯注，将一个个数打散再重新组合。差之毫厘，将谬以千里。

      还是非常兴奋能沉下心写几遍高精度代码并基本完成。虽然与神的代码差距颇大，不过有差距才有进步。但是，什么更能让自己兴奋呢？

                    上面一个是自己写的高精度小数，下面一个是用java的BigDecimal类

 

       虽然我代码比较长，但是我占用空间小，运行速度快！吼吼~~~

    

 

 

高精度小数：

 

#include<iostream>
#define M 500
using namespace std;
int main()
{
    string s1,s2;
    while(cin >> s1 >> s2)
    {
        int d1[M]= {0},g1[M]= {0},d2[M]= {0},g2[M]= {0},rd[M+10]= {0},rg[M+10]= {0};
        int i1=s1.find('.');
        int i2=s2.find('.');
        if(i1==-1)//要是输入的是整数，自己添加小数点吧
     {
            s1+=".0";
            i1=s1.find('.');
        }
        if(i2==-1)
        {
            s2+=".0";
            i2=s2.find('.');
        }
        int i,j,k1,k2;
        for(k1=0,i=i1+1; s1[i]!='\0'; i++,k1++)
            d1[k1] = s1[i]-'0';
        for(k2=0,i=i2+1; s2[i]!='\0'; i++,k2++)
            d2[k2] = s2[i]-'0';
        int len = max(k1,k2);
        for(i=0; i<len; i++)
            rd[i]=d1[i]+d2[i];
        for(j=i-1; j>=0; j--)
            if(rd[j]>=10)
            {
                rd[j]-=10;
                if(j!=0)
                    rd[j-1]++;
                else rg[0]++;
            }
        for(k1=0,i=i1-1; i>=0; i--,k1++)
            g1[k1]=s1[i]-'0';
        for(k2=0,i=i2-1; i>=0; i--,k2++)
            g2[k2]=s2[i]-'0';
        len = max(k1,k2);
        for(i=0; i<len; i++)
            rg[i]+=(g1[i]+g2[i]);
        for(i=0; rg[i]!=0; i++)
            if(rg[i]>=10)
            {
                rg[i]-=10;
                rg[i+1]++;
            }
        for(i=M+9; i>=0; i--)if(rg[i]!=0)break;
        for(j=i; j>0; j--)cout<<rg[j];
        cout<<rg[0];
        for(i=M+9; i>=0; i--)
            if(rd[i]!=0)
            {
                j=i;
                break;
            }
        if((i+1)==0)
        {
            cout<<endl;
            continue;
        }
        cout<<".";
        for(i=0; i<=j; i++)cout<<rd[i];
        cout << endl;
    }
    return 0;
}

 

大数模版：

#include<stdio.h>
#include<string.h>
const int base=10000; // base^2 fit into int
const int N=1000;//the length to offer
struct bint
{
    int len,v[N];
    bint(int r=int())//struct constructor. initialization necessary。
    {
        //with not initialze the v[0],I spend 3 more hours debugging this program
        //why it's so small but so important?
        //For it has effect on the case where cast int 0 to bint 0 ; or v[0] would be an uncertain result
        for(len=0,memset(v,0,N*sizeof(int)); r>0; r/=base)v[len++]=r%base;
    }
    bint& operator = (const bint& a)
    {
        memcpy(this,&a,(a.len+1)*sizeof(int));
        return *this;
    }
};

bool operator < (const bint& a,const bint& b)
{
    //神的代码
    int i;
    if (a.len != b.len) return a.len < b.len;
    for (i = a.len - 1; i >= 0 && a.v[i] == b.v[i]; i--);
    return i < 0 ? 0 : a.v[i] < b.v[i];
    /*我的代码 same idea, different code length 
    if(a.len<b.len)return 1;
    else if(a.len>b.len)return 0;
    else
    {
        int i;
        for(i=a.len-1; i>=0; i--) //！don't set i to a.len
        {
            if(a.v[i]<b.v[i])return 1;
            else if(a.v[i] > b.v[i])return 0;
            else continue;
        }
        if(i==-1)return 0;
    }
    return 0;*/
}
bool operator <= (const bint& a,const bint& b)
{
    return !(b<a);
}
bint operator - (const bint& a,const bint& b)
{
    //神的代码
    bint res;
    int i, cy = 0;
    for (res.len = a.len, i = 0; i < res.len; i++)
    {
        res.v[i] = a.v[i] - cy;
        if (i < b.len) res.v[i] -= b.v[i];
        if (res.v[i] < 0) cy = 1, res.v[i] += base;
        else cy = 0;
    }
    while (res.len > 0 && res.v[res.len - 1] == 0) res.len--;
    return res;
    /*我的代码 it works
    bint res;
    int i;
    for(i=0,res.len=a.len; i<res.len; i++)
        res.v[i]=a.v[i]-b.v[i];
    for(i=0; i<res.len; i++)
        if(res.v[i]<0)
        {
            res.v[i]+=base;
            res.v[i+1]--;
        }
    while (res.len > 0 && res.v[res.len - 1] == 0) res.len--;
    return res;*/
}
bint operator + (const bint& a,const bint& b)
{
    //神的代码
    bint res;
    int i, cy = 0;
    for (i = 0; i < a.len || i < b.len || cy > 0; i++)
    {
        if (i < a.len) cy += a.v[i];
        if (i < b.len) cy += b.v[i];
        res.v[i] = cy % base;
        cy /= base;
    }
    res.len = i;
    return res;
/*我的代码，lots of bugs
    bint sum;
    memset(&sum,0,sizeof(bint));
    int i;
    for(i=0; a.v[i]!=0||b.v[i]!=0; i++)//这里不应该用v[]是否等于0来判断，可以用N，但用len属性可以更快更准确
        sum.v[i]=a.v[i]+b.v[i];
    sum.len = i;
    for(i = 0 ; i<sum.len; i++)
        if(sum.v[i]>=base)
        {
            sum.v[i]-=base;
            sum.v[i+1]+=1;
        }
    return sum;
*/

}
bint operator *(const bint& a,const bint& b)
{
    //神的代码
    bint res;
    res.len=0;
     if (0 == b.len)
    {
        res.v[0] = 0;
        return res;
    }
    memset(&res,0,sizeof(bint));
    int i,j,t;
    for(i=0; i<a.len; i++)
    {
        for(j=t=0; j<b.len||t>0; j++,t/=base)
        {
            t+=a.v[i]*b.v[j];
            if(i+j<res.len)t+=res.v[i+j];
            if(i+j>=res.len)res.v[res.len++] = t % base;
            else res.v[i+j] = t % base;
        }
    }
    return res;
    /*我的代码
    for(i=a.len-1; i>=0; i--)
        for(j = b.len-1 ; j >=0 ; j--)
        {
            m = a.v[i]*b.v[j];
            res.v[i+j] += m % base;
            res.v[i+j+1] += m / base;
            if(res.v[i+j] >= base)
            {
                res.v[i+j+1]+=res.v[i]/base;
                res.v[i+j]%=base;
            }
        }
    res.len = a.len+b.len+5;
    while(res.len > 0 && res.v[res.len-1] == 0)res.len--;
    */
}

bint operator / (const bint& a,const bint& b)
{
    //神的代码，自己还写不出除法
    bint res,mod;
    memset(&res,0,sizeof(bint));
    if(a.len<b.len)
        return res;
    mod.v[0]=mod.len=0;
    int rt,lt,mid,i;
    for(i = a.len-1 ; i >= 0;i--) //！防越界
    {

        mod = mod * base + a.v[i];write(mod);
        for(lt = 0,rt = base - 1 ; lt < rt;)
        {
            mid = ( lt +rt+ 1) / 2; //二分加速
            if(b * mid <= mod) lt = mid;
            else rt = mid -1;
        }
        res.v[i] = lt;
        mod = mod - b * lt;
    }
    res.len = a.len;
    while(res.len > 0 && res.v[res.len - 1]==0)res.len--;
    return res;//return mod 就是取模运算
}

bint operator %(const bint& a,const bint& b) //almost the same code in operator /
{
    bint mod;
    mod.v[0]=mod.len=0;
    int rt,lt,mid;
    for(int i = a.len-1 ; i >= 0; i--) //！越界问题
    {
        mod = mod * base + a.v[i];
        for(rt = base - 1, lt = 0; lt < rt;)
        {
            mid = (rt + lt + 1) / 2; //二分加速
            if(b * mid <= mod) lt = mid;
            else rt = mid -1;
        }
        mod = mod - b * lt;
    }
    return mod;
}
bool read(bint& a,char buf[])
{
    if(scanf("%s",buf)!=1)return 0;
    memset(&a,0,sizeof(bint));//先初始化为0，不然当输入0的时候，a的值不被覆盖
    if(buf[0] == '0' &&  buf[1]=='\0')return 1;
    int w,u,len=strlen(buf);
    for(w=1,u=0; len;)
    {
        u += (buf[--len]-'0') * w;
        if(w*10 == base)
        {
            a.v[a.len++] = u;
            u = 0;
            w = 1;
        }
        else w*=10;
    }
    if(w!=1)a.v[a.len++]=u;
    return 1;
}

void write(const bint& a)
{
    printf("%d",a.len==0?0:a.v[a.len-1]);
    for(int i=a.len-2; i>=0; i--)
        printf("%04d",a.v[i]);
    printf("\n");
}

      

    神的代码总能令人赏心悦目，isn't it ?