多精度数的四则运算-Java和Python实现

发表于2019-11-10更新于2021-09-01字数统计3.1k

多精度数指的是位数超过1024Bit的数。由于这一类数的位数超过了计算机CPU寄存器表达，也就是超出了计算机的字长，所以不能够使用计算机进行直接的运算。除此之外，多精度数的大小也超出了计算机中定义的整型变量的最大大小，所以也不能使用标准的整型来存储这一类数，而需要使用数组或是字符串来存储。

对于多精度数的计算，目前有两种处理办法：

  1. 模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。
    这个方法的优点是操作逻辑符合人们的日常思维，易于理解，缺点是效率较低。
  2. 将多精度数当作一个二进制流进行处理，使用各种移位和逻辑操作来进行加减乘除运算。
    这个方法的优点是执行效率高，缺点是代码极其复杂，可读性低，难以理解。

下面的算法都是基于第一种办法进行处理。

算法原理

先重新理一下竖式计算的流程：

  • 加法在手工竖式计算中，当两个位相加得到的值大于10时就会产生一个进位值，并会在高一位的计算中把进位值也加入计算，这样从低位到高位一直计算直到计算结束为止。所以在算法中也需要定义一个进位值的变量。

  • 减法与加法类似，当被减数位小于减数位时，会产生一个退位值，即向更高一位去借10，来避免产生负数。若这一位产生了借位，那么高一位的计算中就要减去1再进行计算。所以在算法中也需要定义一个退位值的变量。

  • 乘法的运算在竖式计算中是把乘数逐位的与被乘数相乘，且运算结果随着乘数的位数向左移，最后再全部相加。所以在对单个结果位的处理中要考虑到三个因素：第一个是当前的计算结果；第二个是前一位产生的进位；第三个是之前的计算中在这一位得出的结果。

  • 除法在竖式运算中可以理解为是多次的减法。下图展示了除法算法的流程：

  • 模指数运算
    除此之外，还有多精度数的模指数运算，即计算以下式子的值：

ae mod m\Large{a^e\space mod\space m}

可采用重复平方乘算法来实现：

算法实现

理解了竖式计算的流程与规则后，就可以使用算法进行实现了。由于课程实验原因，我做了Java和Python两个语言的版本，其中Java里面使用了ArrayList对数进行存储，Python中则使用了列表List进行存储。

Java：

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
// 导入对应模块
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BigNum {

    /**
     * 此方法用于快速创建一个存储有多精度整数的ArrayList对象
     * 参数 elements 为整个整数的每一位数字
     * 返回 ArrayList<Integer>
     */
    public static ArrayList<Integer> createArrayList(int ... elements) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (Integer element : elements) {
            list.add(element);
        }
        return list;
    }


    /**
     * 此方法用于比较两个数的大小。若第一个数大于等于第二个数则返回true，否则返回false
     * 参数 num1, num2 为要比较的数
     * 返回比较结果 boolean
     */
    public static boolean isBigger(ArrayList<Integer> num1, ArrayList<Integer> num2) {
        if(num1.size() < num2.size())  return false;
        else if(num1.size() > num2.size())  return true;
        else if(num1.size() == num2.size()){
            for (int i = 0; i < num1.size(); i++){
                if(num1.get(i)<num2.get(i))  return false;
                else if(num1.get(i)>num2.get(i)) return true;
            }
        }
        return true;
    }


    /**
     * 此方法用于实现两个多精度整数相加
     * 参数 num1, num2 为两个加数
     * 返回存储有运算结果的 ArrayList<Integer>
     */
    public static ArrayList<Integer> bigPlus (ArrayList<Integer> num1, ArrayList<Integer> num2){
        // 判断特殊情况
        if(num1.size() < num2.size()){
            ArrayList<Integer> tmp = num1;
            num1 = num2;
            num2 = tmp;
        }
        if(num1.isEmpty())  return num2;
        if(num2.isEmpty())  return num1;

        //数组索引反向，使数字的位数与索引对齐
        Collections.reverse(num1);
        Collections.reverse(num2);

        ArrayList result = new ArrayList(num1.size()+1);  //创建结果对象
        int c = 0;  //进位值
        for (int i = 0; i < num2.size(); i++){
            //判断是否进位
            if (num1.get(i) + num2.get(i) + c < 10){
                result.add(num1.get(i) + num2.get(i) + c);
                c = 0;
            }else{
                result.add(num1.get(i) + num2.get(i) + c - 10);
                c = 1;
            }
        }
        if(num1.size() == num2.size())  result.add(c);  //若两数位数相等，则最高位直接为进位值
        else{  //若两数位数不相等，把位数大的数的后续位直接与进位值相加，添加到结果中
            result.add(c+num1.get(num2.size()));
            for(int i : num1.subList(num2.size()+1,num1.size())){
                result.add(i);
            }
        }

        //把所有ArrayList的索引反向至正常状态
        Collections.reverse(result);
        Collections.reverse(num1);
        Collections.reverse(num2);

        //消除前导0
        if((int)result.get(0) == 0) {
            result.remove(0);
        }
        return result;
    }


    /**
     * 此方法用于实现两个多精度整数相减，若被减数小于减数则自动将两者调换后相减
     * 参数 num1 为被减数, num2 为减数
     * 返回存储有运算结果的 ArrayList<Integer>
     */
    public static ArrayList<Integer> bigSub (ArrayList<Integer> num1, ArrayList<Integer> num2){
        // 判断特殊情况
        if(num1 == num2 || (num1.isEmpty() && num2.isEmpty()))  return createArrayList(0);
        if(num1.isEmpty())  return num2;
        if(num2.isEmpty())  return num1;
        if(!BigNum.isBigger(num1,num2)){
            System.out.println("检测到减数大于被减数，已自动将减数与被减数交换");
            ArrayList<Integer> tmp = num1;
            num1 = num2;
            num2 = tmp;
        }

        //数组索引反向，使数字的位数与索引对齐
        Collections.reverse(num1);
        Collections.reverse(num2);

        ArrayList result = new ArrayList(num1.size());  //创建结果对象
        int c = 0;  //借位值
        for (int i = 0; i<num2.size();i++){
            //判断是否借位
            if(num1.get(i) - num2.get(i) + c >= 0){
                result.add(num1.get(i) - num2.get(i) + c);
                c = 0;
            }else{
                result.add(num1.get(i) - num2.get(i) + c + 10);
                c = -1;
            }
        }

        //若两数位数不相等，把位数大的数的后续位直接与进位值相加，添加到结果中
        if(num1.size() > num2.size()){
            result.add(c+num1.get(num2.size()));
            for(int i : num1.subList(num2.size()+1,num1.size()))  result.add(i);
        }

        //把所有ArrayList的索引反向至正常状态
        Collections.reverse(result);
        Collections.reverse(num1);
        Collections.reverse(num2);

        //消除前导0
        if((int)result.get(0) == 0) {
            result.remove(0);
        }
        return result;
    }


    /**
     * 此方法用于实现两个多精度整数相乘
     * 参数 num1, num2 为两个乘数
     * 返回存储有运算结果的 ArrayList<Integer>
     */
    public static ArrayList<Integer> bigMult (ArrayList<Integer> num1, ArrayList<Integer> num2){

        //数组索引反向，使数字的位数与索引对齐
       if(num1.hashCode()==num2.hashCode()){
           Collections.reverse(num1);
       }else{
           Collections.reverse(num1);
           Collections.reverse(num2);
       }


        ArrayList result = new ArrayList(num1.size()+num2.size());  //创建结果对象
        int uv = 0;  //乘法临时值

        for (int i = 0; i<num1.size()+num2.size()+1; i++)  result.add(0);  //结果所有位置为0

        for (int i = 0; i<num1.size(); i++){
            int c = 0;  //进位值
            for (int j = 0; j<num2.size(); j++){
                uv = (int)result.get(i+j) + num1.get(i) * num2.get(j) + c;  //按手工计算的方式进行逐位的运算
                result.set(i+j, uv%10);
                c = uv/10;
            }
            result.set(i+num2.size(), uv/10);
        }

        //把所有ArrayList的索引反向至正常状态
        Collections.reverse(result);
        if(num1.hashCode()==num2.hashCode()){
            Collections.reverse(num1);
        }else{
            Collections.reverse(num1);
            Collections.reverse(num2);
        }

        //消除前导0
        while((int)result.get(0) == 0) {
            result.remove(0);
        }
        return result;
    }


    /**
     * 此方法用于实现两个多精度整数相除
     * 参数 num1 为被除数, num2 为除数
     * 返回存储有运算结果的 List<ArrayList<Integer>>, List 中第一项为商，第二项为余数
     * @return
     */
    public static List bigDiv (ArrayList<Integer> num1, ArrayList<Integer> num2){

        if(num1 == num2) {  //若两数相等，返回商为1，余数为0
            return Arrays.asList(createArrayList(1),createArrayList(0));
        }
        if(num2.get(0) == 0 && num2.size() == 1){  //若除数为0，返回-1
            System.out.println("除数不得为0");
            return Arrays.asList(createArrayList(-1),createArrayList(0));
        }
        if(!BigNum.isBigger(num1,num2)){  //若除数大于被除数，则商为0，余数为被除数的值
            return Arrays.asList(createArrayList(0),num1);
        }

        while(num1.get(0)==0){  //消除产生的前导0
            num1.remove(0);
        }
        while(num2.get(0)==0){  //消除产生的前导0
            num2.remove(0);
        }

        //创建并初始化结果对象
        ArrayList result = new ArrayList();
        for (int i=0;i<num1.size()-num2.size()+1;i++){
            result.add(i,0);
        }

        //为除数扩充0至位数与被除数相等，并计算扩大的倍数
        ArrayList num2_duiqi = (ArrayList) num2.clone();
        int mult_times = 0;  //扩大倍数
        int times = 0;  //除法结果
        while(num2_duiqi.size()!=num1.size()){
            num2_duiqi.add(0);
            mult_times++;
        }

        while(true) {
            while (BigNum.isBigger(num1, num2_duiqi)) {  //逐次相减，并在结果中乘以对应的倍数
                num1 = BigNum.bigSub(num1, num2_duiqi);
                if(num1.size()!=0){
                    while(num1.get(0)==0){  //消除产生的前导0
                        num1.remove(0);
                        if(num1.isEmpty()){
                            break;
                        }
                    }
                }
                times++;
            }
            result.set(mult_times, times);  //结果中填入结果
            times = 0;  //除法结果重置

            //除完一轮重新对齐，并修改扩大的倍数
            if ((int) num2_duiqi.get(num2_duiqi.size() - 1) == 0 && num2_duiqi.size() > num2.size()){
                num2_duiqi.remove(num2_duiqi.size() - 1);
                mult_times--;
            }
            else{  //除到末位后，将结果的索引反向
                Collections.reverse(result);
                break;
            }
        }
        //返回结果
        if(num1.size()==0){
            return Arrays.asList(result,createArrayList(0));
        }
        return Arrays.asList(result,num1);
    }


    public static ArrayList bigPow (ArrayList<Integer> a, ArrayList<Integer> k, ArrayList<Integer> m){
        ArrayList A = (ArrayList)a.clone();  //A=a
        ArrayList b = createArrayList(1);  //令b=1
        if(k.isEmpty() || (k.size()==1 && k.get(0)==0))  return b;  //如果k=0，则返回b

        List kk;
        ArrayList<Integer> k1 = (ArrayList<Integer>)k.clone();
        ArrayList k2 = new ArrayList();
        while(!(k1.size()==1&&k1.get(0)==0)){  //将k转换为二进制，结果为k2
            kk = BigNum.bigDiv(k1,createArrayList(2));
            k1 = (ArrayList<Integer>) kk.get(0);
            k2.add(((ArrayList) kk.get(1)).get(0));
        }

        if((int)k2.get(0)==1){  //如果k0=1，则b=a
            b= (ArrayList) a.clone();
        }
        for(int i = 1;i<k2.size();i++){
            A = (ArrayList) BigNum.bigDiv(BigNum.bigMult(A,A), m).get(1);
            if((int)k2.get(i)==1){
                b = (ArrayList) BigNum.bigDiv(BigNum.bigMult(A,b), m).get(1);
            }
        }

        return b;
    }
}

Python（注释可参考Java版本）：

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
class BigNum:
    
    @staticmethod
    def __isBigger(num1, num2):
        if len(num1) < len(num2):
            return False
        elif len(num1) > len(num2):
            return True
        elif len(num1) == len(num2):
            for i in range(0, len(num1)):
                if num1[i]<num2[i] :
                    return False
                elif num1[i]>num2[i] :
                    return True
        return True

    
    @staticmethod
    def bigPlus(n1, n2):
        if len(n1) < len(n2):
            n1, n2 = n2, n1
        if n1 == []:
            return n2
        if n2 == []:
            return n1
        
        num1 = list(reversed(n1))
        num2 = list(reversed(n2))
        result = []
        c = 0
        for i in range(0, len(num2)):
            if num1[i] + num2[i] + c < 10 :
                result.append(num1[i] + num2[i] + c)
                c = 0
            else:
                result.append(num1[i] + num2[i] + c - 10)
                c = 1
        if len(num1) == len(num2):
            result.append(c)
        else:
            result.append(c+num1[len(num2)])
            for each in num1[len(num2)+1:]:
                result.append(each)
       
        result.reverse()
        if result[0] == 0:
            result.pop(0)
        return result
        
        
    @staticmethod
    def bigSub(n1, n2):
        if n1 == n2 or (n1 == [] and n2 == []):
            return [0,]
        if n1 == []:
            return n2
        if n2 == []:
            return n1
        elif not BigNum.__isBigger(n1, n2):
            print("检测到减数大于被减数，已自动将减数与被减数交换")
            n1, n2 = n2, n1
        
        num1 = list(reversed(n1))
        num2 = list(reversed(n2))
        result = []
        c = 0
        for i in range(0, len(num2)):
            if(num1[i] - num2[i] + c >= 0):
                result.append(num1[i] - num2[i] + c)
                c = 0
            else:
                result.append(num1[i] - num2[i] + c + 10)
                c = -1
        if len(num1) > len(num2):
            result.append(c+num1[len(num2)])
            for each in num1[len(num2)+1:]:
                result.append(each)
        result.reverse()
        if result[0] == 0:
            result.pop(0)
        
        return result
        

    @staticmethod
    def bigMult(num1, num2):
        num1.reverse()
        num2.reverse()

        result = []
        uv = 0
        for i in range(0, len(num1) + len(num2) + 1):
            result.append(0)
        for i in range(0, len(num1)):
            c = 0
            for j in range(0, len(num2)):
                uv = result[i+j] + int(num1[i]) * int(num2[j]) + c
                result[i+j] = uv % 10
                c = uv // 10
            result[i+len(num2)] = uv // 10
        result.reverse()
        num1.reverse()
        num2.reverse()
        while result[0] == 0:
            result.pop(0)
        return result
        
  
    @staticmethod    
    def bigDiv(num1, num2):
        if num1 == num2:
            return [1,], [0,]
        elif not BigNum.__isBigger(num1, num2):
            print("检测到除数大于被除数，已自动将除数与被除数交换")
            num1, num2 = num2, num1
        if num2[0]==0 and len(num2)==1:
            print("除数不得为0")
            return [-1,], [0,]

        result = []
        for i in range(0, len(num1)-len(num2)+1):
            result.append(0)

        num2_duiqi = num2[:]
        mult_times = 0
        times = 0
        
        while len(num2_duiqi)!=len(num1):
            num2_duiqi.append(0)
            mult_times+=1
        
        while True:
            while BigNum.__isBigger(num1, num2_duiqi):
                num1 = BigNum.bigSub(num1, num2_duiqi)
                while num1[0]==0:
                    num1.pop(0)
                times+=1
            result[mult_times] = times
            times = 0
            
            if num2_duiqi[len(num2_duiqi)-1]==0 and len(num2_duiqi)>len(num2):
                num2_duiqi.pop(len(num2_duiqi)-1)
                mult_times-=1
            else:
                result.reverse()
                break
        
        return result, num1