Algoritmo de multiplicação de inteiros
Os algoritmos de multiplicação usados para calcular o resultado da multiplicação .
Graficamente, trata-se de transformar um retângulo multiplicador × multiplicando em uma linha, mantendo o número de elementos.
Multiplicação baseada no número 2
Este tipo de multiplicação usa apenas adição e multiplicação ou divisão por 2. Não requer o conhecimento de uma tabuada (exceto a multiplicação por 2).
Multiplicação baseada em notação decimal
Este tipo de multiplicação usa decomposição decimal de números e requer que você multiplique cada dígito do primeiro número por cada dígito do segundo. Requer o conhecimento da tabuada de um dígito por outro. No entanto, diversos tipos de disposições foram adotados ao longo dos anos.
Multiplicação rápida
A maioria dos métodos descritos nas páginas anteriores exige que você multiplique cada dígito do multiplicador por cada dígito do multiplicando. Se esses dois números têm dígitos, isso requer produtos: dizemos que o cálculo tem uma complexidade em tempo quadrático, ou em .
não{\ displaystyle n}
não2{\ displaystyle n ^ {2}}
O(não2){\ displaystyle {\ mathcal {O}} (n ^ {2})}![{\ mathcal {O}} (n ^ {2})](https://wikimedia.org/api/rest_v1/media/math/render/svg/4441d9689c0e6b2c47994e2f587ac5378faeefba)
O advento dos computadores permitido e necessário o desenvolvimento de algoritmos mais rápidos para grandes números, os primeiros encontrados ter um tempo de complexidade da forma , onde um é um verdadeiro positivo estritamente menor que 1. Arnold Schönhage e Volker Strassen ter conjecturado em 1971 que o O produto de dois inteiros tem uma complexidade , ou seja, há um algoritmo com a complexidade do tempo, e nenhum tem melhor. A melhor complexidade atual é desde 2019 em, mas não é utilizável na prática, pois só é alcançada para números extremamente grandes, maiores do que no post original. Nenhum algoritmo com complexidade melhor do que a conjecturada foi encontrado e a conjectura de Schönhage e Strassen ainda é considerada válida em 2019. Todos os algoritmos abaixo foram desenvolvidos após 1960.
O(não1+no){\ displaystyle O (n ^ {1 + a})}
O(nãoregistronão){\ displaystyle O (n \ log n)}
O(nãoregistronão){\ displaystyle O (n \ log n)}
2172912{\ displaystyle 2 ^ {1729 ^ {12}}}![{\ displaystyle 2 ^ {1729 ^ {12}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a625fdee406fd86e23487b980533553a54b81706)
-
Algoritmo de Karatsuba : complexidade em aproximadamente em ; concebido em 1962, é o primeiro algoritmo de complexidade subquadrática;O(nãoregistro2(3)){\ displaystyle {\ mathcal {O}} (n ^ {\ log _ {2} (3)})}
O(não1,585){\ displaystyle {\ mathcal {O}} (n ^ {1.585})}![{\ displaystyle {\ mathcal {O}} (n ^ {1.585})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5eba32f5c76c88c72d3070410fc018ff4258919)
-
Algoritmo Toom-Cook ou "Toom3": complexidade em ou aproximadamente em ;O(nãoregistro3(5)){\ displaystyle {\ mathcal {O}} (n ^ {\ log _ {3} (5)})}
O(não1,465){\ displaystyle {\ mathcal {O}} (n ^ {1.465})}![{\ displaystyle {\ mathcal {O}} (n ^ {1.465})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef9534c266f5897c9ab8d85e89dcd6f011dcad85)
-
Algoritmo de Schönhage-Strassen , método usando a transformação rápida de Fourier : complexidade em , projetado em 1971;O(não⋅registronão⋅registroregistronão){\ displaystyle {\ mathcal {O}} (n \ cdot \ log n \ cdot \ log \ log n)}
![{\ displaystyle {\ mathcal {O}} (n \ cdot \ log n \ cdot \ log \ log n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e065976fa940be73d5b7b66952c527ea033914b4)
-
Algoritmo de Fürer : complexidade em , onde denota o logaritmo iterado e um número estritamente maior que 1, projetado em 2007;O(nãoregistronãoKO(registro∗não)){\ displaystyle {\ mathcal {O}} (n \ log nK ^ {O (\ log ^ {*} n)})}
registro∗não{\ displaystyle \ log ^ {*} n}
K{\ displaystyle K}![K](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b76fce82a62ed5461908f0dc8f037de4e3686b0)
- Algoritmos de Harvey e van der Hoeven publicados em 2019: complexidade em , mas inútil na prática.O(nãoregistronão){\ displaystyle {\ mathcal {O}} (n \ log n)}
![{\ displaystyle {\ mathcal {O}} (n \ log n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9981ede263cbf28215d3a70bf30f55db41a6e692)
Os processadores mais recentes implementam a multiplicação na forma de circuitos eletrônicos, mas que lidam apenas com números inteiros de tamanho limitado. Esses circuitos são chamados de multiplicadores .
Outras multiplicações
Notas e referências
-
(en) David Harvey e Joris Van Der Hoeven, “ multiplicação inteiro em tempo O (N log N) ” , HAL ,18 de março de 2019( leia online ).
-
Céline Deluzarche, " Esqueça seus multiplicação tabelas: aqui é um método novo e muito mais eficiente " , em Ciências Futura ,12 de abril de 2019.
-
A. Karatsuba e Yu. Ofman, " Multiplication of Many-Digital Numbers by Automatic Computers ", Proceedings of the USSR Academy of Sciences , vol. 145,1962, p. 293-294
-
Kheira Bettayeb, " La multiplication reinventé " , no CNRS ,15 de maio de 2019(acessado em 26 de junho de 2019 ) .
Veja também
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">