高精度

//array index   1 2 3 4 5 6 7 8 9
                5 4 3 2 1
            +   7 8 9 9
            -------------
                2 3 3 2 2
//jw            1 1 1 1

//array index是数组下标，jw代表进位

//array index       1  2  3  4  5  6  7  8  9  ...
                A   6  5  8
                B   5  2
                ----------------------------------
                    0  8  2  4
                       2  1  7  1
                ----------------------------------
                    0  0  4  1  2
                    
//array index       1  2  3  4  5  6  7  8  9  ...
                A   a1 a2 a3 a4
                B   b1 b2
                ----------------------------------
                C   c1 c2 c3 c4
                       c2 c3 c4 c5
//本例中未写出进位

void chengfa(int A[], int B[], int C[]){        //C=A*B
    int i,j;
    for(i=1; i<=B[0]; i++){                     //B[0]轮乘法
        int jw;                                 //进位 
        for(j=1, jw=0; j<=A[0]; j++){           //每轮按位乘A[0]次
            C[i+j-1]=C[i+j-1]+A[j]*B[i]+jw;     //错位相加
            jw=C[i+j-1]/10;                     //求进位
            C[i+j-1]%=10;                       //进位后，与10求余
        }
        C[i+A[0]]=jw;                           //存储最后一个进位
    }
    int len=A[0]+B[0];                          //最大可能位数 
    while(C[len]==0 && len>1)   len--;          //确定有效位数
    C[0]=len;
    return;
}
//使用方法
int main(){
    ...      
    chengfa(num1, num2, result);
    printNum(result);
    return 0;
}
五、高精度除低精度

//
被除数数位      当前位数字  过程被除数      过程除结果
i=6             1           1/23            商：0
i=5             1           11/23           商：0
i=4             3           113/23          商：4，余：21
i=3             0           210/23          商：9，余：3
i=2             5           35/23           商：1，余：12
i=1             6           126/23          商：5，余：11
//计算结果      商：4915， 余数：11
代码示例：

void chuDi(int A[], int B, int C[], int &yushu){    //A/B=C 余数：yushu
    int i, t;                                       //t为过程被除数
    for(i=A[0], t=0; i>=1; i--){                    //从被除数高位循环到低位
        t=t*10+A[i];                                //更新t
        C[i]=t/B;                                   //计算C[i]
        t%=B;                                       //更新t
    }
    yushu=t;                                        //计算完后t就是余数
    i=A[0];                                         //计算C有效位数
    while(C[i]==0 && i>1) i--;
    C[0]=i;
    return;
}
//使用方法
int main(){
    int num1[500];
    int num2;
    int shang[500];
    int yushu;
    getNum(num1);
    scanf("%d", num2);
    chuDi(num1, num2, shang, yushu);
    printNum(shang);
    count<<" "<<yushu;
    return 0;
}

六、高精度除高精度


思路

高精度除高精度是这几种运算中最难的一种。仍然可以模仿竖式的方式进行，过程有点儿麻烦。另一种办法是利用减法：被除数A-除数B，看看能减多少个，直到A<B，这时剪去的个数就是商，剩下的A就是余数。如果利用前面编写好的高精度减法jianfa()和compare()的话，实现起来岂不是很容易？可惜不是这样，假设被除数A的位数M与除数B位数N之差M-N很大，这个范围有可能从0～200，按照最大的情况200考虑，这意味着商值也是高精度数字，而你要减10^200次才能减完，这是一个天文数字。

所以，明白否？解决这个问题也很简单，我们不一个一个减，而是按照最大可能的数量级减，例如：12345/45：

//商的最大位数i=M-N+1，即4，设计一个 临时减数，减数后面补齐i-1个0，再进行减法
i=4     12345 < 45000   可以减0个   shang[4]=0      减后A：12345
i=3     12345 < 4500    可以减2个   shang[3]=2      减后A：3345
i=2     3345  < 450     可以减7个   shang[2]=7      减后A：195
i=1     195   < 45      可以减4个   shang[1]=4      减后A：15

//因shang[4]=0，故商的有效位数shang[0]--，为3
//结果  商为274，余数15

看明白了吗，这样的计算过程，仅仅减了2+7+4=13次，而非274次，可见一个一个减是绝对不靠谱的。下面提供了代码，注意：减法函数jianfa()被修改了，使得直接把结果存入A中，而不需要存在另一个数组C中，这是为了简化后面运算的缘故。

代码示例

void jianfa(int A[], int B[]){              //修改了的减法，使得直接在A数组上减
    int i;                                  //不再需要存在数组C，简化后面的运算
    for(i=1; i<=B[0]; i++){
        if(A[i]<B[i]){
            A[i+1]--;                       //向高位借1 
            A[i]+=10;                       //当前位+10 
        }
        A[i]-=B[i];                         //按位减 
    }
    if(i<A[0])  return;                     //计算有效位数
    else{                                
        while(A[i]==0 && i>=1)  i--;
        A[0]=(i==0)? 1 : i;
    }
    return;
}
                                            //shang=A/B, yushu为余数
bool chuGao(int A[], int B[], int shang[], int yushu[]){
    memset(shang, 0, sizeof(int)*300);      //初始化shang
    memset(yushu, 0, sizeof(int)*300);      //初始化yushu
    shang[0]=A[0]-B[0]+1;                   //商的最大数位 
    for(int i=shang[0]; i>=1; i--){         //从高位到低位开始计算商
        int jianshu[300];                   //构造要减的减数
        memset(jianshu, 0, sizeof(jianshu));
                                            //这个函数下面有解释
        memcpy(jianshu+i, B+1, sizeof(int)*B[0]);
        jianshu[0]=B[0]+i-1;                //确定减数的位数
        while(compare(A, jianshu)){         //通过循环减
            jian(A, jianshu);                     
            shang[i]++;                     //减去一个商的对应为+1
        }
    }
    if(shang[shang[0]]==0)  shang[0]--;     //判断商的最高位是否有效
    memcpy(yushu, A, sizeof(int)*300);      //A就是余数，把它完全复制给yushu
}

//使用方法
int main(){
    int num1[300];                          //数组A存储第1个数字信息 
    int num2[300];                          //数组B存储第2个数字信息
    int shang[300];
    int yushu[300];
    init(num1);
    init(num2);
    chuGao(num1, num2, shang, yushu);
    print(shang);
    printf(" ");
    print(yushu);
    return 0;
}

上面的代码中用到了memcpy()，该函数位于cstring头文件中，用于内存块之间的复制
参数1是destination，即复制的目的地，为一地址
参数2是source，即复制数据的来源，为一地址
参数3是要复制的字节数，sizeof(int)计算出int的字节数，乘以相应的元素个数N

例程中的memcpy(jianshu+i, B+1, sizeof(int)*B[0])是从B数组的1号位置开始（跳过B[0]），复制B[0]个数位，目的地为jianshu数组的第jianshu+1+i-1个位置，+1是为了跳过jianshu[0]，+i-1是把这几个位置空成0，以构造最大数量级的减数。晕了么有？别怕，其实可以把代码写的长一些，但是更简单一些的，这里是偷懒了;-)