Quero contar aos leitores sobre um truque de programação que encontrei em algum tipo de livro de tradução que contém uma seleção desses truques naqueles dias em que ainda não havia sido inventado não apenas o byte, mas é assustador dizer a pilha e o grande Dijkstra ainda não amaldiçoou o operador GOTO (sic, em maiúsculas).
Gostei tanto do truque por sua simplicidade e graça que, já neste milênio, fiquei feliz em contar aos alunos sobre ele na forma da tarefa a seguir.
Imagine que, no processo de retorno da Lua em 2030, você subitamente descobriu que seu computador de bordo não está executando corretamente operações de multiplicação inteira, e isso certamente levará a um acidente durante o pouso.
Nesta história, não há nada particularmente fantástico. Lembremos, por exemplo, quais problemas ocorreram com os
processadores Pentium e, quando você foi enviado à Lua, ainda não havia alcançado a substituição total da importação. Em geral, é necessário verificar se os processadores foram perfurados especialmente.
Mas direto ao ponto. É necessário implementar com urgência a multiplicação programaticamente, para que ela funcione rapidamente em tempo real e se ajuste a um recurso disponível.
Do curso escolar de aritmética, lembramos que os números com valores múltiplos podem ser multiplicados por uma coluna, e o resultado da multiplicação de números individuais pode ser obtido da tabela de multiplicação.
Mas somente se os números forem escolhidos abreviados (por exemplo, 0 e 1), a tabela de multiplicação será curta e as colunas longas, e seu cálculo levará muito tempo.
Se, pelo contrário, pegarmos números longos (por exemplo, de 0 a 65535), então para aritmética de 16 bits
o resultado é obtido diretamente da tabela e as colunas estão ausentes. No entanto, o tamanho da tabela clássica de Pitágoras acaba por ser de cerca de 17 GB (4 * 65536 * 65536), se levarmos em conta a simetria em relação à diagonal, então metade é de cerca de 8,5 GB.
Pode ser um pouco demais.
Aperte e lembre-se de álgebra.
(1)2)Subtrair
(2) de
(1)e mais
Assim, tendo uma tabela de quadrados na matriz sqr, obtemos
a * b = (sqr [a + b] - sqr [a - b]) / 4
(*)O tamanho da tabela 8 * (65535 + 65535) é de cerca de 8,4 MB, o que já pode ser aceitável.
O tamanho do elemento da tabela de 8 bytes deve-se ao fato de que, para o máximo aeb, o quadrado da soma de 4 bytes não se encaixa - não há 2 bits suficientes.
A seguir, descreverei algumas melhorias, que não estavam no livro. Eu mesmo a inventei quando já estava escrevendo esta nota.
Observe que os dois bits menos significativos de um quadrado par são sempre 00 e o quadrado ímpar é sempre 01. Por outro lado, para qualquer par de números, sua soma e diferença têm a mesma paridade.
Portanto, em nossa fórmula
(*), o processo de subtração entre parênteses não pode ter hífens,
associado aos dois bits menos significativos. Portanto, o conteúdo dos elementos da tabela de quadrados
Você pode avançar dois bits para a direita e, assim, economizar metade da memória.
Finalmente nós temos
a * b = sqr4 [a + b] - sqr4 [a - b]
(**)onde sqr4 é a tabela de quadrados modificada.
No nosso exemplo, seu tamanho é de cerca de 4,2 MB.
Abaixo para ilustrar essa abordagem, o texto do programa Lua está incluído.
function create_multiplier(N)
Para processadores modernos, parece razoável ter um tamanho de dígito múltiplo do tamanho de bytes para facilitar o acesso a eles. Com dígitos de 1 byte, o tamanho da tabela é de apenas 1022 bytes, o que pode permitir que esse truque seja usado em processadores de 8 bits que não possuem multiplicação de hardware.
Serei grato a todos os leitores desta nota pelas correções e comentários.