1

我正在研究一个数字相乘的 Karatsuba 算法的实现，但与大多数使用字符串作为主要数据结构而不是 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));
}
4

1 回答 1

1

我注意到两个问题：

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

（请注意，前两个受控语句可以组合：
if (factor1.length() &lt;= 1 && factor2.length() &lt;= 2)。）

于 2019-03-21T14:00:52.793 回答