Teoria do Big Bang Teoria do Big Bang
Home

Matemáticos descobriram uma maneira totalmente nova de multiplicar números muito grandes

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 nossas tabelas - uma ajuda incrivelmente útil, pioneira pela primeira vez pelos 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 dois 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 o quão difícil é a multiplicação longa.

O problema é que, à 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 o 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 sua 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", diz Harvey.

"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 idéia", explicam os pesquisadores 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 com o fato de ter sido feito", disse à Science News o cientista da computação Martin Fürer, da Penn State University.

O próprio Fürer tentou reformular o algoritmo Schönhage-Strassen há mais de uma década, mas acabou interrompendo o trabalho, dizendo à Science News: "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 à New Scientist o matemático e cientista da computação Fredrik Johansson, do INRIA Bordeaux e do Instituto de Matemática de Bordeaux.

"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", disse Harvey à 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.