Lição de casa aritmética

Lyoshenka, Lyoshenka, faça-me um favor!
Aprenda, Alyoshenka, a tabuada!
Agnia Barto


Primeira tarefa para um aluno da primeira série. Algum número positivo é dado. Você precisa multiplicar por outro número, desconhecido previamente. A questão é: como os nobres Dons aconselham fazer isso ??? Um desenvolvedor experiente certamente dirá, eles dizem cara, coloque o multiplicador e não se preocupe. E talvez seja fundamentalmente errado! Além dos monstros de Alterra e Xilinx, também existe uma família maravilhosa como o iCE-40 da Lattice . Ultra micro consumo. Muito barato. Sim, o problema é que eles são dolorosamente pequenos e, infelizmente, não há multiplicadores lá. Me deparei com isso há cerca de quatro anos atrás, quando eu transportava um certo codec ADPCM do assembler adsp-2185 para esse cristal.

Não, sem um multiplicador de uso geral (para duas variáveis) certamente não poderia ter sido feito. Eu tive que fazer isso com canetas e ele pegou metade do cristal. O problema é que ele trilhou em todos os meus passos, ou seja. sem janelas. Além da multiplicação de variáveis ​​no algoritmo, havia coeficientes fixos, que também precisavam ser multiplicados. E não havia como usar o multiplicador para isso, simplesmente não havia janela. E como a luta no projeto passou por cada célula, é claro que eu estava muito interessado em como desviar, e o uso das propriedades desses coeficientes faz o esquema ideal de multiplicação por eles (não um multiplicador de uso geral, mas um dispositivo de multiplicação por um determinado número!). Bem, como um sonho completo tornado realidade - para que os esquemas de multiplicação por diferentes coeficientes aproveitem ao máximo alguns recursos comuns de cristal.

Assim, a partir da tarefa para o aluno da primeira série, passamos suavemente à tarefa para o engenheiro e matemático. Como construir um esquema de multiplicação ideal para um determinado número específico?

Lembremos um pouco de como geralmente multiplicamos o número A por B.

1. Para começar, defina o resultado como zero.
2. Vamos examinar os bits A.
3. Se na descarga 0, não fazemos nada.
4. Se no bit 1, alteramos B pelo número correspondente de bits e adicionamos ao resultado.

No total, quanto menos unidades A estiverem nos dígitos, mais fácil será multiplicar por ele. Multiplicar por 2, 4 ou 8 é fácil. Apenas uma mudança é necessária. Um pouco mais difícil de multiplicar por 3, 5 ou 10. Será necessário um acréscimo. Ainda mais difícil de multiplicar por 11. Quanto mais unidades, mais difícil.

Bem, que tal multiplicar por 255? Até 8 unidades, uma tarefa de pesadelo, certo? E aqui estão as figuras! Vamos fazer uma simulação complicada com nossos ouvidos. Multiplique nosso B por 256 (ou seja, mude-o por 8 dígitos) e subtraia-o do resultado. Acontece que, apesar da aparência formidável, multiplicar por 255 é tão fácil quanto multiplicar por 10. É tão fácil multiplicar por 254, 240 e 224 (se você quiser, verifique!).

No total, a subtração ajuda na multiplicação. Lembre-se deste pensamento valioso. Enquanto isso, chamamos a dificuldade de um número de número mínimo de operações de adição (ou subtração) necessárias para multiplicar por ele. Os turnos não são levados em consideração. Pois no contexto do problema (temos circuitos, não programação!) Eles são obtidos por nada. Vamos formular uma afirmação óbvia, mas útil:

A dificuldade de um número é menor ou igual ao número de unidades em sua notação binária.
De fato, se multiplicarmos honestamente sem truques de subtração, como ensinamos na escola, o número de adições será igual ao número de unidades no binário A. E se começarmos a enganar e, além disso, tivermos sorte, reduziremos o número de operações.

Uma conseqüência interessante dessa afirmação:
A dificuldade de qualquer número de n bits é sempre estritamente menor que n .
Afinal, o maior número de unidades em um número de n dígitos é n , para um número como 255. Por outro lado, é claro que o foco, como na multiplicação por 255, podemos repetir para números de qualquer capacidade. Isso abre perspectivas de otimização de multiplicadores de uso geral.

Vamos dar uma olhada mais regular ao nosso raciocínio. Para começar, já temos algum tipo de esquema de multiplicação por A. Tomamos como a unidade. Todos os termos são movidos, somados e subtraídos de forma que o resultado seja o mesmo A. Total, nosso esquema de multiplicação por A nada mais é do que uma representação do número A como a soma das potências de dois, nas quais os termos podem estar tanto com o sinal + como com o sinal - . E você pode agrupar os termos positivo e negativo e dizer que o esquema é descrito pela diferença de alguns números A + e A- , igual a A. Isso é ruim ... Os membros da diferença podem ser arbitrariamente grandes. Vamos pensar se há alguma consideração para limitá-los?
Antes de tudo, observamos que cada potência de duas pode entrar no circuito apenas uma vez. De fato, se ela entrar duas vezes com o mesmo sinal, isso pode ser substituído por uma potência de dois por uma unidade de maior. Se ela entrar duas vezes com sinais diferentes, eles serão subtraídos mutuamente. No total, o esquema é muito semelhante à representação binária usual de A. A única diferença é que seus "bits" (a seguir denominados trits ) podem levar não dois, mas três valores: 1, 0 e -1.

Total Se A é um número binário de n bits, o esquema de multiplicação por ele é descrito pela soma:

$$

$$A = {t_m} 2 ^ m + {t_ {m-1}} 2 ^ {m-1} + .... + {t_1} 2 + {t_0}$$

onde $$${t_i}$- trits, assumindo os valores 1, 0 e -1, e m é um número desconhecido.

A seguir, chamaremos essa expressão de esquema ternário ou simplesmente esquema ou esquema de multiplicação para o número A.

Vamos tentar encontrar m . Como pode ser visto no exemplo com multiplicação por 255, m não é menor que n . Vamos ver se pode ser igual a n + 1 .
Seja A, como antes, um número positivo de n dígitos. Então o esquema de multiplicação é definido como:

$$

$$A = {t_ {n + 1}} 2 ^ {n + 1} + {t_ {n}} 2 ^ {n} + {t_ {n-1}} 2 ^ {n-1} .... + {t_1} 2 + {t_0}$$

Lembre-se que $$$2 ^ k + 2 ^ {k-1} + .... + 2 + 1 = 2 ^ {k + 1} -1$
Portanto, o trit mais alto não pode ser igual a -1. De fato, mesmo que todos os outros sejam 1, a soma ainda será -1. E pela condição A é positiva. Agora, deixe o trit principal ser 1. Mas, neste caso, o próximo trit deve ser -1. Caso contrário, a quantidade será muito grande. De fato, se o próximo trit é 0, a soma não será menor que $$$2 ^ {n + 1} - (2 ^ {n-1} + ... + 1) = 2 ^ {n + 1} - (2 ^ n - 1) = 2 ^ n + 1$
Enquanto n- bit A não é mais $$$2 ^ n - 1$. Mas se o trit principal for 1 e o próximo -1, a soma dos dois membros superiores será $$$2 ^ {n + 1} -2 ^ n = 2 ^ n$. Portanto, o trit principal é 0.

Assim, uma afirmação importante é comprovada: m = n .

Em outras palavras, para representar qualquer esquema de multiplicação por um n- bit A , n + 1 potências de dois são suficientes - de 0 a n (um a mais que a representação binária), o que imediatamente nos salva do infinito.

Agora você pode tentar calcular as dificuldades (veja acima) de qualquer número específico. A coisa mais simples é fazer o que fazemos escrevendo números binários em ordem. Somente em primeiro lugar, não temos bits aqui, mas trites (três valores possíveis); em segundo lugar, algumas combinações de trites dão números negativos e devem ser descartadas; em terceiro lugar, algumas combinações podem dar números coincidentes. Isso significa que, para esse número, existem vários esquemas.

Vamos escrever em python. Não porque sou muito fã dele, mas porque é extremamente conveniente trabalhar com ele em cadernos de anotações. Para começar, escrevemos a classe TriScheme que trabalha com os esquemas ternários apresentados acima, a função allSchemes, que calcula todos os esquemas para números de um determinado tamanho de bit por uma enumeração simples e a função printSchemes que imprime o resultado:


Calculamos os esquemas para todos os números de 4 bits:

0 0 1 [00000]
1 1 5 [0000+, 000 + -, 00 + -, 0 + ---, + ----]
2 1 4 [000 + 0, 00 + -0, 0 + - 0, + --- 0]
3 2 7 [000 ++, 00 + - +, 00 + 0-, 0 + - +, 0 + -0-, + --- +, + - 0-]
4 1 3 [00 + 00, 0 + -00, + - 00]
5 2 8 [00 + 0 +, 00 ++ -, 0 + -0 +, 0 + - + -, 0 + 0--, + - 0+, + - + -, + -0--]
6 2 5 [00 ++ 0, 0 + - + 0, 0 + 0-0, + - + 0, + -0-0]
7 2 7 [00 +++, 0 + - ++, 0 + 0- +, 0 + 00-, + - ++, + -0- +, + -00-]
8 1 2 [0 + 000, + -000]
9 2 7 [0 + 00 +, 0 + 0 + -, 0 ++ -, + -00 +, + -0 + -, + - + -, +0 ---]
10 2 5 [0 + 0 + 0, 0 ++ - 0, + -0 + 0, + - + - 0, + 0-0]
11 3 8 [0 + 0 ++, 0 ++ - +, 0 ++ 0-, + -0 ++, + - + - +, + - + 0-, +0 - +, + 0-0 -]
12 2 3 [0 ++ 00, + - + 00, + 0-00]
13 3 7 [0 ++ 0 +, 0 +++ -, + - + 0+, + - ++ -, + 0-0 +, +0 - + -, + 00--]
14 2 4 [0 +++ 0, + - ++ 0, + 0- + 0, + 00-0]
15 2 5 [0 ++++, + - +++, +0 - ++, + 00- +, + 000-]

Aqui, no início da linha, há um número, seguido por sua dificuldade (o número mínimo de elementos diferentes de zero no circuito), depois o número de circuitos e, finalmente, uma lista de circuitos.

No esquema, + indica 1, 0 - 0 e - - -1. O trit mais velho à esquerda (como na ortografia usual de números).

A tabela mostra, primeiramente, que apenas os números 13 e 11 têm dificuldade 3 (o máximo para números de 4 bits, conforme comprovado acima). E segundo, que o número de esquemas diferentes para cada número é bastante grande. Isso sugere, em primeiro lugar, que a multiplicação é mais frequentemente a operação é muito mais simples do que fomos ensinados na escola. E segundo, que para a implementação de dispositivos para multiplicar por várias constantes usando recursos comuns de cristal, a escolha de circuitos é bastante grande. Ainda mais interessantes são os dados em números mais longos. Portanto, para números de 14 bits, a dificuldade máxima é 8. E o número máximo de circuitos é 937.

Tudo ficaria bem, mas o algoritmo acima é muito caro. Sua complexidade cresce à medida que $$$3 ^ n$dependendo do tamanho dos números n . Para 8 dígitos conta instantaneamente. Por 14 minutos. Por 16 horas. Se você precisar ler os circuitos para todos os números de n bits, infelizmente, nada mais poderá ser feito, a não ser reescrevê-lo para C e levar um computador mais potente. No entanto, o algoritmo é perfeitamente paralelo e certamente pode ser executado na GPU ou no cluster.

Para o design de peças específicas de ferro, geralmente são necessárias listas de esquemas para números específicos. E tudo é desejável, e não apenas ideal. Para qual escolher, pode depender das circunstâncias (por exemplo, um dispositivo para multiplicar por várias constantes). E aqui você pode oferecer um algoritmo muito mais humano. Mais uma vez, lembramos a notável igualdade: $$$2 ^ k + 2 ^ {k-1} + .... + 2 + 1 = 2 ^ {k + 1} -1$.

No contexto da tarefa, isso significa o seguinte. Suponha que vários esquemas de trit seniores sejam conhecidos. Todos os trits menores começando na posição k são desconhecidos e são anteriormente considerados iguais a zero. Então, alterando os trits desconhecidos de qualquer forma, alteraremos o valor do circuito em não mais que mais / menos $$$2 ^ {k + 1} -1$. Além disso, com o avanço para os trits mais baixos, o valor dessa incerteza diminui. Isso permite procurar esquemas por aproximações sucessivas, trit após trit.

Seja dado um número positivo A. Precisamos encontrar todos os esquemas para isso entre números de n bits. O valor absoluto da diferença entre A e o valor de um determinado circuito é chamado de erro do circuito. Para começar, adotamos um esquema de n + 1 bit que descreve os números de n bits, todos desconhecidos e inicialmente definidos como zero. E vamos começar a definir trits, um por um, começando pelo mais antigo. Na k- ésima posição, o circuito pode gerar três novos padrões - com valores dos k- ésimos 1, 0 e -1. Deixamos na lista de esquemas para continuação apenas aqueles cujo erro não exceda $$$2 ^ k-1$. Com a lista resultante de circuitos, vamos para o passo na posição k-1 . Assim, na lista resultante (na posição 0), haverá TODOS os esquemas possíveis cujo valor é A. Vamos escrever essa função calcSchemes.


E, finalmente, a prometida venda de sonhos.

Nesse projeto, havia dois coeficientes que precisavam ser multiplicados: 16351 e 16318. Usando calcSchemes, encontramos os esquemas para esses coeficientes:


Temos sorte! Ambos os fatores têm dificuldade 3. Escolhemos os esquemas ideais para ambos:
Para 16318 + 0000000-0000-0 e para 16351 - + 00000000-0000- . Tivemos sorte novamente! Preste atenção às caudas dos esquemas. Eles para 16318 e 16351 diferem apenas no deslocamento para a esquerda em uma posição. Portanto, o dispositivo multiplicado por 16318 e 16351 inclui apenas um multiplexador adicional, alternando o operando com e sem deslocamento na entrada do somador.

Vamos ver o resultado. Escrevemos no veril três opções para o dispositivo de multiplicação por 16318 e 16351:

1. Opção "Escola" (apenas acréscimos e turnos)
2. Circuito ideal
3. Esquema ideal usando recursos compartilhados

Nas três opções, realizamos a síntese e vemos quantos recursos de cristal serão gastos em cada uma delas.


Todas as três opções funcionam corretamente, multiplicando-se em 0 na entrada s por 16318 e em 1 em 16351. Ao mesmo tempo, o yosys fornece 488 células para a versão escolar, 206 para a versão ideal e 202 para a variante com recursos compartilhados. otimiza, embora ainda exista uma diferença em 4 células. Como você pode ver, a diferença com a opção da escola é muito decente.

Bem, finalmente. Talvez pareça desnecessário alguém cercar um jardim assim, apenas para simplesmente perceber que 16318 = 16384-64-2 e 16351 = 16384-32-1. No entanto, em primeiro lugar, os números podem ser mais complicados. Em segundo lugar, se o dispositivo precisar multiplicar vários números, está longe de ser óbvio que esquemas ótimos devem ser adotados. Eu tive sorte nesse projeto. Em geral, um programa de busca de circuitos pode ajudar muito. Espero que o artigo seja útil para alguém. E quem leu, espero que não entre em pânico se precisar multiplicar, mas não há multiplicador.