Multiplicação de número inteiro quando um número inteiro é fixo

Seja um número inteiro positivo fixo de tamanho bits.$A$$n$

É permitido pré-processar esse número inteiro, conforme apropriado.

Dado outro número inteiro positivo de tamanho bits, qual é a complexidade da multiplicação ?m A $B$$m$$AB$

Observe que já temos os algoritmos . A questão aqui é se podemos tomar \ epsilon = 0 por algo mais inteligente? ϵ = $(\max(n,m))^{1+\epsilon}$$\epsilon=0$

Embora nem sempre seja o algoritmo mais eficiente, esta questão tem uma relação muito próxima com cadeias de adição; qualquer algoritmo para calcular rapidamente por cadeias de adição se traduz em um algoritmo para calcular por adição repetida (cada adição, obviamente, é uma operação ). Por outro lado, um algoritmo rápido para calcular para qualquer leva a um algoritmo rápido para calcular , mas é claro que esse algoritmo não precisa necessariamente ter a forma de uma cadeia de adição; Ainda assim, parece um excelente lugar para começar. Dê uma olhada em http://en.wikipedia.org/wiki/Addition_chain ou confira o vol. 2 def ( B ) = A B O ( n ) A B B AUMA$A$$A$$f(B) = AB$$O(n)$$AB$$B$$A$The Art Of Computer Programming para mais detalhes.

Para expandir a idéia de Steven Stadnicki, podemos rapidamente construir um algoritmo ingênuo que se sai melhor do que a multiplicação de matrizes usando a Transformada Discreta de Fourier.

Contamos o número de uns em . Se menos da metade dos bits forem um, construímos uma lista vinculada de suas posições. Para multiplicar, simplesmente deslocamos para cada posição da lista (multiplicando pelo bit representado) e adicionamos os resultados.$A$$B$

Se mais da metade dos bits são um, fazemos o mesmo que acima, mas usamos os zeros para preencher a lista de posições. A idéia é que subtrairemos essa soma da soma que seria obtida multiplicando por todas. Para obter a soma de todos, alteramos pelo número de bits em e subtraímos disso. Em seguida, podemos subtrair nossa soma obtida da lista vinculada.A $B$$A$$B$

Podemos chamar isso de ingênuo algoritmo de lista vinculada. Seu tempo de execução é no pior caso, mas no caso médio, que é mais rápido que o DFT para pequenos.O ( | B | $O(n^2)$$O(|B| \sqrt{\frac{|A|}{2\pi}})$$|A|$

Para usar a idéia de listas de maneira ideal, usamos dividir e conquistar. Dividimos ao meio e localizamos os tamanhos das listas associadas usando o algoritmo ingênuo. Se eles são maiores que 5, chamamos o algoritmo ingênuo novamente em metades maiores que 5 até conseguirmos cortar todas as metades para menos de cinco. (Isso ocorre porque podemos reduzir isso para 4 subtrações)$A$

Ainda melhor ainda, melhoramos nosso algoritmo de dividir e conquistar. Repetimos todas as combinações possíveis de ramificação, escolhendo avidamente a melhor. Esse pré-processamento leva aproximadamente o mesmo tempo que a multiplicação real.

Se nos for permitida liberdade infinita com o pré-processamento, resolveremos o algoritmo otimizado de dividir e conquistar para todos os ramos da melhor maneira possível. Isso leva tempo na pior das hipóteses, mas deve ser ótimo pelos métodos da cadeia de adição.$O(2^{|A|})$

Estou trabalhando no cálculo de valores mais exatos para os algoritmos acima.

O artigo chamado Multiplicação por uma constante é sublinear ( PDF ) fornece um algoritmo para operações de deslocamento / adição , em que é o tamanho da constante .$\mathcal{O}\left(\frac{n}{\log n}\right)$$n$

Essencialmente, ele funciona procurando os bits na constante, alterando e adicionando o número a ser multiplicado apenas para os bits na constante (como multiplicação longa para binário, onde um bit no número inferior a ser multiplicado significa a parte superior não é deslocado e adicionado, enquanto um bit significa a parte superior é deslocada e adicionado). No entanto, isso ainda é , porque pode haver bits na constante.1 0 1 O ( n ) O ( n ) $1$$1$$0$$1$$\mathcal{O}\left(n\right)$$\mathcal{O}(n)$ $1$

O artigo então fala sobre a alteração da representação numérica da constante no sistema de números de base dupla, onde aparentemente os bits não- são mais escassos, se a conversão for feita corretamente (é um sistema numérico muito redundante). Eles calculam o quão escasso é; o número de bits diferentes de zero é limitado a menos que , portanto, há um número sublinear de adições necessárias. No entanto, ainda são operações reais , devido ao custo de cada adição (onde é o tamanho de a constante e é o tamanho do outro 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$

Portanto, para responder sua pergunta, sim, há um resultado semelhante à multiplicação de vetores matriciais, pois você obtém um speedup se for constante; mas é claro que essa aceleração é apenas sobre multiplicação longa ingênua e existem algoritmos de multiplicação que são muito melhores que você pode obter esse algoritmo.O ( n $\log n$$\mathcal{O}\left(\frac{n^2} {\log n}\right)$

Conforme sugerido por Matt Groff, você pode estar interessado em procurar inspiração na comunidade de praticantes (ou se na sua situação estiver dentro da largura de bits de uma CPU atual). De fato, o problema da multiplicação de números inteiros por uma constante foi considerado por muitos escritores de compiladores e projetistas de circuitos, embora eles geralmente estejam interessados ​​em "multiplicadores sem multiplicadores" (multiplique usando shift, add e subtrair). Uma das primeiras referências que conheço é (eu aprendi isso na seção 8.4 do Hacker's Delight).$n$

Bernstein, R. (1986), Multiplicação por constantes inteiras. Software: Practice and Experience, 16: 641–652. doi: 10.1002 / spe.4380160704

Um trabalho mais moderno de Vincent Lefèvre pode ser encontrado aqui (não deixe de ver os trabalhos de acompanhamento dele), e ele também observa um projeto da CMU sobre a síntese eficiente de circuitos (veja as referências ali). O último projeto ainda considera a multiplicação simultânea por um conjunto de constantes.

PS: Convido você a mudar seu nome de usuário para algo reconhecível.

Não tenho certeza se isso é diretamente relevante para a questão, mas o seguinte resultado elementar pode ser interessante. Dado um número natural fixo , a operação pode ser realizada por um autômato seqüencial, desde que seja escrito em notação binária invertida (ou seja, Menos Pouco Significativo Primeiro). O número de estados do autômato é onde é a maior potência de divide . Por exemplo, a operação é realizada pelo seguinte autômato. 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 exemplo, e . Assim, no binário reverso, é escrito como e (má escolha, eu sei ...) como . O processamento da entrada neste autômato fornece o caminho $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 fornece a saída correta . O tipo de autômato seqüencial que estou usando aqui foi chamado subsequencial por Schützenberger: como você pode ver, existe um prefixo inicial (em verde) e uma função de saída do terminal$\color{blue}{01101010001}$(também em verde). Para mais detalhes de como esta máquina seqüencial pode ser computada de forma sistemática, consulte este link .