java - Karasuba 算法实现 : works for small ns, 因更大的 ns 而中断

Question

我正在研究 Karatsuba 数字乘法算法的实现，但与大多数使用字符串而不是 BigNumber 或 long 的实现不同。我已经为该问题编写了一个递归解决方案，该解决方案似乎适用于所有 n < 6，但由于某种原因，它无法适用于大于 6 的奇数 ns，尽管所有基本情况都有效。这是程序的 karatsuba 部分，其中有一些调试留下的打印结果。这里使用的所有方法都应该按预期工作，我对它们进行了彻底的测试。对于值factor1 =“180”和factor2 =“109”，输出正确的结果。对于值factor1 =“1111”和factor2 =“1111”，将输出正确的结果。对于factor1 =“2348711”和factor2 =“8579294”，程序在应该输出“20150282190034”时输出“20358060808034”。我尝试回溯逻辑，但找不到到底哪里出了问题。如果有人对某些地方可能不起作用有任何见解，我们将不胜感激。

public static String multiply(String factor1, String factor2) {
    // base case of length = 1
    System.out.println("Factor1 " + factor1 + " factor2 " + factor2);
    if (factor1.length() == 1 && factor2.length() == 1) {
        return smallNumberMultiplication(factor1, factor2);
    } else if (factor1.length() == 1 && factor2.length() == 2) { //these conditions needed for odd-size #s
        return smallNumberMultiplication(factor1, factor2); // max iteration = 10
    } else if (factor1.length() == 2 && factor2.length() == 1) {
        return smallNumberMultiplication(factor2, factor1); // max iteration = 10
    }

    // check which factor is smaller, find the index at which the value is split
    int numberLength = factor1.length();
    int middleIndex = numberLength / 2;
    // Find the power to which 10 is raised such that it follows Karatsuba's algorithm for ac
    int powerValue = numberLength + numberLength % 2;

    // divide both numbers into two parts bounded by middleIndex place
    String[] tempSplitString = splitString(factor1, middleIndex);
    String f1Large = tempSplitString[0], f1Small = tempSplitString[1];
    tempSplitString = splitString(factor2, middleIndex);
    String f2Large = tempSplitString[0], f2Small = tempSplitString[1];

    String multiplyHighestNumbers, multiplySmallestNumbers, multiplyMiddleNumbers;
    // large factor1 * large factor2
    multiplyHighestNumbers = multiply(f1Large, f2Large);
    // Multiply (f1Large + f1Small)*(f2Large + f2Small)
    multiplyMiddleNumbers = multiply(addTwoValues(f1Large, f1Small), addTwoValues(f2Large, f2Small));
    // small factor1 * small factor2
    multiplySmallestNumbers = multiply(f1Small, f2Small);

    // add trailing zeros to values (multiply by 10^powerValue)
    String finalHighestNumber = addTrailingZeros(multiplyHighestNumbers, powerValue);
    String finalMiddleNumber = addTrailingZeros(
            subtractTwoValues(subtractTwoValues(multiplyMiddleNumbers, multiplyHighestNumbers),
                    multiplySmallestNumbers),
            powerValue / 2);
    String finalSmallestNumber = multiplySmallestNumbers;

    // add each part together
    return removeLeadingZeros(addTwoValues(addTwoValues(finalHighestNumber, finalMiddleNumber), finalSmallestNumber));
}

Answer 1

我注意到两个问题:

• 使用不同的值进行分割 ( middleIndex ) 和移位 ( powerValue )(不必要地通过添加零来实现)。
  对于 productHighParts ("multiplyHighestNumbers ") 要在长度上更接近其他产品，请使用 (factor1.length() + factor2.length()) / 4 (两个因子平均长度的一半)。
• 这个长度必须是 splitString() 中不太重要的部分的长度，不是主要部分。

(请注意，前两个受控语句可以组合:
if (factor1.length() <= 1 && factor2.length() <= 2) .)