Где ошибка в этом, очевидно, -O (n lg n) алгоритме умножения?

15

Недавнее сообщение в блоге о поиске трех равномерно распределенных приводит меня к вопросу о стековом потоке с главным ответом, который утверждает, что сделал это за O (n lg n) время. Интересная часть состоит в том, что решение включает возведение в квадрат полинома, ссылаясь на статью, которая описывает, как сделать это за O (n lg n) времени .

Теперь умножение многочленов практически совпадает с умножением чисел. Единственная реальная разница - отсутствие переносчиков. Но ... переносы также могут быть выполнены за O (n lg n) времени. Например:

    var value = 100; // = 0b1100100

    var inputBitCount = value.BitCount(); // 7 (because 2^7 > 100 >= 2^6)
    var n = inputBitCount * 2; // 14
    var lgn = n.BitCount(); // 4 (because 2^4 > 14 => 2^3)
    var c = lgn + 1; //5; enough space for 2n carries without overflowing

    // do apparently O(n log n) polynomial multiplication
    var p = ToPolynomialWhereBitsAreCoefficients(value); // x^6 + x^5 + x^2
    var p2 = SquarePolynomialInNLogNUsingFFT(p); // x^12 + 2x^11 + 2x^10 + x^8 + 2x^7 + x^4
    var s = CoefficientsOfPolynomial(p2); // [0,0,0,0,1,0,0,2,1,0,2,2,1]
    // note: s takes O(n lg n) space to store (each value requires at most c-1 bits)

    // propagate carries in O(n c) = O(n lg n) time
    for (var i = 0; i < n; i++)
        for (var j = 1; j < c; j++)
            if (s[i].Bit(j))
                s[i + j].IncrementInPlace();

    // extract bits of result (in little endian order)
    var r = new bool[n];
    for (var i = 0; i < n; i++)
        r[i] = s[i].Bit(0);

    // r encodes 0b10011100010000 = 10000

Итак, мой вопрос заключается в следующем: где здесь ошибка? Умножение чисел в O (n lg n) - гигантская открытая проблема в информатике, и я действительно очень сомневаюсь, что ответ будет таким простым.

  • Носит неправильно или нет O (n lg n)? Я выяснил, что для отслеживания переносов достаточно lg n + 1 бита на значение, а алгоритм настолько прост, что я бы удивился, если бы он ошибался. Обратите внимание, что хотя отдельное приращение может занять O (LG N) времени, совокупная стоимость для приращений X составляет O (X).
  • Является ли алгоритм полиномиального умножения из статьи неправильным или есть условия, которые я нарушаю? В статье используется быстрое преобразование Фурье вместо теоретико-числового преобразования, что может быть проблемой.
  • Много ли умных людей пропустили очевидный вариант алгоритма Шёнхаге-Штрассена за 40 лет? Это кажется наименее вероятным.

Я на самом деле написал код для реализации этого, за исключением эффективного полиномиального умножения (я пока недостаточно хорошо понимаю теоретико-числовое преобразование). Похоже, что случайное тестирование подтверждает правильность алгоритма, поэтому проблема, скорее всего, заключается в анализе временной сложности.

Крейг Гидни
источник
Разве квадрат не должен включать x^10 + 2x^8? x ^ 10 только один раз (x ^ 5 * x ^ 5) и x ^ 8 дважды (x ^ 6 * x ^ 2 + x ^ 2 * x ^ 6)
Sjoerd
Я сделал пример вручную. Я сделал арифметическую ошибку. Сожалею. Я действительно реализовал алгоритм, протестировал его и получил правильные результаты.
Крейг Гидни

Ответы:

13

О(журналN) . Арифметика на них не приходит бесплатно. Вы должны применить конструкцию рекурсивно, и вы что-то потеряете.

Юваль Фильмус
источник
1

«Ошибка» здесь заключается в том, что преобразование Фурье можно вычислить за O (n log n) шагов сложения или умножения чисел, подлежащих преобразованию, но по мере того, как n становится действительно большим, преобразованные числа также увеличиваются, что добавляет еще один фактор, журнал журнала N.

На практике я бы подумал, что использования плавающей запятой с квадратичной точностью (128-битная с плавающей запятой с использованием двух двойных значений) или 128-битной фиксированной точки в БПФ будет достаточно для любого продукта, который достаточно мал, чтобы рассчитываться вообще.

gnasher729
источник