Dois matemáticos da Austrália e da França criaram uma maneira nova forma de multiplicar números, enquanto resolviam um quebra-cabeça algorítmico que deixaria algumas das maiores mentes da matemática há quase meio século, no mínimo perplexos.
Multiplicar números pequenos pode ser muito fácil. Mas e se os números aumentarem? Bem, se as cifras ficarem pesadas a maioria de nós passaria a uma multiplicação longa: outro truque útil que aprendemos na escola e uma técnica confiável para multiplicar basicamente dois números juntos. Mas existe um problema com a multiplicação longa. É lento.
Mais significativamente, é um problema para os computadores, uma vez que seus próprios gargalos na execução de cálculos são impostos pelos limites da matemática abstrata que nós mesmos podemos compreender.
Basicamente, a multiplicação longa é um algoritmo, mas não é particularmente eficiente, pois o processo é inevitavelmente trabalhoso.
LEIA TAMBÉM: A matemática, finalmente, tem uma explicação científica do porquê suas juntas estalarem
Por acaso, os matemáticos realmente descobriram uma nova forma de calcular o quão difícil é a multiplicação longa.
Como o matemático David Harvey, da UNSW na Austrália, explica no vídeo abaixo, em uma multiplicação em que ambos os números têm três dígitos ( n = 3), o número de operações de multiplicação separadas envolvidas é na verdade 9, que é n 2:
À medida que os números aumentam, a quantidade de trabalho envolvido também aumenta, sempre sendo representada por n à potência de 2.
Embora seja ineficiente, o algoritmo de multiplicação longa era na verdade o algoritmo de multiplicação mais avançado que tínhamos até a década de 1960, quando o matemático russo Anatoly Karatsuba descobriu que n 1,58 era possível.
Uma década depois, dois matemáticos alemães fizeram outra descoberta: o algoritmo de Schönhage-Strassen, que conjeturou – mas nunca provou – que refinamentos adicionais também eram possíveis.
“Eles previram que deveria existir um algoritmo que multiplica números de n dígitos usando essencialmente operações básicas de n * log ( n )”, explica Harvey.
“Nosso artigo fornece o primeiro exemplo conhecido de um algoritmo que consegue isso”.
Segundo os pesquisadores, multiplicar dois números com um bilhão de dígitos cada pelo processo de multiplicação longa levaria meses para ser computados.
Usando o algoritmo Schönhage-Strassen, levaria menos de 30 segundos e, com a prova teórica, seria ainda mais rápido – teoricamente – e pode até representar o algoritmo de multiplicação mais rápido e matematicamente possível.
LEIA TAMBÉM: Matemática pode ajudar a prever como células do câncer se desenvolvem
“Nesse sentido, espera-se que nosso trabalho seja o fim do caminho para esse problema, embora ainda não saibamos como provar isso rigorosamente”, diz Harvey .
“As pessoas procuram esse algoritmo há quase 50 anos. Não foi com uma conclusão perdida que alguém acabaria sendo bem-sucedido”.
Vale a pena notar que o novo algoritmo só seria útil para multiplicar números muito grandes. Quão grande exatamente?
“Não temos ideia”, explicam os pesquisadores em uma FAQ, embora um exemplo que eles dão no artigo seja 10 214857091104455251940635045059417341952, que é um número muito, muito, muito grande. A comunidade matemática do mundo ainda está absorvendo as novas descobertas, que ainda precisam ser revisadas por pares.
O próprio Fürer tentou reformular o algoritmo Schönhage-Strassen há mais de uma década, mas acabou interrompendo o trabalho, disse ele “Pareceu-me bastante inútil”.
“Se o resultado estiver correto, é uma grande conquista na teoria da complexidade computacional”, disse à New Scientist o matemático e cientista da computação Fredrik Johansson, do INRIA Bordeaux e do Instituto de Matemática de Bordeaux.
LEIA TAMBÉM: A definição do quilograma mudou para sempre. E agora é baseada em física quântica
“As novas idéias neste trabalho provavelmente inspirarão mais pesquisas e poderão levar a melhorias práticas no futuro”.
Enquanto isso, Harvey e seu co-pesquisador, Joris van der Hoeven, da École Polytechnique na França, dizem que seu algoritmo precisa ser otimizado, e eles apenas esperam que tenham revelado algo em seus testes.
“Muito do trabalho foi nos convencer de que é realmente correto”, disse Harvey à AAP. “Ainda estou com medo de que possa acabar dando errado.”
As descobertas estão disponíveis no arquivo de acesso aberto HAL.
FONTE / Science Alert
