java - Karatsuba 乘法 java 递归代码不起作用？

Question

我正在尝试使用 karatsuba 乘法将两个数字相乘。我的 java 代码不工作。我使用字符串作为参数和参数，以便我们可以将两个 n 位数字相乘(n 是偶数)。另外，我不想使用 long 或 BigInteger。请帮我找出我的代码错误。

class karat{

public static String karatsuba(String first, String second){

    if(first.length() <= 1 || second.length() <= 1)
        return String.valueOf(Long.parseLong(first)*Long.parseLong(second));

    String a = karatsuba(first.substring(0, first.length()/2), second.substring(0, second.length()/2));

    String b = karatsuba(first.substring(first.length() - first.length()/2, first.length()), second.substring(second.length() - second.length()/2, second.length()));

    String c = karatsuba(String.valueOf(Long.parseLong(first.substring(0, first.length()/2)) + Long.parseLong(first.substring(first.length() - first.length()/2, first.length()))), String.valueOf(Long.parseLong(second.substring(0, second.length()/2)) + Long.parseLong(second.substring(second.length() - second.length()/2, second.length()))));

    String d = String.valueOf(Long.parseLong(c) - Long.parseLong(b) - Long.parseLong(a));

    return String.valueOf(((int)Math.pow(10, first.length()))*(Long.parseLong(a)) + (((int)Math.pow(10, first.length()/2))*Long.parseLong(d)) + (Long.parseLong(c)));
}

public static void main(String[] args){
        String result = karatsuba("1234", "5678");
        System.out.println(result); }
}

能否请您完善我的代码。

通过乘法的数字 - 1234 和 5678

输出是 - 6655870(不正确)

输出应该是 - 7006652(正确)

谢谢

Answer 1

首先，我尝试查看您的代码，这让程序员迷失了方向，在我们进入解决方案之前需要做一些事情。

一般建议。像您一样将字符串转换为值并前后转换不是好习惯，它不会像这样工作。我也试过调试你的代码，这只是魔鬼圈。

所以我将从检查值长度和最大值开始。

如果其中一个值的长度小于 2，则意味着所有小于 10 的东西都进行乘法运算，否则进行 karatsuba 递归算法。

解决方法如下:

public static long karatsuba(long num1, long num2) {

    int m = Math.max(
            String.valueOf(num1).length(),
            String.valueOf(num2).length()
    );

    if (m < 2)
        return num1 * num2;

    m = (m / 2) + (m % 2);

    long b = num1 >> m;
    long a = num1 - (b << m);
    long d = num2 >> m;
    long c = num2 - (d << m);

    long ac = karatsuba(a, c);
    long bd = karatsuba(b, d);
    long abcd = karatsuba(a + b, c + d);

    return ac + (abcd - ac - bd << m) + (bd << 2 * m);
}

一些测试；

public static void main(String[] args) {
    System.out.println(karatsuba(1, 9));
    System.out.println(karatsuba(1234, 5678));
    System.out.println(karatsuba(12345, 6789));
}

输出将是

9
7006652
83810205

它比您的 Stringish 代码更轻松。顺便说一句，该解决方案的灵感来自 pesudo在维基和这个class .