Karatsuba算法实现:小ns工作，大ns中断

Question

我正在研究Karatsuba乘法算法的实现，但与大多数使用String作为主要数据结构而不是BigNumbers或longs的实现不同。我已经为这个问题写了一个递归的解决方案，它似乎适用于所有的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)。)