Ao dividir grandes números em pequenos, os pesquisadores excederam o limite fundamental de velocidade matemática
Quatro mil anos atrás, os habitantes da
Babilônia inventaram a multiplicação. E em março deste ano, os matemáticos melhoraram.
Em 18 de março de 2019, dois pesquisadores
descreveram o método mais rápido conhecido de multiplicar dois números muito grandes. O trabalho marca o culminar de uma busca de longa data pelo procedimento mais eficiente para realizar uma das operações básicas da matemática.
"Todo mundo pensa que o método de multiplicação que ensinou na escola é o melhor, mas, de fato, a pesquisa ativa está em andamento nessa área", diz
Joris van der Hoeven , matemático do Centro Nacional Francês de Pesquisa Científica, um dos coautores do trabalho.
A complexidade de muitos problemas computacionais, desde a contagem de novos dígitos do número π até a localização de números primos grandes, reduz a taxa de multiplicação. Van der Hoeven descreve seu resultado como uma atribuição de um tipo de limite de velocidade matemática para resolver muitos outros problemas.
"Na física, existem constantes importantes, como a velocidade da luz, que permitem descrever todos os tipos de fenômenos", disse van der Hoeven. "Se você deseja saber com que rapidez os computadores podem resolver certos problemas matemáticos, a multiplicação de números inteiros surge na forma de algum componente básico, com relação ao qual você pode expressar essa velocidade".
Quase todo mundo aprende a multiplicar números da mesma maneira. Escrevemos os números em uma coluna, multiplicamos o número superior por cada dígito da parte inferior (levando em consideração os dígitos) e adicionamos o resultado. Quando você multiplica dois números de dois dígitos, é necessário fazer quatro multiplicações menores para obter o resultado final.
O método escolar de "
transferência " requer n
2 etapas, onde n é o número de dígitos em cada um dos números multiplicados. Os cálculos com números de três dígitos requerem nove multiplicações e, com números de um dígito, 10.000.
O método de transferência funciona bem com números que consistem em vários dígitos, no entanto, começa a escorregar ao multiplicar números que consistem em milhões ou bilhões de dígitos (que é o que os computadores fazem ao calcular com precisão π ou ao
procurar grandes números primos em
todo o mundo ). Para multiplicar dois números com um bilhão de dígitos, você precisará produzir um bilhão de quadrados, ou 10
18 , multiplicações - isso levará cerca de 30 anos para um computador moderno.
Por vários milênios, acreditava-se que os números não podiam ser multiplicados mais rapidamente. Então, em 1960, o matemático soviético e russo de 23 anos,
Anatoly Alekseevich Karatsuba, participou de um seminário conduzido por
Andrei Nikolayevich Kolmogorov , um matemático soviético, um dos maiores matemáticos do século XX. Kolmogorov afirmou que não há método generalizado de multiplicação que exija menos de n
2 operações. Karatsuba decidiu que existia esse método - e após uma semana de pesquisa, ele o descobriu.
Anatoly Alekseevich KaratsubaA multiplicação do Karatsuba consiste em dividir os dígitos do número e combiná-los de uma nova maneira, o que permite, em vez de um grande número de multiplicações, realizar menos adições e subtrações. O método economiza tempo, pois a adição leva apenas 2n etapas, em vez de n2.
O método tradicional de multiplicação 25x63 requer quatro multiplicações de um dígito e várias adições
A multiplicação de Karatsuba 25x63 requer três multiplicações por um único número e várias adições e subtrações.
a) quebre os números
b) multiplicar dezenas
c) multiplicar unidades
d) some os números
e) multiplicar esses valores
f) considere e - b - c
g) colete o total de b, ce efÀ medida que o número de caracteres em números aumenta, o método Karatsuba pode ser usado recursivamente.
O método tradicional de multiplicar 2531x1467 requer 16 multiplicações por um único dígito.
A multiplicação de Karatsuba 2531x1467 requer 9 multiplicações."A adição na escola ocorre um ano antes, porque é muito mais simples, funciona em tempo linear, com a velocidade de leitura dos números da esquerda para a direita", disse
Martin Fuhrer , matemático da Pennsylvania State University, que criou o algoritmo de multiplicação mais rápido em 2007.
Ao lidar com grandes números, a multiplicação do Karatsuba pode ser repetida recursivamente, dividindo os números originais em quase tantas partes quanto os sinais neles. E com cada partição, você altera a multiplicação, que requer muitas etapas, para adição e subtração, que exigem muito menos etapas.
"Várias multiplicações podem ser transformadas em adições, uma vez que os computadores poderão fazer isso mais rapidamente", disse
David Harvey , matemático da Universidade de New South Wales e co-autor do novo trabalho.
O método Karatsuba tornou possível multiplicar números usando apenas n
1,58 multiplicações por um único dígito. Então, em 1971, Arnold Schönhage e Volker Strassen publicaram um método para multiplicar grandes números por n × log n × log (log n) pequenas multiplicações. Para multiplicar dois números de um bilhão de caracteres, cada método do Karatsuba exigirá 165 trilhões de etapas.
Joris van der Hoeven, matemático do Centro Nacional Francês de Pesquisa CientíficaO método Schönhage-Strassen é usado pelos computadores para multiplicar grandes números e levou a duas outras consequências importantes. Primeiro, ele introduziu uma técnica do campo de processamento de sinais chamada
Fast Fourier Transform . Desde então, essa técnica tem sido a base de todos os algoritmos de multiplicação rápida.
Em segundo lugar, no mesmo trabalho, Schönhage e Strassen sugeriram a possibilidade de um algoritmo ainda mais rápido - um método que requer apenas multiplicações n × log n por um sinal - e que esse algoritmo seja o mais rápido possível. Essa suposição foi baseada no sentimento de que, para uma operação tão fundamental como a multiplicação, a restrição de operações deve ser escrita de maneira mais elegante do que n × log n × log (log n).
“A maioria concorda que a multiplicação é uma operação básica tão importante que, do ponto de vista puramente estético, precisa de uma bela restrição de complexidade”, afirmou o Führer. "Por experiência, sabemos que a matemática das coisas básicas sempre acaba sendo elegante."
A restrição embaraçosa de Schönhage e Strassen, n × log n × log (log n), durou 36 anos. Em 2007, o
Führer quebrou esse recorde, e tudo aconteceu. Na última década, os matemáticos encontraram algoritmos de multiplicação cada vez mais rápidos, cada um dos quais rastejou gradualmente até a marca n × log n, não alcançando-a completamente. Então, em março deste ano, Harvey e van der Hoeven alcançaram.
O método deles é melhorar o excelente trabalho feito antes deles. Ele divide números em sinais, usa uma versão aprimorada da rápida transformação de Fourier e tira proveito de outras descobertas feitas nos últimos 40 anos. "Usamos a transformada rápida de Fourier muito mais grosseiramente, usamos várias vezes, não apenas uma, e substituímos ainda mais multiplicações por adição e subtração", disse van der Hoeven.
O algoritmo de Harvey e van der Hooven prova que a multiplicação pode ser feita em etapas n × log n. No entanto, ele não prova a ausência de um método mais rápido. Será muito mais difícil estabelecer que sua abordagem seja o mais rápido possível. No final de fevereiro, uma equipe de cientistas da computação da Universidade de Aarhus
publicou um artigo afirmando que, se um dos teoremas não comprovados for verdadeiro, esse método será realmente a maneira mais rápida de se multiplicar.
E, embora em teoria esse novo algoritmo seja muito importante, na prática ele não mudará muito, uma vez que apenas supera ligeiramente os algoritmos já usados. "Tudo o que podemos esperar é uma aceleração tríplice", disse van der Hoeven. "Nada além."
Além disso, os circuitos de equipamentos de computador foram alterados. Vinte anos atrás, os computadores executavam adição muito mais rápido que a multiplicação. A lacuna nas taxas de multiplicação e adição diminuiu drasticamente, como resultado, em alguns chips, a multiplicação pode até ultrapassar a adição. Usando certos tipos de equipamento, "você pode acelerar a adição forçando o computador a multiplicar números, e isso é meio louco", disse Harvey.
O equipamento muda com o tempo, mas os melhores algoritmos de sua classe duram para sempre. Independentemente da aparência dos computadores no futuro, o algoritmo Harvey e van der Hooven ainda será a maneira mais eficiente de multiplicar números.