Java实现Karatsuba算法处理64位数字输入报NumberFormatException问题

你写的String版Karatsuba有三处致命问题，直接触发异常且无法支持64位大数计算：

• 字符串拆分逻辑完全没做长度对齐：拆分c和d时用的是x长度算出的half值，没有校验y的长度是否匹配。递归过程中一旦出现两个乘数字符串长度不一致的情况，短字符串调用substring(half)时会因为起始索引超过字符串最大下标返回空串，传入下一层递归后执行Long.parseLong("")就会抛出你看到的NumberFormatException。比如x长度为2、y长度为1时，half=1，y.substring(1)得到的就是空字符串。
• 全程依赖Long类型做中间运算完全失去了String处理大数的意义：64位十进制数的乘积是128位，远超过long类型最大支持的19位十进制数上限，就算解决了空串问题，计算大数字时必然出现数值溢出，得到错误结果甚至直接抛数值范围异常。
• 递归边界逻辑有漏洞：只判断了x的长度，没有统一处理两个乘数的长度关系，递归拆分时很容易出现长度不匹配的问题。

1. 每次递归进入后首先对两个数字字符串做前导补零，对齐到相同长度，再按统一长度计算拆分位置，从根源上避免截取到空串。
2. 彻底移除所有Long.parseLong相关的转换逻辑，自己实现三个基础的大数字符串操作：加法、减法（保证被减数大于减数，无负数场景）、乘以10的n次幂（直接在字符串末尾补对应数量的0即可），所有运算全程用字符串完成，才能突破long的长度限制。
3. 调整递归终止条件：当两个对齐后的数字长度为1时，直接计算个位数乘积返回即可。

public class IntegerMultipl {
    public static void main(String[] args) {
        // 测试64位大数相乘
        String num1 = "1234567890123456789012345678901234567890123456789012345678901234";
        String num2 = "9876543210987654321098765432109876543210987654321098765432109876";
        System.out.println(karatsuba(num1, num2));
    }

    // 字符串大数加法，无负数
    private static String add(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int i = a.length() - 1, j = b.length() - 1;
        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;
            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';
            sb.append(sum % 10);
            carry = sum / 10;
        }
        return sb.reverse().toString();
    }

    // 字符串大数减法，默认a >= b，无负数
    private static String subtract(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int borrow = 0;
        int i = a.length() - 1, j = b.length() - 1;
        while (i >= 0) {
            int digitA = (a.charAt(i--) - '0') - borrow;
            int digitB = j >= 0 ? (b.charAt(j--) - '0') : 0;
            borrow = 0;
            if (digitA < digitB) {
                digitA += 10;
                borrow = 1;
            }
            sb.append(digitA - digitB);
        }
        // 去掉计算结果前导零
        while (sb.length() > 1 && sb.charAt(sb.length() - 1) == '0') {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.reverse().toString();
    }

    // 数字字符串乘10的n次幂，直接末尾补n个0
    private static String multiplyByPow10(String num, int pow) {
        StringBuilder sb = new StringBuilder(num);
        for (int i = 0; i < pow; i++) {
            sb.append('0');
        }
        return sb.toString();
    }

    public static String karatsuba(String x, String y) {
        // 补前导零对齐两个数字长度
        int maxLen = Math.max(x.length(), y.length());
        StringBuilder xPad = new StringBuilder(x);
        while (xPad.length() < maxLen) xPad.insert(0, '0');
        StringBuilder yPad = new StringBuilder(y);
        while (yPad.length() < maxLen) yPad.insert(0, '0');
        x = xPad.toString();
        y = yPad.toString();

        int len = x.length();
        // 递归终止：个位数直接计算乘积
        if (len == 1) {
            int product = (x.charAt(0) - '0') * (y.charAt(0) - '0');
            return String.valueOf(product);
        }

        int half = len / 2;
        String a = x.substring(0, len - half);
        String b = x.substring(len - half);
        String c = y.substring(0, len - half);
        String d = y.substring(len - half);

        String ac = karatsuba(a, c);
        String bd = karatsuba(b, d);
        String abCd = karatsuba(add(a, b), add(c, d));
        String gauss = subtract(subtract(abCd, ac), bd);

        // 按Karatsuba公式拼接结果：ac * 10^(2*half) + gauss * 10^half + bd
        String part1 = multiplyByPow10(ac, 2 * half);
        String part2 = multiplyByPow10(gauss, half);
        return add(add(part1, part2), bd);
    }
}

内容的提问来源于stack exchange，提问作者Beatrice z.jiang