As crianças aprendem a tabuada na escola. Memorize-os. Boa sorte com números de três dígitos. É aí que os algoritmos entram em ação. Você empilha os dígitos. Multiplique linha por linha. Durante milhares de anos, pensamos que isso era o melhor que podíamos fazer. É lento. Brutalmente lento para big data. Então, em 1960, um jovem de 23 anos mudou tudo. O mistério da velocidade de multiplicação permanece em aberto.
Por que é importante
Multiplicação não é apenas lição de casa. Ele administra a internet. Criptografia, IA, processamento de áudio. Tudo isso depende da multiplicação. Multiplicação pesada. Quando você multiplica números enormes milhões de vezes por segundo, cada passo conta. Um ligeiro ganho de eficiência economiza bilhões.
Veja o método da escola primária. Dois dígitos significam quatro multiplicações de um único dígito. Três dígitos? Nove. Ele é dimensionado quadraticamente. Dobre o comprimento, quadruplique o trabalho. Dobre novamente, o trabalho aumenta dezesseis vezes. Os cientistas da computação ignoram os segundos. O hardware acelera de qualquer maneira. Eles contam passos. Chamamos isso de notação Big O. A escola primária é O (n ^ 2). Quadrático. Se o seu número aumentar em 1.000, o trabalho explodirá em um milhão.
A carga de trabalho é dimensionada com o quadrado do número de dígitos.
Desde a antiguidade, os magos da matemática presumiam que esse limite quadrático era uma lei da natureza. Andrey Kolmogorov, uma lenda soviética, apostou sua reputação nisso em uma palestra em 1960. Ele disse aos estudantes da Universidade Estadual de Moscou: “É preciso O(n^2).” É uma conjectura formal. Um desafio. Espere que alguém prove ou quebre.
Demorou uma semana. Anatoly Karatsuba sentou-se na plateia. Ele tinha 23 anos. Ele voltou com provas de que Kolmogorov estava errado. O professor ficou surpreso. Na verdade, Kolmogorov escreveu ele mesmo o artigo para uma revista de prestígio, mas colocou o nome de Karatsuba nele. O garoto não sabia até que as reimpressões chegaram pelo correio.
O truque
Karatsuba percebeu algo simples, mas profundo. Multiplicações são caras. As adições são baratas. Por que não negociá-los?
Pegue 12 x 34.
Divida.
12 é 10 + 2.
34 é 30 + 4.
Tradicionalmente, você faz quatro multiplicações:
1×3
1×4
2×3
2×4
Karatsuba encontrou uma maneira de fazer isso com três.
Calcule a primeira parte: 1×3 = 3.
Calcule a última parte: 2×4 = 8.
Agora o meio. Normalmente você faria (1×4) + (2×3). Dois multiplicados. Em vez disso, adicione os primeiros números: 1+2=3. Some os últimos números: 3+4=7. Multiplique essas somas: 3×7=21. Subtraia as partes que você já conhece. 21 – 3 – 8 = 10.
Bum. Você obteve o termo médio com uma multiplicação extra.
Isso vale a pena?
Não para números pequenos. A sobrecarga de dividir e adicionar custa você.
Mas para 1.234 x 5.678? Divida ao meio. Recurso. Divida essas metades. Faça de novo. O composto de poupança.
O algoritmo cai para aproximadamente O (n ^ 1,585).
Números de mil dígitos costumavam exigir um milhão de múltiplos de um dígito. Agora são necessários menos de 57.000 passos. Enorme.
Isto não é apenas teoria. Está em Python.
Python usa matemática escolar padrão para pequenas entradas. Suave o suficiente.
Depois de atingir aproximadamente 63 dígitos decimais (dependendo da base da máquina), o Python aciona um botão. Karatsuba assume. Você não vê isso acontecendo. Mas está lá. Manipulando sua criptografia.
Algoritmos Galácticos
A corrida continuou por décadas. Podemos ir mais rápido?
2019 trouxe o choque mais recente. David Harvey e Joris van Der Hoeven publicaram um algoritmo que supera Karatsuba por um quilômetro.
Sobre (n log n).
Leia isso novamente.
Os logaritmos crescem incrivelmente devagar.
n log n é pouco maior que n.
Basicamente, multiplicar dois números enormes agora leva quase o mesmo tempo que lê-los.
É impressionante. O teto teórico parece ter sido tocado.
Ou talvez não.
Aqui está o problema.
Não funciona para números que nos interessam.
O algoritmo de Harvey e Van Der Hoeven só se torna mais rápido que Karatsuba quando os números ficam realmente grandes. Não é grande o “número do cartão de crédito”. Grande galáctico.
Na ciência da computação temos um termo para isso: algoritmo galáctico.
Linda teoria. Zero uso prático. Os números necessários são maiores do que a maioria das transações digitais combinadas na história da humanidade.
Estamos presos no meio.
Usando truques da década de 1960 para a maior parte da nossa computação diária.
Vestindo ternos do século 21 em cima da matemática do século 20.
Será que alguma vez usamos O(n log n) no mundo real?
Talvez quando processamos dados defina o tamanho das galáxias.
Até então esperamos.
Para o próximo truque.
Ou melhor hardware para esconder nossa preguiça.
A resposta ainda pode ser quadrática.
Pode ser linear.
Ainda não sabemos.
