Реализация алгоритма Карацубы: работает для малых нс, разрывы для больших нс - PullRequest
Новая
       35

Реализация алгоритма Карацубы: работает для малых нс, разрывы для больших нс

1 голос
/ 20 марта 2019

Я работаю над реализацией алгоритма умножения чисел Карацубы, но в отличие от большинства реализаций, использующих Strings в качестве основной структуры данных вместо BigNumbers или longs. Я написал рекурсивное решение проблемы, которая, кажется, работает для всех n <6, но по какой-то причине она не работает для нечетных ns больше 6, несмотря на то, что все базовые случаи работают. Вот часть программы karatsuba, с несколькими отпечатками, оставленными после отладки. Все методы, используемые в этом, должны работать как задумано, я тщательно их протестировал. Для значения factor1 = "180" и factor2 = "109" выводится правильный результат. Для значения factor1 = "1111" и factor2 = "1111" выводится правильный результат. Для factor1 = "2348711" и factor2 = "8579294" программа выдает "20358060808034", когда она должна вывести "20150282190034". Я попытался вернуться к логике, и я не могу найти, где именно это идет не так. Если у кого-то есть понимание того, где что-то может не работать, любая помощь приветствуется. </p> 

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));
}

1 Ответ

1 голос
/ 21 марта 2019

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

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

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

...