Por que matemáticos ainda não sabem o algoritmo mais rápido para multiplicar

O problema que parece simples mas não e

Multiplicar dois números. Parece trivial, certo? Você aprendeu isso na terceira serie. Mas para números com milhões ou bilhoes de dígitos - como os usados em criptografia moderna e calculo científico de alta precisão - a pergunta "qual e o algoritmo mais rápido possível para multiplicar dois números?" continua em aberto na matemática e na ciência da computação.

Um artigo recente da Scientific American revisitou esse problema e gerou mais de 80 comentários no Hacker News. A razão? Porque matemáticos e cientistas da computação ainda não sabem se o algoritmo mais rápido já conhecido e realmente o ideal, ou se existe algo ainda mais eficiente esperando para ser descoberto.

Para desenvolvedores, esse problema não e apenas académico. A multiplicação de grandes inteiros e o coração da criptografia RSA, do processamento de números em precisão arbitrária (BigInteger, Python's int, Java's BigInteger) e de cálculos científicos. Entender como funciona abre uma janela para como as bibliotecas que você usa todos os dias foram otimizadas.

Como funciona a multiplicação "normal"

O algoritmo que você aprendeu na escola - multiplicar cada digito de um número por cada digito do outro e somar tudo - e chamado de algoritmo de multiplicação longa (long multiplication). Para números com n dígitos, ele faz O(n^2) operações básicas.

O que significa O(n^2)? Se você dobrar o tamanho dos números (de 100 para 200 dígitos), o tempo de multiplicação quadruplica. Para números com 1 milion de dígitos, o algoritmo escolar faria um quadrilhao de operações - completamente impraticável.

Por décadas, acreditou-se que O(n^2) era o melhor possível. Era "óbvio" que você precisava olhar para cada par de dígitos pelo menos uma vez. Em 1960, o matemático russo Anatoly Karatsuba provou que essa intuição estava errada - e derrubou a suposição com um algoritmo elegante que reduzia o trabalho para O(n^1.585).

A ideia genial de Karatsuba

O algoritmo de Karatsuba usa uma técnica chamada dividir e conquistar. Para multiplicar dois números A e B de n dígitos cada, você os divide ao meio:

A = A_alto * base^(n/2) + A_baixo
B = B_alto * base^(n/2) + B_baixo

A multiplicação clássica de (A_alto * base + A_baixo) * (B_alto * base + B_baixo) requer 4 multiplicações de números menores. A sacada de Karatsuba: com um truque algébrico, da para fazer o mesmo trabalho com apenas 3 multiplicações de números menores. Recursivamente aplicado, isso reduz a complexidade de O(n^2) para O(n^1.585).

# Implementação básica do algoritmo de Karatsuba em Python
def karatsuba(x, y):
    # Caso base: multiplicação simples para números pequenos
    if x < 10 or y < 10:
        return x * y

    n = max(len(str(x)), len(str(y)))
    m = n // 2

    # Divide os números ao meio
    a, b = divmod(x, 10**m)
    c, d = divmod(y, 10**m)

    # Apenas 3 multiplicações recursivas em vez de 4
    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    ad_plus_bc = karatsuba(a + b, c + d) - ac - bd

    return ac * 10**(2*m) + ad_plus_bc * 10**m + bd

# Teste
print(karatsuba(1234, 5678))  # 7006652

A corrida pelos algoritmos mais rápidos

Após Karatsuba, a corrida estava lançada. Se O(n^2) não era o limite, até onde podia-se chegar?

Em 1971, Schonhage e Strassen publicaram um algoritmo revolucionário baseado na Transformada Rápida de Fourier (FFT). O algoritmo de Schonhage-Strassen tem complexidade O(n log n log log n) - muito mais rápido que Karatsuba para números muito grandes. Esse algoritmo foi o estado da arte por quase 50 anos.

Em 2019, os matemáticos David Harvey e Joris van der Hoeven publicaram um algoritmo que quebrou a barreira: O(n log n). Isso e o melhor que se pode teoricamente esperar, pois só para escrever a resposta (n dígitos) já e preciso fazer n operações. A pergunta e: e isso o ótimo? Pode existir algo mais rápido?

Por que isso importa para desenvolvedores

Se os números que você usa não tem bilhoes de dígitos, por que isso é relevante? Porque os fundamentos importam:

Criptografia RSA e ECC: chaves RSA de 4096 bits envolvem multiplicação de números de centenas de dígitos. Cada operação criptográfica faz dezenas ou centenas dessas multiplicações. A eficiência do algoritmo de multiplicação afeta diretamente a velocidade das suas conexões HTTPS.

Python e números grandes: Python usa inteiros de precisão arbitrária nativamente. Quando você escreve 2 ** 1000000 em Python, ele usa algoritmos otimizados de multiplicação. Entender isso ajuda a prever quando operações com números grandes vao ser lentas.

Bibliotecas de alto desempenho: GMP (GNU Multiple Precision), usado em quase toda linguagem de programação para aritmética de precisão arbitrária, implementa Karatsuba, Schonhage-Strassen e outros algoritmos avançados automaticamente baseado no tamanho dos números.

# Comparação de desempenho em Python
import timeit

# Números grandes para teste
a = 2 ** 10000  # número com ~3011 dígitos
b = 3 ** 10000

# Python usa Karatsuba automaticamente para esses números
tempo = timeit.timeit(lambda: a * b, number=1000)
print(f"1000 multiplicações de ~3000 dígitos: {tempo:.3f}s")

# Para números menores, usa multiplicação longa
x = 123456789
y = 987654321
tempo2 = timeit.timeit(lambda: x * y, number=1000000)
print(f"1M multiplicações de inteiros pequenos: {tempo2:.3f}s")

Comparação dos principais algoritmos

Veja como os algoritmos evoluíram ao longo do tempo:

• Multiplicação longa (tradicional): O(n^2) - prático até números de algumas dezenas de dígitos. O algoritmo que você aprendeu na escola.
• Algoritmo de Karatsuba (1960): O(n^1.585) - usado em Python nativo, GMP, OpenSSL para números de centenas a milhares de dígitos.
• Toom-Cook (1963): generalização do Karatsuba, O(n^1.465) para Toom-3. Usado em GMP para números intermediários.
• Schonhage-Strassen (1971): O(n log n log log n) - baseado em FFT. Estado da arte por quase 50 anos, ainda usado em produção para números muito grandes.
• Harvey-Hoeven (2019): O(n log n) - teoricamente ótimo, mas prático apenas para números absurdamente grandes que não existem em aplicações reais hoje.

A questão em aberto: O(n log n) e o melhor possível? Existe uma prova matemática de que nenhum algoritmo pode ser mais rápido? Até agora, não. E isso que mantem o problema "aberto".

Pontos que tornam o problema fascinante

Por que é tao difícil provar o limite inferior:

• Para provar que O(n log n) e ótimo, precisaria provar que qualquer algoritmo de multiplicação terá que fazer pelo menos n log n operações no pior caso - algo que os matemáticos não sabem fazer ainda
• A teoria de complexidade computacional ainda não tem ferramentas suficientes para provar a maioria dos limites inferiores que intuitivamente parecem corretos
• E similar ao problema P vs NP: todo mundo acredita que o limite existe, mas provar e outra historia

A beleza do progresso: de O(n^2) em 1960 para O(n log n) em 2019, a melhora e enorme para números grandes. Para n = 1 milhão de dígitos, a diferença entre O(n^2) e O(n log n) e de 50 bilhoes de vezes mais rápido.

Casos de uso reais onde isso importa

Quando a multiplicação eficiente de grandes números afeta o seu código?

Criptografia assimétrica: RSA, Diffie-Hellman e outros protocolos baseados em teoria dos números fazem centenas de multiplicações de números com centenas ou milhares de bits em cada handshake TLS. Toda conexão HTTPS que você faz depende dessas multiplicações sendo rápidas.

Criptomoedas: Bitcoin e outras criptos usam curvas elípticas sobre campos finitos. A multiplicação de pontos numa curva elíptica e feita com multiplicações de inteiros grandes. Cada transação validada envolve varias dessas operações.

Computação científica: simulações físicas, calculo de constantes matemáticas com precisão astronómica (pi com trilhoes de casas decimais), análise numérica de alta precisão - todos dependem de multiplicação rápida de inteiros enormes.

Computadores quânticos: o algoritmo de Shor, que quebraria RSA em computadores quânticos, basicamente e um algoritmo eficiente para fatorar números grandes - e a multiplicação e central para isso.

Dicas e boas práticas para devs

Estudar esses algoritmos também é útil para entrevistas técnicas: problemas sobre divisão e conquista, análise de complexidade e recursao aparecem frequentemente. E o algoritmo de Karatsuba e um exemplo clássico que muitos entrevistadores adoram mencionar.

Vale a pena entender isso?

Para quem sim: desenvolvedores que trabalham com criptografia, computação científica, ou que simplesmente gostam de entender como as coisas funcionam por baixo dos panos. Também para quem esta estudando algoritmos e quer ver um exemplo real de por que complexidade computacional importa na prática.

Para quem não e urgente: se você trabalha com aplicações web típicas ou mobile, dificilmente vai precisar multiplicar números com milhares de dígitos manualmente. Mas entender que Python e Java fazem isso automaticamente por você - e com algoritmos muito mais sofisticados do que O(n^2) - e útil para ter uma intuição correta sobre quando operações com números grandes vao ser lentas.

Próximo passo: implemente o algoritmo de Karatsuba do zero em Python ou na sua linguagem favorita. E um exercício excelente de recursao e divisão e conquista, demora menos de uma hora, e você sai com uma compreensão real de como otimizações matemáticas impactam o desempenho computacional.