UM DISCO CHEIO EMPRESTADO TORNA OS COMPUTADORES MAIS RÁPIDOS

Alguns problemas são baratos em tempo mas gulosos em memória, outros o contrário. Para algumas tarefas básicas, os teóricos provaram limites rígidos para este compromisso: com uma memória de trabalho pequena, não é possível ser rápido. Um novo artigo mostra que um recurso estranho, uma memória que já está cheia e tem de ser devolvida intacta, quebra esses limites.

O disco rígido emprestado

O modelo chama-se computação catalítica (catalytic computing), introduzido em 2014 por Buhrman, Cleve, Koucký, Loff e Speelman. Um algoritmo recebe uma minúscula memória limpa, da ordem de log n bits para uma entrada de tamanho n, mais uma enorme memória suja, já preenchida com dados arbitrários que não escolheu. Pode usar ambas como quiser, mas, quando para, cada bit da memória suja tem de estar exatamente como estava.

Os autores usam a imagem habitual: pede emprestado o enorme disco rígido de um amigo, cheio de preciosas recordações digitais, para fazer um cálculo. Não quer perder um amigo, por isso restaura cada bit no fim.

O modelo pretendia, de início, provar que tal memória é inútil. Intuitivamente, para restaurar tudo é preciso guardar toda a informação, pelo que nunca se liberta espaço. Surpreendentemente, revelou-se verdade o contrário: a memória cheia permite resolver problemas que ninguém sabe resolver só com memória limpa. Mas esses resultados diziam respeito ao espaço, e os algoritmos eram extremamente lentos.

Mais rápido do que é comprovadamente possível

Adelmo Morrison Orozco, Nathan Sheffield e Ryan Williams (MIT) olham agora para a velocidade. Com memória limpa logarítmica e uma quantidade polinomial de memória emprestada, apresentam algoritmos que:

• ordenam uma lista e calculam uma transformada de Fourier discreta em tempo n^(1+o(1)), quase linear;
• multiplicam matrizes em tempo n^(ω+o(1)), tão depressa como o melhor método conhecido com memória ilimitada.

Sem o disco emprestado, está provado que o produto do tempo pela memória tem de ser pelo menos da ordem de n² para a ordenação e a transformada de Fourier, e de n³ para a multiplicação de matrizes. Estes algoritmos catalíticos atingem, portanto, velocidades que nenhum algoritmo comum com pouca memória consegue atingir. Os autores chamam-lhe a primeira demonstração incondicional de que os algoritmos catalíticos superam os seus equivalentes não catalíticos.

Alternar, ler, desfazer

O ingrediente-chave é um pequeno truque combinatório. Suponha que um algoritmo consegue alternar uma secção da memória emprestada entre um valor desconhecido τ e τ + x, onde x é o resultado que lhe interessa. Numa grande tabela “auxiliar”, também emprestada, soma-se 1 a um conjunto de entradas cuidadosamente escolhido. A entrada na posição τ aumenta uma unidade se e só se x pertencer a um dado conjunto. Depois executa-se cada passo ao contrário, e o disco fica como antes, exceto pelo bocadinho de resposta que se queria.

Empilhando este truque camada a camada, avaliam-se rapidamente circuitos pouco profundos. Os autores reformulam depois redes de ordenação, transformadas rápidas de Fourier e multiplicação rápida de matrizes como circuitos desse tipo. Na aritmética, só as camadas que multiplicam duas incógnitas custam a mais; as camadas puramente lineares saem quase de graça.

Uma comparação justa

Uma objeção: os limites clássicos pressupõem que a resposta é escrita uma só vez, da esquerda para a direita, numa fita de saída separada, enquanto os algoritmos catalíticos escrevem a resposta no disco emprestado. O artigo responde a isto. Os autores mostram que os seus algoritmos conseguem escrever a resposta em duas passagens numa fita de saída, e que, para algoritmos comuns, duas passagens não ajudam mais do que uma. Os limites continuam, portanto, a aplicar-se, e a separação mantém-se. Provam também que uma passagem não basta, mesmo com o disco emprestado: a ordenação esbarra então na mesma barreira n².

Uma longa lista de beneficiários

As mesmas ferramentas dão algoritmos catalíticos rápidos para multiplicar inteiros grandes e polinómios, contar triângulos e encontrar cliques em redes, detetar caminhos e ciclos, e procurar padrões de texto com caracteres curinga. Os seus tempos de execução igualam, a menos de pequenos fatores, os melhores algoritmos conhecidos que dispõem de toda a memória que quiserem. Em todos os casos, a memória emprestada tem de voltar exatamente como foi cedida.