Matemáticos descobrem o método perfeito para multiplicar números grandes

Quatro mil anos atrás, os babilônios inventaram a multiplicação. Este ano, os matemáticos aperfeiçoaram-no.

Em 18 de março, dois pesquisadores descreveram o método mais rápido já descoberto para multiplicar dois números muito grandes. O documento marca a culminação de uma longa pesquisa para encontrar o procedimento mais eficiente para realizar uma das operações mais básicas em matemática.

"Todo mundo pensa basicamente que o método que você aprende na escola é o melhor, mas na verdade é uma área ativa de pesquisa", disse Joris van der Hoeven, matemático do Centro Nacional Francês de Pesquisa Científica e um dos co-autores. .

A complexidade de muitos problemas computacionais, desde calcular novos dígitos de pi até encontrar grandes números primos, se resume à velocidade de multiplicação. Van der Hoeven descreve seu resultado como uma espécie de limite matemático de velocidade para a rapidez com que muitos outros tipos de problemas podem ser resolvidos.

"Na física, você tem constantes importantes, como a velocidade da luz, que permitem descrever todos os tipos de fenômenos", disse van der Hoeven. “Se você quiser saber com que velocidade os computadores podem resolver certos problemas matemáticos, a multiplicação de números inteiros aparece como um tipo de tijolo básico de construção em relação ao qual você pode expressar esse tipo de velocidade.”

A maioria das pessoas aprende a multiplicar-se da mesma maneira. Nós empilhar dois números, multiplicar cada dígito no número inferior por cada dígito no número superior e fazer adição no final. Se você está multiplicando dois números de dois dígitos, acaba realizando quatro multiplicações menores para produzir um produto final.

A escola primária ou o método de "transporte" exige cerca de n² etapas, em que n é o número de dígitos de cada um dos números que você está multiplicando. Portanto, números de três dígitos exigem nove multiplicações, enquanto números de 100 dígitos exigem 10.000 multiplicações.

O método de transporte funciona bem para números com apenas alguns dígitos, mas é difícil quando estamos multiplicando números com milhões ou bilhões de dígitos (que é o que os computadores fazem para calcular com precisão pi ou como parte da pesquisa mundial de primos grandes) . Para multiplicar dois números com 1 bilhão de dígitos, é necessário 1 bilhão de quadrados, ou 1018 multiplicações, o que levaria um computador moderno por volta dos 30 anos.

Durante milênios, foi amplamente assumido que não havia maneira mais rápida de se multiplicar. Então, em 1960, o matemático russo Anatoly Karatsuba, de 23 anos de idade, realizou um seminário liderado por Andrey Kolmogorov, um dos grandes matemáticos do século XX. Kolmogorov afirmou que não havia procedimento geral para fazer multiplicação que exigisse menos de n² etapas. Karatsuba pensou que havia - e depois de uma semana de busca, ele encontrou.

O método de Karatsuba envolve dividir os dígitos de um número e recombiná-los de uma maneira inovadora que permite substituir um pequeno número de adições e subtrações por um grande número de multiplicações. O método economiza tempo porque a adição leva apenas 2n etapas, ao contrário das n² etapas.

Leia a matéria completa, em inglês, aqui: https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/