Dois matemáticos da Austrália e da França criaram uma maneira alternativa de multiplicar números, enquanto resolviam um quebra-cabeça algorítmico que perplexa algumas das maiores mentes da matemática há quase meio século.

Para a maioria de nós, a maneira como multiplicamos números relativamente pequenos é lembrando tabuada – uma ajuda incrivelmente útil, pioneira nos babilônios há cerca de 4.000 anos atrás.

Mas e se os números aumentarem? Bem, se as cifras ficarem pesadas – e supondo que não temos uma calculadora ou computador, é claro – 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 duas números juntos.

Há apenas um problema com a multiplicação longa. É lento.

O motivo é lento porque, para cada dígito em cada número no problema, é necessário executar uma operação de multiplicação separada, antes de adicionar todos os produtos.

Isso pode não ser um problema para você e eu, que provavelmente raramente recorremos a uma multiplicação longa. Mas é uma desvantagem com a qual as crianças estão familiarizadas, percorrendo laboriosamente seus cálculos enquanto aprendem a mágica da multiplicação.

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.

Por acaso, os matemáticos realmente têm uma maneira de calcular apenas quão meticulosa 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 os dois números têm três dígitos (n = 3), o número de operações de multiplicação separadas envolvidas é realmente 9, o que é n2:

O problema é que, à medida que os números aumentam, a quantidade de trabalho envolvido também aumenta, sendo sempre representada por n ao poder de 2.

Embora seja ineficiente, o algoritmo de multiplicação longa period 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 descoberto este n1,58 foi 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 outros refinamentos também eram possíveis.

"Eles previram que deveria existir um algoritmo que multiplica nde dois dígitos usando essencialmente n * registro(n) operações básicas," Harvey explica.

"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 de Schönhage-Strassen, levaria menos de 30 segundos e, com seus prova teórica, seria ainda mais rápido – teoricamente – e pode até representar o algoritmo de multiplicação mais rápido que é matematicamente possível.

"Nesse sentido, espera-se que nosso trabalho seja o fim do caminho para esse problema, embora ainda não saibamos como provar isso rigorosamente", Harvey diz.

"As pessoas procuram esse algoritmo há quase 50 anos. Não foi 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", os pesquisadores explicar em uma FAQ, embora um exemplo que eles dêem no artigo seja 10214857091104455251940635045059417341952, que é um número muito, muito, muito grande.

A comunidade de matemática do mundo ainda está absorvendo as novas descobertas, que ainda precisam ser revisadas por pares, mas já estão causando ondas.

"Fiquei muito surpreso que isso tivesse sido feito", afirmou o cientista da computação teórico Martin Fürer, da Penn State college. contou Notícias científicas.

O próprio Fürer tentou reformular o algoritmo de Schönhage-Strassen mais de uma década atrás, mas acabou interrompendo o trabalho, dizendo Notícias científicas, "Pareceu-me bastante inútil".

Mas a esperança foi restaurada, desde que os matemáticos possam verificar o trabalho.

"Se o resultado estiver correto, é uma grande conquista na teoria da complexidade computacional", disse o matemático e cientista da computação Fredrik Johansson, do INRIA Bordeaux e do Instituto de Matemática de Bordeaux. New Scientist.

"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 não tenham revelado algo em suas provas.

"Muito do trabalho foi nos convencer de que é realmente correto", Harvey disse à AAP. "Ainda estou com medo de que possa acabar errado."

As descobertas pré-impressão estão disponíveis no Arquivo de acesso aberto HAL.

Uma versão desta história foi publicada pela primeira vez em abril de 2019.

Esta matéria foi traduzida e republicada. Clique aqui para acessar o website original.