- Multiplicar grandes números é difícil. Em 1971, dois professores alemães previram um algoritmo que facilitaria as coisas, mas ninguém nunca o provou.
- Até agora.
- Os matemáticos da Austrália e França dizem que o seu algoritmo pode tornar a multiplicação e outros tipos de aritmética muito mais eficiente.
Desde a escola primária, a multiplicação complexa tem sido uma dor de cabeça. Mas um professor assistente da Universidade de New South Wales Sydney na Austrália desenvolveu um novo método para multiplicar números gigantes juntos que é mais eficiente do que a “longa multiplicação”, tantos são ensinados em idade precoce.
“Mais tecnicamente, nós provamos uma conjectura de Schönhage e Strassen de 1971 sobre a complexidade da multiplicação inteira”, diz o professor associado David Harvey no vídeo abaixo.
O algoritmo Schönhage-Strassen, desenvolvido por dois matemáticos alemães, foi na verdade o método mais rápido de multiplicação de 1971 a 2007. Embora um método mais rápido tenha sido desenvolvido em 2007, ele é raramente usado hoje em dia.
Schönhage e Strassen previram que um algoritmo multiplicando números n-dígitos usando n * log(n) operações básicas deveria existir, diz Harvey. O seu trabalho é a primeira prova conhecida de que existe.
Harvey escolhe o exemplo de 314 multiplicado por 159 – uma grande equação, claro, mas muito maior é usada todos os dias em cenários da vida real. Para resolver o problema, a maioria das pessoas é ensinada a multiplicar cada número individual em conjunto, e depois somar as somas:
9 é multiplicado por 4, 1, e 3; depois 5 é multiplicado por 4, 1, e 3, e assim por diante. O resultado termina com produtos de 9 dígitos por dígito.
Este método é chamado n2 ou n ao quadrado, porque é necessário multiplicar n por n um número de vezes. Ele obterá a resposta correta, mas Schönhage e Strassen projetaram um método mais rápido. Ele foi capaz de passar de n2 para algo menor, mas um desafio ainda se apresentou na forma de n * log(n).
Para alguns, ver uma palavra no meio de um problema matemático pode ser o suficiente para fazer seus olhos brilharem como fizeram na classe de álgebra. Como um refresher: log é a abreviação de logaritmo, que ajuda as pessoas a decifrar expoentes que fazem números ao quadrado ou ao cubo ou até mesmo algo mais alto. Então 2⁵ é 32, mas expresso logaritmo, pareceria log₂(32)=5. Embora possa parecer uma boca cheia, os logaritmos são cruciais quando os números ficam muito maiores.
O método Schönhage-Strassen é muito rápido, diz Harvey. Se um computador usasse o método ao quadrado ensinado na escola em um problema onde dois números tinham um bilhão de dígitos cada um, levaria meses. Um computador usando o método Schönhage-Strassen poderia fazer isso em 30 segundos.
Mas se os números continuarem a subir até aos triliões e mais além, o algoritmo desenvolvido por Harvey e pelo colaborador Joris van der Hoeven na École Polytechnique na França poderia encontrar soluções mais rapidamente do que o algoritmo Schönhage-Strassen de 1971.
“Significa que você pode fazer todo tipo de aritmética de forma mais eficiente, por exemplo, divisão e raízes quadradas”, diz ele. “Você também poderia calcular dígitos de pi mais eficientemente do que antes. Tem até aplicações para problemas envolvendo números primos enormes.
“Há quase 50 anos que as pessoas andam à procura de um algoritmo assim”, continua ele. Não era uma conclusão falsa que alguém acabaria por ser bem sucedido. Pode ter-se verificado que Schönhage e Strassen estavam errados, e que tal algoritmo não é possível.
“Mas agora nós sabemos melhor”, diz ele.