算法思想：通过减少乘法次数来提高效率。

算法步骤：

• 假设我们要计算两个大整数 x 和 y 的乘积，可以将 x 和 y 分别表示为：
  • x=a⋅10^m+b
  • y=c⋅10^m+d
• 其中 aa 和 bb 是 xx 的高 m 位和低 m 位，c 和 d 是 y 的高 m 位和低 m 位。那么：
  • x⋅y=(a⋅10^m+b)⋅(c⋅10^m+d) =ac⋅10^2m+(ad+bc)⋅10^m+bd
  • 这种传统算法我们需要计算 ac, adad, bcbc, 和 bdbd，共 4 次乘法。

Karatsuba 算法通过以下步骤减少乘法次数：

1. • 计算 z₂=a⋅c：
     • 计算高 m 位的乘积。
   • 计算 z₀=b⋅d：
     • 计算低 m 位的乘积。
   • 计算 z₁=(a+b)⋅(c+d)：
     • 计算 (a+b)(a+b) 和 (c+d)(c+d) 的乘积。
   • 计算 (z₁−z₂−z₀)⋅10^m：
     • 通过 z₁​ 减去 z_2​ 和 z₀​，得到 ad+bc 的值。
   • 最终结果：
     • 组合上述结果，得到最终的乘积： x⋅y=z₂⋅10^2m+(z₁−z₂−z₀)⋅10^m+z₀

经过这样的修改之后 Karatsuba 算法只需要 3 次乘法 z₁​ 、 z_2​ 和 z₀​就可以算出结果。

代码：

主方法：在 main 方法中，定义了大整数 x 和 y，调用 karatsuba 方法来计算他们的乘积。

public static void main(String[] args){
        //用户在屏幕上输入数字
        System.out.println("请输入两个数：");
        Scanner sc = new Scanner(System.in);
        String x = sc.next();
        String y = sc.next();
//        String x = "123456789";
//        String y = "987654321";
        System.out.println(karatsuba(x,y));
    }

				

					
				
				

					
				
				

					
				
				

					
				
			

karatsuba 方法：

• 首先是判断其中一个数的长度是否为 1，如果为 1 那就可以直接返回结果。
• 确保长度相同：通过在较短的字符串前面补零，使得两个字符串的长度相同并且都为偶数。padLeft 方法用于在字符串前面补零。
• 分割字符串：将每个字符串分成两部分，分别表示高 m 位和低 m 位。m 是字符串长度的一半。
• 递归调用
  • 计算 z₂=a⋅c
  • 计算 z₀=b⋅d
  • 计算 z₁=(a+b)⋅(c+d)
• 组装结果：
  • 计算 (z₁−z₂−z₀)⋅10^m
  • 最终结果为 x⋅y=z₂⋅10^2m+(z₁−z₂−z₀)⋅10^m+z₀

public static String karatsuba(String  x, String y){
    //当一个数的长度为1，则直接返回他们的乘积。
    if(x.length() == 1 || y.length()==1){
        return String.valueOf(Long.parseLong(x) * Long.parseLong(y));
    }
    //确保两个数的长度相同并且为偶数
    int n = Math.max(x.length(),y.length());
    //确保n是偶数
    n = n % 2 == 0 ? n : n+1;
    x = padLeft(x, n);
    y = padLeft(y, n);
    //分割字符串.substring 是 Java 中 String 类的一个内置方法，用于获取字符串的一部分。
    int m = n/2;
    String a = x.substring (0, m);//表示获取字符串x的前m个字符，即从索引0到m-1（包含m-1）。
    String b = x.substring(m);//表示获取字符串x的后m个字符，即从索引m开始到最后。
    String c = y.substring(0, m);
    String d = y.substring(m);
    // 递归计算 z2, z0, z1
    String z2 = karatsuba(a, c); // z2 = a * c
    String z0 = karatsuba(b, d); // z0 = b * d
    String z1 = karatsuba(add(a, b), add(c, d)); // z1 = (a + b) * (c + d)
 
    // 计算 (z1 - z2 - z0) * 10^m
    String part1 = multiplyByPowerOf10(z2, 2 * m);
    String part2 = multiplyByPowerOf10(subtract(subtract(z1, z2), z0), m);
    String part3 = z0;
 
    // 组装最终结果
    return add(add(part1, part2), part3);
}

				

					
				
				

					
				
				

					
				
				

					
				
			

辅助方法：

• padLeft：在字符串前面补零，使其达到指定长度。
• add 和 subtract：使用 Long.parseLong 将字符串转换为长整数，进行加法和减法操作。
• multiplyByPowerOf10：将字符串乘以 1010 的幂次方，通过在末尾添加零实现。

// 字符串加法
private static String add(String a, String b) {
    return String.valueOf(Long.parseLong(a) + Long.parseLong(b));
}

// 字符串减法
private static String subtract(String a, String b) {
    return String.valueOf(Long.parseLong(a) - Long.parseLong(b));
}
// 将字符串乘以 10 的幂次方
private static String multiplyByPowerOf10(String s, int power) {
    StringBuilder sb = new StringBuilder(s);
    for (int i = 0; i < power; i++) {
        sb.append('0');
    }
    return sb.toString();
}