Karatsuba算法实施:用于小型NS的工作，为较大的NS休息

Question

我正在研究乘以数字的karatsuba算法的实现，但是与大多数使用字符串作为主要数据结构而不是bignumbers或longs的实现不同。我已经为这个问题编写了递归解决方案，该解决方案似乎适用于所有N＆lt;6，但由于某种原因，尽管所有基本案例都在起作用，但它无法在奇数ns大于6中工作。这是该计划的Karatsuba部分，在调试中留下了一些印刷品。我使用的所有方法都应按预期工作，我对它们进行了彻底的测试。对于值因子1 =" 180"和factor2 =" 109"，将输出正确的结果。对于值factor1 =" 1111"和factor2 =" 1111"，将输出正确的结果。对于因子1 =" 2348711"和factor2 =" 8579294"程序输出" 20358060808034"何时应该输出" 20150282190034"。我已经尝试了回顾逻辑，但找不到完全出错的地方。如果有人对某些东西可能无法工作有任何见识，那么对任何帮助都表示赞赏。

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)。）