Multiplicación de enteros cuando un entero es fijo

Sea un entero positivo fijo de tamaño bits.$A$$n$

Se permite preprocesar este número entero según corresponda.

Dado otro entero positivo de tamaño bits, ¿cuál es la complejidad de la multiplicación ?m A $B$$m$$AB$

Tenga en cuenta que ya tenemos algoritmos . La pregunta aquí es si podemos tomar \ epsilon = 0 por algo más inteligente. ϵ = $(\max(n,m))^{1+\epsilon}$$\epsilon=0$

Si bien no siempre será el algoritmo más eficiente, esta pregunta tiene una relación muy estrecha con las cadenas de adición; cualquier algoritmo para calcular rápidamente mediante cadenas de adición se traduce en un algoritmo para calcular mediante adición repetida (cada adición, por supuesto, es una operación ). Por el contrario, un algoritmo rápido para calcular para cualquier conduce a un algoritmo rápido para calcular , pero, por supuesto, este algoritmo no necesariamente tiene que tener la forma de una cadena de adición; Aún así, parece un excelente lugar para comenzar. Echa un vistazo a http://en.wikipedia.org/wiki/Addition_chain o echa un vistazo a vol. 2 def ( B ) = A B O ( n ) A B B AA$A$$A$$f(B) = AB$$O(n)$$AB$$B$$A$El arte de la programación de computadoras para más detalles.

Para ampliar la idea de Steven Stadnicki, podemos construir rápidamente un algoritmo ingenuo que funcione mejor que la multiplicación de matrices usando la Transformada discreta de Fourier.

Contamos el número de unos en . Si menos de la mitad de los bits son unos, construimos una lista vinculada de sus posiciones. Para multiplicar, simplemente desplazamos hacia la izquierda por cada posición en la lista (multiplicando por ese bit que está representado) y agregamos los resultados.$A$$B$

Si más de la mitad de los bits son unos, hacemos lo mismo que arriba, pero en su lugar usamos los ceros para completar la lista de posiciones. La idea es que restaremos esta suma de la suma que se obtendría multiplicando por todas. Para obtener la suma de todos, cambiamos por el número de bits en y restamos de esto. Entonces podemos restar nuestra suma obtenida de la lista vinculada.A $B$$A$$B$

Podemos llamar a eso el ingenuo algoritmo de lista enlazada. Su tiempo de ejecución es en el peor de los casos, pero en el caso promedio, que es más rápido que DFT para pequeños.O ( | B | $O(n^2)$| A$O(|B| \sqrt{\frac{|A|}{2\pi}})$$|A|$

Para utilizar la idea de listas de manera óptima, utilizamos divide y vencerás. Dividimos por la mitad y encontramos los tamaños de las listas asociadas utilizando el algoritmo ingenuo. Si son mayores que 5, llamamos al algoritmo ingenuo nuevamente en mitades mayores a 5 hasta que logremos cortar todas las mitades a menos de cinco. (Esto se debe a que podemos reducir esto a 4 restas)$A$

Aún mejor, mejoramos nuestro algoritmo de divide y vencerás. Recorremos todas las combinaciones posibles de ramificación, escogiendo con avidez la mejor. Este preprocesamiento tarda aproximadamente el mismo tiempo que la multiplicación real.

Si se nos permite una libertad infinita con el preprocesamiento, resolvemos el algoritmo optimizado de dividir y conquistar para todas las ramas de manera óptima. Esto lleva tiempo en el peor de los casos, pero debería ser ~ óptimo mediante métodos de cadena de adición.$O(2^{|A|})$

Estoy trabajando en calcular valores más exactos para los algoritmos anteriores.

El artículo llamado Multiplicación por una constante es sublineal ( PDF ) proporciona un algoritmo para las operaciones de desplazamiento / suma , donde es el tamaño de la constante .$\mathcal{O}\left(\frac{n}{\log n}\right)$$n$

Esencialmente, funciona buscando los bits en la constante, cambiando y sumando el número que se multiplicará solo para esos bits en la constante (como la multiplicación larga para binario, donde un bit en el número inferior para multiplicar significa la parte superior no se desplaza y agrega, mientras que bit significa que la parte superior se desplaza y agrega). Sin embargo, esto sigue siendo , porque puede haber bits en la constante.1 0 1 O ( n ) O ( n ) $1$$1$$0$$1$$\mathcal{O}\left(n\right)$$\mathcal{O}(n)$ $1$

Luego, el documento habla sobre cambiar la representación numérica de la constante en el sistema de números de doble base, donde aparentemente, los bits que no son son más dispersos, si la conversión se realiza correctamente (es un sistema de números muy redundante). Calculan cuán escaso es; el número de bits distintos de cero está limitado a menos de , por lo tanto, se requiere un número sublineal de adiciones. Sin embargo, todavía es operaciones reales, debido al costo de cada adición (donde es el tamaño de la constante, es el tamaño del otro número).O ( n ) O ( n $0$$\mathcal{O}(n)$O(m)n$\mathcal{O}\left(\frac{nm} {\log n}\right)$$\mathcal{O}(m)$$n$$m$

Entonces, para responder a su pregunta, sí, hay un resultado similar a la multiplicación de matriz-vector, en el sentido de que obtiene un speedup si es constante; pero, por supuesto, esta aceleración solo es sobre la ingenua multiplicación larga, y existen algoritmos de multiplicación que son mucho mejores que que puedes obtener con este algoritmoO ( n $\log n$$\mathcal{O}\left(\frac{n^2} {\log n}\right)$

Según lo sugerido por Matt Groff, puede interesarle buscar inspiración en la comunidad de práctica (o si en su situación está dentro del ancho de bits de una CPU actual). De hecho, el problema de la multiplicación de enteros por una constante ha sido considerado por muchos escritores de compiladores y diseñadores de circuitos, aunque generalmente están interesados ​​en "multiplicador sin multiplicador" (multiplicar usando shift, add y sustract). Una de las primeras referencias que conozco es (lo aprendí de la sección 8.4 de Hacker's Delight):$n$

Bernstein, R. (1986), Multiplicación por constantes enteras. Software: práctica y experiencia, 16: 641–652. doi: 10.1002 / spe.4380160704

Un trabajo más moderna de Vincent Lefèvre se puede encontrar aquí (asegúrese de ver trabajos de seguimiento para él), y él también toma nota de un proyecto de CMU en la síntesis eficiente circuito (ver las referencias allí). El último proyecto incluso considera la multiplicación simultánea por un conjunto de constantes.

PD: te animo a que consideres cambiar tu nombre de usuario a algo reconocible.

No estoy seguro de si esto es directamente relevante para la pregunta, pero el siguiente resultado elemental podría ser de interés. Dado un número natural fijo , la operación puede realizarse mediante un autómata secuencial, siempre que se escriba en notación binaria inversa (es decir, el bit menos significativo primero). El número de estados del autómata es donde es la mayor potencia de divisiones . Por ejemplo, la operación se realiza mediante el siguiente autómata. n → k n n k / 2 r 2 r 2 k n → 6 $k$$n \to kn$$n$$k/2^r$$2^r$$2$$k$$n \to 6n$

Por ejemplo, y . Por lo tanto, en binario inverso, se escribe como y (mala elección, lo sé ...) como . El procesamiento de la entrada en este autómata proporciona la ruta $185 = 1 + 8 + 16 + 32 + 128$$6 \times 185 = 1110 = 2 + 4 + 16 + 64 + 1024$$185$$10011101$$1110$$01101010001$$\color{red}{10011101}$

$$\xrightarrow{\color{green}0} 0 \xrightarrow{\color{red}1\mid \color{blue}1} 1 \xrightarrow{\color{red}0\mid \color{blue}1} 0 \xrightarrow{\color{red}0\mid \color{blue}0} 0 \xrightarrow{\color{red}1\mid \color{blue}1} 1 \xrightarrow{\color{red}1\mid \color{blue}0} 2 \xrightarrow{\color{red}1\mid \color{blue}1} 2 \xrightarrow{\color{red}0\mid \color{blue}0} 1 \xrightarrow{\color{red}1\mid \color{blue}0} 2 \xrightarrow{\color{green}{01}}$$ que proporciona la salida correcta . El tipo de autómata secuencial que estoy usando aquí fue llamado subsecuencial por Schützenberger: como puede ver, hay un prefijo inicial (en verde) y una función de salida de terminal$\color{blue}{01101010001}$(también en verde). Para obtener más detalles sobre cómo se puede calcular esta máquina secuencial de manera sistemática, consulte este enlace .