大数相乘

发表于 更新于 分类于

前言

假如说我们有两个很大的数相乘，比如说两个二十位数相乘，我们用程序该怎么实现呢？在c语言中，int类型的变量大小一般是4byte，肯定是存不下这么大的数的。这篇文章来稍微讨论下这个问题。

思路

既然变量存不下这么大的数，那么我们可以用数组来存储，比如说789，我们可以用char a[4] = “789”来存储，这样的话就可以存下很大的数了。
下一步就是如何解析数组并实现乘法。关于乘法，我们小时候都学过笔算，所以，我们就可以根据这个笔算的方法来实现。

举个例子：
比如说我们计算1256*23
第一步：

1
2
3*1256=3768，
2*1256=2512

第二步：

1
2512*10+3768=28888

代码

下面我们用代码来实现一下

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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
    char data[256] = {0};
    int mult1_size = 0;
    int mult2_size = 0;
    char *mult1 = NULL;
    char *mult2 = NULL;

    printf("Please input mult1:\n");
    fgets(data, 256, stdin);
    mult1_size = strlen(data) - 1;
    data[mult1_size] = '\0';
    mult1 = (char *)malloc(mult1_size + 1 + 1); // +1 for carry, +1 is '\n' for printf
    memset(mult1, 0, mult1_size + 1 + 1);
    memcpy(mult1, data, mult1_size);

    memset(data, 0, 256);
    printf("Please input mult2:\n");
    fgets(data, 256, stdin);
    mult2_size = strlen(data) - 1;
    data[mult2_size] = '\0';
    mult2 = (char *)malloc(mult2_size + 1 + 1);
    memset(mult2, 0, mult2_size + 1 + 1);
    memcpy(mult2, data, mult2_size);

    //printf("mult1 = %s, mult2 = %s\n", mult1, mult2);

    char sum_ret_row = mult1_size+1+1; //行
    char sum_ret_col = mult2_size+1+1; //列
    char *sum_ret = (char *)malloc(sum_ret_row * sum_ret_col);

    for (int i = mult2_size - 1; i >= 0; i--) {
        char reserve = 0;
        int sum_ret_i = 0;
        for (int j = mult1_size - 1; j >= 0; j--) {
            int m1 = mult1[j] - '0';
            int m2 = mult2[i] - '0';
            int value = m1 * m2 + reserve;
            //printf("%d * %d = %d\n", m1, m2, value);

            sum_ret[sum_ret_row * i + sum_ret_i++] = (value % 10) + '0';

            if (value > 9) reserve = value / 10;
            else reserve = 0;
        }
        if (reserve != 0) {
            sum_ret[sum_ret_row * i + sum_ret_i++] = reserve + '0';
        }
    }

    // printf("ret=\n");
    // for (int i = mult2_size - 1; i >= 0; i--) {
    //     int len = strlen(&sum_ret[i * sum_ret_row]);
    //     for (int j = len - 1; j >= 0; j--) {
    //         printf("%c", sum_ret[i*sum_ret_row+j]);
    //     }
    //     printf("\n");
    // }

    char out[256] = {0};
    int out_i = 0;
    for (int i = mult2_size - 1; i > 0; i--) {
        static int copy = 0;
        if (copy == 0) {
            copy++;
            memcpy(out, &sum_ret[i * sum_ret_row], strlen(&sum_ret[i * sum_ret_row]));
        }

        out_i++;
        int reserve = 0;
        int len = strlen(&sum_ret[(i - 1) * sum_ret_row]);
        for (int j = 0; j < len; j++) {
            int add1 = out[out_i + j] == 0 ? 0 : out[out_i + j] - '0';
            int add2 = sum_ret[(i - 1) * sum_ret_row + j] - '0';
            int value = add1 + add2 + reserve;
            //printf("%d=%d+%d+%d\n", value, add1, add2, reserve);

            out[out_i + j] = (value % 10) + '0';
            //printf("%c\n", out[out_i + j]);

            if (value > 9) reserve = value / 10;
            else reserve = 0;
        }
        if (reserve != 0) {
            out[out_i + len - 1] = reserve + '0';
        }
    }

    //reverse
    int len = strlen(out);
    for (int j = 0; j < len / 2; j++) {
        char tmp = out[j];
        out[j] = out[len - 1 - j];
        out[len - 1 - j] = tmp;
    }

    printf("%s * %s = %s\n", mult1, mult2, out);

    free(mult1);
    free(mult2);
    free(sum_ret);

    return 0;
}

简单分析

其实代码的思想就和上面说的一样，运行一下

1
2
3
4
5
Please input mult1:
123456789654123456798
Please input mult2:
451216557522365512323
123456789654123456798 * 451216557522365512323 = 55705747630496376206760849965779027121754

可以看见，两个二十一位数相乘，我们的程序依然算出了结果，经过实验，结果正确。