Блог

Я работаю над реализацией алгоритма умножения чисел Карацубы, но в отличие от большинства реализаций, использующих строки в качестве основной структуры данных вместо значений или длин. Я написал рекурсивное решение проблемы, которое, похоже, работает для всех n < 6, но по какой-то причине оно не работает для нечетных ns, превышающих 6, несмотря на то, что все базовые варианты работают. Вот часть программы, посвященная karatsuba, с несколькими отпечатками, оставшимися после отладки. Все методы, используемые в этом, должны работать так, как задумано, я тщательно их протестировал. Для значений factor1 = «180» и factor2 = «109» выводится правильный результат. Для значений factor1 = «1111» и factor2 = «1111» выводится правильный результат. Для factor1 = «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 amp;amp; factor2.length() == 1) {
        return smallNumberMultiplication(factor1, factor2);
    } else if (factor1.length() == 1 amp;amp; factor2.length() == 2) { //these conditions needed for odd-size #s
        return smallNumberMultiplication(factor1, factor2); // max iteration = 10
    } else if (factor1.length() == 2 amp;amp; 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));
}
  

Я заметил две проблемы:

• использование разных значений для разделения ( middleIndex ) и сдвига ( powerValue ) (без необходимости реализуется путем привязки нулей).
  Чтобы productHighParts (« multiplyHighestNumbers «) был ближе по длине к другим продуктам, используйте (factor1.length() factor2.length()) / 4 (половину средней длины обоих факторов).
• эта длина должна быть длиной менее значимой части в splitString() , а не главной части.

(Обратите внимание, что первые два управляемых оператора могут быть объединены:
if (factor1.length() <= 1 amp;amp; factor2.length() <= 2) .)