多精度数的四则运算-Java和Python实现
多精度数指的是位数超过1024Bit的数。由于这一类数的位数超过了计算机CPU寄存器表达，也就是超出了计算机的字长，所以不能够使用计算机进行直接的运算。除此之外，多精度数的大小也超出了计算机中定义的整型变量的最大大小，所以也不能使用标准的整型来存储这一类数，而需要使用数组或是字符串来存储。 对于多精度数的计算，目前有两种处理办法： 模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。 这个方法的优点是操作逻辑符合人们的日常思维，易于理解，缺点是效率较低。 将多精度数当作一个二进制流进行处理，使用各种移位和逻辑操作来进行加减乘除运算。 这个方法的优点是执行效率高，缺点是代码极其复杂，可读性低，难以理解。 下面的算法都是基于第一种办法进行处理。 算法原理 先重新理一下竖式计算的流程： 加法在手工竖式计算中，当两个位相加得到的值大于10时就会产生一个进位值，并会在高一位的计算中把进位值也加入计算，这样从低位到高位一直计算直到计算结束为止。所以在算法中也需要定义一个进位值的变量。 减法与加法类似，当被减数位小于减数位时，会产生一个退位值，即向更高一位去借10，来避免产生负数。若这一位产生了借位，那么高一位的计算中就要减去1再进行计算。所以在算法中也需要定义一个退位值的变量。 乘法的运算在竖式计算中是把乘数逐位的与被乘数相乘，且运算结果随着乘数的位数向左移，最后再全部相加。所以在对单个结果位的处理中要考虑到三个因素：第一个是当前的计算结果；第二个是前一位产生的进位；第三个是之前的计算中在这一位得出的结果。 除法在竖式运算中可以理解为是多次的减法。下图展示了除法算法的流程： 模指数运算 除此之外，还有多精度数的模指数运算，即计算以下式子的值： $$\Large{a^e\space mod\space m} $$ 可采用重复平方乘算法来实现： 算法实现 理解了竖式计算的流程与规则后，就可以使用算法进行实现了。由于课程实验原因，我做了Java和Python两个语言的版本，其中Java里面使用了ArrayList对数进行存储，Python中则使用了列表List进行存储。 Java： // 导入对应模块 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....