高精度乘法

高精度乘法

给定两个非负整数（不含前导 0）A 和 B，请你计算 A×B 的值。
所用方法和基本原理

该代码采用一种简化的乘法方式来实现大数乘法（大数x小数），基本原理如下：

• 数位拆分与转换：
      - 对于字符串 A，将其每一位数字拆分出来存储到数组 mulA 中，从字符串末尾开始处理，方便后续按位运算。
      - 对于字符串 b，将其转换为一个整数 mulb。通过遍历字符串 b，利用 Math.pow(10, j) * (b.charAt(i) - '0') 的方式，将每一位数字乘以对应的权值并累加，得到 b 对应的整数值。
  
• 模拟乘法运算：
      - 创建一个长度为 ALen + 1 的结果数组 res 来存储乘法结果，最后一位可能是多位数，而前面都是单位数。
      - 初始化一个变量 t 用于存储进位。
      - 遍历数组 mulA，将每一位与 mulb 相乘，并加上之前的进位 t，得到当前位的和 iSum。将 iSum 对 10 取余得到当前位的数字存入 res 数组，iSum 除以 10 得到新的进位 t。
  
• 处理结果：
      - 从结果数组的高位开始（即 ALen 位置），跳过前导 0，找到第一个非零元素的位置 startIdx。
      - 将从 startIdx 开始到数组开头的元素依次添加到 StringBuffer 中，最后转换为字符串返回。
  

代码及注释

1. public class BigNumberMultiplication {
2.     // 实现两个非负整数字符串的乘法
3.     public static String mul(String A, String b) {
4.         int ALen = A.length();
5.         int bLen = b.length();
6.         // 创建数组mulA用于存储字符串A按位拆分后的数字
7.         int[] mulA = new int[ALen];
8.         int mulb = 0;
11.         // 将字符串A按位拆分并存入mulA数组
12.         for (int i = ALen - 1, j = 0; i >= 0; i--, j++) {
13.             mulA[j] = A.charAt(i) - '0';
14.         }
15.         // 将字符串b转换为整数mulb
16.         for (int i = bLen - 1, j = 0; i >= 0; i--, j++) {
17.             mulb += Math.pow(10, j) * (b.charAt(i) - '0');
18.         }
21.         // 创建结果数组res，长度为ALen + 1
22.         int[] res = new int[ALen + 1];
23.         int t = 0;
24.         // 模拟乘法运算，逐位相乘并处理进位
25.         for (int i = 0; i < ALen; i++) {
26.             int iSum = mulA[i] * mulb + t; // 当前这一位的和
27.             res[i] = iSum % 10; // 每一位上的数字
28.             t = iSum / 10; // 进位
29.         }
30.         res[ALen] = t; // 最后一位
33.         // 找到结果数组中第一个非零元素的位置，跳过前导0
34.         int startIdx = ALen;
35.         while (res[startIdx] == 0) {
36.             startIdx--;
37.             if (startIdx < 0) {
38.                 return "0";
39.             }
40.         }
43.         // 创建StringBuffer用于构建结果字符串
44.         StringBuffer resStr = new StringBuffer();
45.         // 将结果数组从有效位开始添加到StringBuffer中
46.         for (int i = startIdx; i >= 0; i--) {
47.             resStr.append(res[i]);
48.         }
51.         return resStr.toString();
52.     }
53. }

复制代码

举例说明

假设 A = "123"，b = "45"。

• 数位拆分与转换：
      - ALen = 3，bLen = 2。
      - mulA = [3, 2, 1]。
      - mulb = 5 * Math.pow(10, 0) + 4 * Math.pow(10, 1) = 45。
  
• 模拟乘法运算：
      - 第一次循环：i = 0，iSum = 3 * 45 + 0 = 135，res[0] = 135 % 10 = 5，t = 135 / 10 = 13。
      - 第二次循环：i = 1，iSum = 2 * 45 + 13 = 103，res[1] = 103 % 10 = 3，t = 103 / 10 = 10。
      - 第三次循环：i = 2，iSum = 1 * 45 + 10 = 55，res[2] = 55 % 10 = 5，t = 55 / 10 = 5。
      - 此时 res = [5, 3, 5, 5]。
  
• 处理结果：
      - startIdx = 3，从 startIdx 开始添加元素到 resStr，得到 "5535"。
  

方法的优劣

• 时间复杂度：
      - 对于字符串 A 的拆分时间复杂度为 (O(m))，其中 m 是 A 的长度；对于字符串 b 转换为整数的时间复杂度为 (O(n))，其中 n 是 b 的长度；模拟乘法运算的时间复杂度为 (O(m))。总体时间复杂度为 (O(m + n))，这里假设 (m \geq n)。
  
• 空间复杂度：
      - 创建了一个长度为 ALen + 1 的数组 res 和长度为 ALen 的数组 mulA，空间复杂度为 (O(m))，这里 (m) 是 A 的长度。同时在计算 mulb 时，可能会涉及到与 n 相关的临时空间，但总体空间复杂度主要由数组决定，为 (O(m))。
  

优点：
    - 实现相对简单，对于较小规模的大数乘法能够较为直观地计算出结果。
    - 代码逻辑较为清晰，容易理解。
缺点：
    - 当 b 是一个非常大的数时，将其转换为整数可能会导致整数溢出，限制了该方法处理大数的能力。
    - 空间复杂度相对较高，需要额外的数组来存储中间结果。对于非常大的数，内存消耗较大。
    - 从算法效率上看，这种简单的乘法方式在处理大规模数据时，时间复杂度不是最优的，存在更高效的大数乘法算法，如 Karatsuba 算法等。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！