Bueno, yo también soy bastante nuevo en la multiplicación y he tropezado con tu pregunta después de buscar el algoritmo de la multiplicación sobre la resolución de la multiplicación de dos números de 3 dígitos con sólo 5 multiplicaciones.
Así que...
-
Lo primero - con Karatsuba probablemente no puedas hacer esto. Derivado de la versión de 2 dígitos del algoritmo: $$ (10a + b) (10x + y) = 100ax + by + 10\Big( (a+b)(x+y) - ax - by\Big) $$ y aplicándolo recursivamente obtendremos $$ \Big( \; 10 (10a + b) + c \; \Big) \cdot \Big( \; 10 (10x + y) + z \; \Big) = 100 (10a+b)(10x+y) \;+\; cz \;+\; 10\Big( (10a+b+c)(10x+y+z) \; - \; (10a+b)(10x+y) \; - \; cz \Big) = 100 \Bigg( 100ax + by + 10 \Big( (a+b)(x+y) - ax - by \Big) \Bigg) \;+\; cz \;+\; 10\Bigg\{ 100ax \;+\; (b+c)(y+z) \;+\; 10\bigg[ \; (a+b+c)(x+y+z) \;-\; ax \;-\; (b+c)(y+z) \; \bigg] \;-\; \bigg[ \; 100ax \;+\; by \;+\; 10\Big( (a+b)(x+y) - ax - by \Big) \bigg] \;-\; cz \Bigg\} \;\;\;\; = \;\;\;\;10^4ax +10^2by +10^3(a+b)(x+y)-10^3ax-10^3by+cz+10^3ax+10(b+c)(y+z)+10^2(a+b+c)(x+y+z)-10^2ax-10^2(b+c)(y+z)-10^3ax-10by-10^2(a+b)(x+y)+10^2ax+10^2by-10cz \;\;\;\; = \;\;\;\; 10^4ax +10^3\Big( (a+b)(x+y)-ax-by \Big) + 10^2\Big( (a+b+c)(x+y+z)-(b+c)(y+z)-(a+b)(x+y)+2by\Big)+10\Big((b+c)(y+z)-by-cz\Big)+cz $$ Así se reduce el número de multiplicaciones necesarias a 6:
- hacha
- por
- cz
- (a+b)(x+y)
- (b+c)(y+z)
- (a+b+c)(x+y+z)
- Pero debería ser posible hacerlo con Multiplicación Toom-Cook algoritmo.
¿Qué idea hay detrás de esto? Sencillamente, en lugar de hacer cálculos, tratamos cada conjunto de números como un polinomio: $$ p(t) = at^2 + bt + c $$ $$ q(t) = xt^2 + yt + z $$
Y buscamos el polinomio:
$$ w(t) = p(q) \cdot q(t) = w_4 t^4 + w_3 t^3 + w_2 t^2 + w_1 t + w_0 $$
Como se puede ver fácilmente cada coeficiente $w_i$ de nuestro $w(t)$ polinomio es uno de los productos de la multiplicación. Para evitar la multiplicación de polinomios (que mataría el caso) intentaremos calcular los coeficientes de $w(t)$ utilizando la interpolación en nuestro $p(t)$ y $q(t)$ polinomios. Para ello necesitamos algunos puntos de interpolación. Para 5 variables ( $w_0,w_1,w_2,w_3,w_4$ ) necesitamos 5 puntos. Que sean (como en el artículo de la wikipedia) $t \in \{-2,-1,0,1,\infty\} $ .
Los puntos de evaluación del polinomio pueden ser los que usted desee. Pero es común elegir $0$ y $\infty$ entre ellos. En el caso de los polinomios con valor en $\infty$ no tiene mucho sentido, así que en lugar de esto estamos usando $$ p(\infty) = \lim_{t \to \infty} {{p(t)} \over {t^{deg(p)}}} $$
Y por lo tanto siempre es coeficiente de mayor poder (como $w_4$ en caso de $w(t)$ )
Una vez explicado esto vamos a probarlo:
$$ \begin{array}[b]{l} t=0 &&p(0) = c \\ &&q(0) = z \\ t=1 &&p(1) = a +b +c \\ &&q(1) = x +y +z \\ t=-1 &&p(-1) = a -b +c \\ &&q(-1) = x -y +z \\ t=-2 &&p(-2) = 4a-2b +c \\ &&q(-2) = 4x-2y +z \\ t=\infty &&p(\infty) = a \\ &&q(\infty) = x \end{array} $$ Lo que nos lleva a: $$ \begin{array}[b]{l} w(0) &&= w_0 &&= cz \\ w(1) &&= w_4 +w_3+w_2+w_1+w_0 &&= (a+b+c)(x+y+z) \\ w(-1) &&= w_4 -w_3+w_2-w_1+w_0 &&= (a-b+c)(x-y+z) \\ w(-2) &&= 16w_4-8w_3+4w_2-2w_1+w_0 &&= (4a-2b+c)(4x-2y+z)\\ w(\infty) &&= w_4 &&= ax \end{array} $$ Así vemos que sólo se necesitan 5 multiplicaciones de esas sumas específicas y ya casi estamos.
Para acelerar las cosas, vamos a utilizar la representación matricial de las ecuaciones anteriores:
$$ \begin{pmatrix} w(0) \\ w(1) \\ w(-1)\\ w(-2)\\ w(\infty) \end{pmatrix} = \begin{pmatrix} 1 && 0 && 0 && 0 && 0 \\ 1 && 1 && 1 && 1 && 1 \\ 1 && -1 && 1 && -1 && 1 \\ 16 && -8 && 4 && -2 && 1 \\ 0 && 0 && 0 && 0 && 1 \end{pmatrix} \cdot \begin{pmatrix} w_0 \\ w_1 \\ w_2 \\ w_3 \\ w_4 \end{pmatrix} $$
Usando la inversa de esta matriz (tomada directamente de Wikipedia):
$$ \begin{pmatrix} w_0 \\ w_1 \\ w_2 \\ w_3 \\ w_4 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1/2 & 1/3 & -1 & 1/6 & -2 \\ -1 & 1/2 & 1/2 & 0 & -1 \\ -1/2 & 1/6 & 1/2 & -1/6 & 2 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} w(0) \\ w(1) \\ w(-1) \\ w(-2) \\ w(\infty) \end{pmatrix} $$ Lo que nos lleva a: $$ \begin{array}[b]{l} w_0 = cz \\ w_1 = \frac {w(0)} 2 + \frac {w(1)} 3 - w(-1) + \frac {w(-2)} 6 -2 w(\infty) \\ w_2 = -w(0) + \frac {w(1)} 2 + \frac {w(-1)} 2 - w(\infty) \\ w_3 = -\frac{w(0)} 2 + \frac{w(1)} 6 + \frac{w(-1)} 2 - \frac{w(-2)} 6 + 2 w(\infty) \\ w_4 = ax \end{array} $$ Y por último: $$ \begin{array}[b]{l} w_0 = cz \\ w_1 = \frac {cz} 2 + \frac {(a+b+c)(x+y+z)} 3 - (a-b+c)(x-y+z) + \frac {(4a-2b+c)(4x-2y+z)} 6 -2 ax \\ w_2 = -cz + \frac {(a+b+c)(x+y+z)} 2 + \frac {(a-b+c)(x-y+z)} 2 - ax \\ w_3 = -\frac{cz} 2 + \frac{(a+b+c)(x+y+z)} 6 + \frac{(a-b+c)(x-y+z)} 2 - \frac{(4a-2b+c)(4x-2y+z)} 6 + 2 ax \\ w_4 = ax \end{array} $$
Editar:
Para aquellos que quieran usar esas ecuaciones como soporte para alguna programación (como yo mismo - necesitaba esto para mi propia clase de enteros de 96 bits):
-
Tenga en cuenta el desbordamiento - especialmente con la adición, ya que puede ser fácilmente pasado por alto, pero sucederá - especialmente cuando se suman 3 segmentos con multiplicadores como 16, etc.
-
Un coste bastante importante (algorítmicamente hablando) es la división aquí - aunque será "división exacta" (ver en la biblioteca matemática GMP) por lo que significa que siempre saldrá sin ningún recordatorio (por lo que es más barato) y puede ser precalculado (ya sea por el compilador o tú en ensamblador o lo que sea)
-
Puede intentar experimentar con diferentes puntos de interpolación para obtener números de división/multiplicación "más adecuados", aunque ir más allá de 8/-8 parece poco práctico, ya que alcanzará rápidamente los límites de desbordamiento o perjudicará la precisión (depende de si se trata de números enteros o en coma flotante)
PS. Por favor, indíqueme cualquier error que haya cometido, tanto en inglés como en las ecuaciones
