Karatsuba vs. Schönhage-Strassen para la multiplicación de polinomios

Question

Me pregunto cómo multiplicar de manera más efectiva dos polinomios con varios cientos de coeficientes, cada coeficiente con $1000$-$2000$ dígitos decimales.

Sé que Schönhage-Strassen comienza a ser más efectivo que Karatsuba entre $10,000$ y $40,000$ dígitos. Mi pregunta es, ¿no vale la pena SS porque hay mucho menos de $10,000$ coeficientes, o vale la pena porque un polinomio tiene más de $100,000$ dígitos en total?

Answer 1

Aquí hay un truco que he usado algunas veces que te permite multiplicar dos polinomios enteros usando una sola multiplicación de enteros grande. De esta manera, puedes evitar la división de tu algoritmo de multiplicación entre el nivel de polinomios y el nivel de enteros.

Sean $$p(x) = a_0 + a_1x + \cdots + a_mx^m, \quad q(x) = b_0 + b_1x + \cdots + b_nx^n,$$ tus dos polinomios y sea $$r(x) = p(x)q(x) = c_0 + c_1x + \cdots + c_{m+n}x^{m+n}$$ el producto a ser calculado.

Para calcular este producto, primero evalúa $P = p(2^k)$ y $Q = q(2^k)$ para algún valor de $k$ lo suficientemente grande y luego calcula el producto entero $R = PQ$ (usando Schönhage-Strassen ya que $P$ y $Q$ serán bastante grandes). Nota que $$R = r(2^k) = c_0 + c_12^k + \cdots + c_{m+n}2^{k(m+n)}.$$

Si se eligió $k$ de manera que $|c_i| < 2^{k-1}$ para $i = 0, 1, \dots, m+n$, entonces podemos recuperar $r(x)$ de $R$ de la siguiente manera. Dado que $c_0 \equiv R \pmod{2^k}$ y $|c_0| < 2^{k-1}$, se sigue que $c_0$ es el número de valor absoluto más pequeño que es congruente a $R$ módulo $2^k$. Así, si $r_0$ es el residuo (no negativo) de dividir $R$ por $2^k$, entonces $c_0 = r_0$ cuando $r_0 < 2^{k-1}$ y $c_0 = r_0 - 2^k$ cuando $r_0 > 2^{k-1}$. Sea $$R' = \frac{R-c_0}{2^k} = c_1 + c_2 2^k + \cdots + c_{m+n}2^{k(m+n-1)}$$ y repite el mismo proceso para extraer $c_1$ de $R'$, y así sucesivamente hasta que se recuperen todos los coeficientes de $r(x)$.

Es importante tener en cuenta que evaluar $P = p(2^k)$, $Q = q(2^k)$ y recuperar $r(x)$ de $R$ son operaciones de bajo costo en una computadora binaria ya que la multiplicación y división por potencias de $2$ solo implican desplazar bits a la izquierda y a la derecha. Además, se puede elegir un exponente adecuado $k$ sabiendo solamente $p(x)$ y $q(x)$, por ejemplo, basta con seleccionar $k$ de modo que $$\min(m,n)\max(|a_0|,|a_1|,\dots,|a_m|)\max(|b_0|,|b_1|,\dots,|b_n|) < 2^{k-1}.$$

Answer 2

Si la longitud de los bits de los coeficientes y el grado del polinomio no difieren demasiado*, es más eficiente ejecutar directamente la DFT en los coeficientes del polinomio. De lo contrario, la técnica descrita por François (sustitución de Kronecker) es más rápida.

Ver página 4 de esta presentación.

* - deben estar dentro de un factor de aproximadamente 2

Answer 3

Empecemos recordando que hay otros algoritmos entre Karatsuba y SS: por ejemplo, Toom, que puede ser mejor en cierto intervalo.

Estoy de acuerdo con Dorais, el truco de Kronecker (mapear polinomios multivariados a univariados, luego polinomios a enteros) puede valer la pena intentarlo, en particular si ya tienes una buena librería para aritmética de enteros (por ejemplo, GMP), y también se aplica mutatis mutandis también con coeficientes en un campo o anillo Z_n.

Por cierto, el umbral exacto entre Karatsuba, (Toom,) y SS depende en gran medida de los detalles de implementación (y la CPU, cachés, asignación de memoria...), pero está conectado aproximadamente al tamaño total del resultado. Es decir: no depende solo del tamaño de los coeficientes, sino de ambos coeficientes y grado. En cierto sentido, el truco de Kronecker muestra por qué.