前言

  由于计算机运算是有模运算,数据范围的表示有一定限制,如整型int(C++中int与long相同)表达范围是(-2^312^31-1),unsigned long(无符号整数)是(02^32-1),都约为几十亿.如果采用实数型,则能保存最大的double只能提供15~16位的有效数字,即只能精确表达数百万亿的数.因此,在计算位数超过十几位的数时,不能采用现有类型,只能自己编程计算.

  高精度计算通用方法:高精度计算时一般用一个数组来存储一个数,数组的一个元素对应于数的一位(当然,在以后的学习中为了加快计算速度,也可用数组的一个元素表示数的多位数字,暂时不讲),表示时,由于数计算时可能要进位,因此为了方便,将数由低位到高位依次存在数组下标对应由低到高位置上,另外,我们申请数组大小时,一般考虑了最大的情况,在很多情况下,表示有富余,即高位有很多0,可能造成无效的运算和判断,因此,我们一般将数组的第0个下标对应位置来存储该数的位数.如数:3485(三千四百八十五)，表达在数组a[5]上情况是:

下标  0  1  2  3  4
内容  4  5  8  4  3
说明： 位数  个位  十位  百位  千位
具体在计算加减乘除时方法就是小学时采用的列竖式方法.

高精度数的存储

采用字符串读入

将数先存在字符串中,再逐位倒叙存入数组中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int num1[200], num2[200]; //最高199位
    string input;
    memset(num1, 0, sizeof(num1)); //数组清零
    memset(num2, 0, sizeof(num2));
    cin >> input;
    num1[0] = input.length(); //位数
    for (int i = 1; i <= num1[0]; ++i)
        num1[i] = input[num1[0] - i] - '0'; //将字符转为数字并倒序存储进数组
    cin >> input;
    num2[0] = input.length();
    for (int i = 1; i <= num2[0]; ++i)
        num2[i] = input[num2[0] - i] - '0';
}

采用直接读入

利用取余数的方式存入数组中

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int main() {
    int num[200], key;
    cin >> key;
    memset(num, 0, sizeof(num)); //数组清零
    int i = 0; //第i位
    while(key){
        num[++i] = key % 10; //取第i位数
        key /= 10;
    }
    num[0] = i; //位数位i位
}

操作高精度数

以下程序只写实现功能的函数,并且假定高精度数的数据结构满足上述约定.

比较两个高精度数

1
2
3
4
5
6
7
8
9
10
11
//比较a和b的大小关系,a>b return 1,a<b return -1,a=b return 0
int compare(int a[], int b[]) {
    int k = a[0] > b[0] ? a[0] : b[0]; //更大的位数
    for (int i = k; i > 0; --i) { //逐位比较
        if (a[i] > b[i])
            return 1;
        if (a[i] < b[i])
            return -1;
    }
    return 0; //各位都相等
}

高精度数加法

1
2
3
4
5
6
7
8
9
10
11
void doplus(int a[], int b[]) {  //结果放在a中，即计算a=a+b
    int k = a[0] > b[0] ? a[0] : b[0];
    for (int i = 1; i <= k; ++i) {
        a[i + 1] += (a[i] + b[i]) / 10; //先进位
        a[i] = (a[i] + b[i]) % 10;
    }
    if (a[k + 1] > 0)
        a[0] = k + 1;
    else
        a[0] = k;
}

高精度数减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int dominus(int a[], int b[]) {  //结果放于a中，返回符号位，1正数，0相等，-1负数
    if (compare(a, b) == 0) {  // a=a-b=0 return 0
        a[1] = 0, a[0] = 1;    // memset(a,0,sizeof(a));
        return 0;
    }
    if (compare(a, b) == 1) {  // a=a-b return 1
        for (int i = 1; i <= b[0]; ++i) {
            if (a[i] < b[i]) {
                a[i + 1]--;
                a[i] = a[i] + 10 - b[i];
            } else {
                a[i] -= b[i];
            }
        }
        while (a[a[0]] == 0)
            a[0]--;
        return 1;
    }
    for (int i = 1; i <= b[0]; ++i) {  // a=b-a return -1
        if (b[i] < a[i]) {
            b[i + 1]--;
            a[i] = b[i] + 10 - a[i];
        } else {
            a[i] = b[i] - a[i];
        }
    }
    a[0] = b[0];
    while (a[a[0]] == 0)
        a[0]--;
    return -1;
}

高精度乘法

要求尽可能用更少的存储单元,逐位相乘,注意进位和总位数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int *multiply(int a[], int b[]) { //结果存在res数组中并返回res
    int res[a[0] + b[0]];
    res[0] = a[0] + b[0]; //最坏情况下的位数
    memset(res, 0, sizeof(res));
    for (int i = 0; i < a[0]; ++i)
        for (int j = 0; j < b[0]; ++j) {
            res[i + j] += a[i] * b[j];
            res[i + j + 1] += res[i + j] / 10;
            res[i + j] = res[i + j] % 10;
        }
    while (!res[res[0]]) //位数的修正
        res[0]--;
    return res;
}

高精度除法

模拟手算除法,把除法试商转化为连减.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <stdio.h>
#include <string.h>
#define N 500
int bj(int a[], int b[], int k1, int k2) /*比较大小函数*/
{
    int i, t, flag; /*flag作标志位*/
    if (k1 < k2)
        flag = 0; /*被除数小于除数返回0*/
    else if (k1 > k2)
        flag = 1; /*被除数大于除数返回1*/
    else {        /*被除数和除数位数相等则逐位进行比较*/
        i = k1;
        t = 0;
        while (t == 0 && i > 0) {
            if (a[i] > b[i]) {
                t = 1;
                flag = 1;
            } else if (a[i] == b[i])
                i--;
            else {
                t = 1;
                flag = 0;
            }
        }
        if (i == 0 && t == 0)
            flag = 2; /*被除数等于除数返回2*/
    }
    return flag;
}
int jf(int a[], int b[], int k1, int k2) /*减法运算*/
{
    int i, k, d[N];
    for (i = 0; i < k2; i++)
        d[i] = b[i]; /*把除数赋给数组d*/
    for (i = k2; i < N; i++)
        d[i] = 0;    /*d数组无数据的高位置0*/
    k = k1 - k2 - 1; /*计算减法起始位置*/
    if (k < 0)
        k = 0;
    if (k > 0) {
        for (i = k2 - 1; i >= 0; i--)
            d[i + k] = d[i]; /*移动减数位数与被减数对齐*/
        for (i = 0; i < k; i++)
            d[i] = 0; /*移动后的其余位置0*/
    }
    for (i = 0; i < k1; i++) {
        if (a[i] >= d[i])
            a[i] -= d[i];
        else {
            a[i + 1] = a[i + 1] - 1;
            a[i] = 10 + a[i] - d[i];
        }
    }
    return k;
}
int main() {
    int a[N] = { 0 }, b[N] = { 0 }, c[N] = { 0 }, d[N] = { 0 };
    int i, ka, kb, m, t, t1, t2, k, x, kd, kk;
    char a1[N], b1[N];
    printf("Input 被除数:");
    scanf("%s", a1);
    ka = strlen(a1);
    for (i = 0; i < ka; i++)
        a[i] = a1[ka - i - 1] - '0';
    printf("Input 除数:");
    scanf("%s", b1);
    kb = strlen(b1);
    for (i = 0; i < kb; i++)
        b[i] = b1[kb - i - 1] - '0';
    kd = ka; /*保存被除数位数  */
    t2 = bj(a, b, ka, kb);
    m = 0;
    do {
        while (a[ka - 1] == 0)
            ka--;
        t = bj(a, b, ka, kb);
        if (t >= 1) {
            k = jf(a, b, ka, kb);
            c[k]++;
            if (k > m)
                m = k;
            t1 = 0;
            for (i = k; i <= m; i++) {
                x = c[i] + t1;
                c[i] = x % 10;
                t1 = x / 10;
            }
            if (t1 > 0) {
                m++;
                c[m] = t1;
            }
        }
    } while (t == 1);
    if (t2 == 0) {
        printf("商=0");
        printf("\n余数=");
        for (i = kd - 1; i >= 0; i--)
            printf("%d", a[i]);
        exit(1);
    }
    if (t2 == 2) {
        printf("商 = 1");
        printf("\n余数 = 0");
        exit(1);
    }
    kk = kd;
    while (!c[kd - 1])
        kd--;
    printf("商 = ");
    for (i = kd - 1; i >= 0; i--)
        printf("%d", c[i]);
    while (!a[kk])
        kk--;
    printf("\n余数 = ");
    if (kk < 0) {
        printf("0");
        exit(1);
    }
    for (i = kk; i >= 0; i--)
        printf("%d", a[i]);
}

案例

N！，要求精确到P位(0〈P〈1000)

问题1. N！，要求精确到P位(0〈P〈1000)
算法：结果用数组a保存，开始时a[0]=1，依次乘以数组中各位，注意进位和数组长度的变化
源程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#define M 1000
int main() {
    int a[M], i, n, j, flag = 1;
    printf("n=");
    scanf("%d", &n);
    printf("n!=");
    a[0] = 1;
    for (i = 1; i < M; i++)
        a[i] = 0;
    for (j = 2; j <= n; j++) {
        for (i = 0; i < flag; i++)
            a[i] *= j;
        for (i = 0; i < flag; i++)
            if (a[i] >= 10) {
                a[i + 1] += a[i] / 10;
                a[i] = a[i] % 10;
                if (i == flag - 1)
                    flag++;
            }
    }
    for (j = flag - 1; j >= 0; j--)
        printf("%d", a[j]);
}

麦森数

问题2. 麦森数
【问题描述】形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关
任务：从文件中输入P（1000<P<3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）
【输入格式】
文件中只包含一个整数P（1000<P<3100000）
【输出格式】
第一行：十进制高精度数2P-1的位数。
第2-11行：十进制高精度数2P-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）
不必验证2P-1与P是否为素数。
【输入样例】
1279
【输出样例】
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087
算法：2的幂可以转化成左移运算，为了提高运算速度，可每次左移10位，即每次乘210。对于个位单独考虑，每次左移一位
源程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <math.h>
#include <stdio.h>
#define MAX 100000
int main() {
    int p;
    int i, j;
    scanf("%d", &p);
    printf("%d\n", (int)(p * log10(2.0)) + 1);
    long store[110] = { 0 };
    store[0] = 1;
    int left = p % 10;
    p /= 10;
    for (i = 1; i <= p; i++) {
        for (j = 0; j <= 100; j++)
            store[j] <<= 10;
        for (j = 0; j <= 100; j++) {
            if (store[j] >= MAX) {
                store[j + 1] += store[j] / MAX;
                store[j] %= MAX;
            }
        }
    }
    for (i = 1; i <= left; i++) {
        for (j = 0; j <= 100; j++)
            store[j] <<= 1;
        for (j = 0; j <= 100; j++) {
            if (store[j] >= MAX) {
                store[j + 1] += store[j] / MAX;
                store[j] %= MAX;
            }
        }
    }
    store[0] -= 1;
    for (i = 1; i < 100; i++) {
        if (store[i - 1] < 0) {
            store[i] -= 1;
            store[i - 1] += MAX;
        } else
            break;
    }
    for (i = 99; i >= 0; i--) {
        printf("%05d", store[i]);
        if ((100 - i) % 10 == 0)
            printf("\n");
    }
}