Se um hardware não suporta operações de módulo ou divisão, são necessários muito mais ciclos de CPU para simular módulo / divisão por software. Existe alguma maneira mais rápida de calcular a divisão e o módulo se o operando for 10?
No meu projeto, freqüentemente preciso calcular o módulo inteiro 10. Em particular, estou trabalhando no PIC16F e preciso mostrar um número em um LCD. Existem 4 dígitos para suportar, portanto, existem 4 chamadas para a função de módulo e divisão (implementação de software). Ou seja, como o seguinte:
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
Existem outras áreas que usam código semelhante.
Respostas:
Heres um algoritmo binário para BCD que usei há vários anos, com base em um encontrado aqui . Eu estava usando um driver de vídeo BCD externo para 7 seg para que o resultado pudesse ser gravado nas portas apropriadas diretamente como BCD compactado para saída.
Isso é bastante rápido se você tiver um multiplicador de hardware no PIC, eu estava usando um PIC18F97J60. Se você não possui um multiplicador de hardware no seu PIC, considere usar shift + add para a multiplicação.
Isso leva um int de 16 bits não assinado e retorna um BCD empacotado com 5 dígitos, podendo ser modificado e acelerado para 4 dígitos. Ele usa adições shift + para aproximar a divisão por 10, mas dado o intervalo de entrada limitado, é exato para esse uso. Convém empacotar o resultado de maneira diferente e alinhar-se com a maneira como você está usando o resultado.
fonte
Assumindo números inteiros não assinados, a divisão e a multiplicação podem ser formadas a partir de mudanças de bits. E da divisão (multiplicação) e multiplicação, o módulo pode ser derivado.
Para multiplicar por 10:
Dividir por 10 é mais difícil. Eu sei de vários algoritmos de divisão. Se bem me lembro, existe uma maneira de dividir por 10 rapidamente usando deslocamento de bits e subtração, mas não consigo lembrar o método exato. Se isso não for verdade, então esse é um algoritmo de divisão que gerencia <130 ciclos . Não tenho certeza de qual micro você está usando, mas você pode usá-lo de alguma forma, mesmo que seja necessário portá-lo.
Edição: Alguém diz no Stack Overflow , se você pode tolerar um pouco de erro e tem um grande registro temporário, isso funcionará:
Supondo que você tenha divisão e multiplicação, o módulo é simples:
fonte
Você pode converter de BCD para BCD empacotado sem nenhuma divisão usando o algoritmo de dabble duplo . Ele usa apenas shift e adiciona 3 .
Por exemplo, converta 243 10 = 11110011 2 em binário
Esse algoritmo é muito eficiente quando não há divisor de hardware disponível. Mais do que apenas o turno esquerdo de 1 é usado, por isso é rápido mesmo quando um deslocador de barril não está disponível
fonte
Dependendo da quantidade de dígitos necessários, você poderá usar o método de força bruta (
d
- número de entrada,t
- sequência ASCII de saída):Você também pode alterar os múltiplos ifs em um loop, com potências de dez obtidas por multiplicação ou uma tabela de pesquisa.
fonte
Esta nota de aplicação descreve algoritmos para aritmética do BCD, incluindo a conversão de binário para BCD e vice-versa. A appnote é da Atmel, que é o AVR, mas os algoritmos descritos são independentes do processador.
fonte
Não tenho uma boa resposta, mas há uma grande discussão em nosso site irmão Stack Overflow sobre o mesmo assunto de otimização de divisão e módulo.
Você tem memória suficiente para implementar uma tabela de pesquisa?
O Hackers Delight tem um artigo sobre algoritmos de divisão ideais.
fonte
Você já pensou em manter esse valor como BCD o tempo todo (usando sub-rotinas especiais simples de "incremento de BCD" e "BCD add"), em vez de manter esse valor em formato binário e convertê-lo em BCD conforme necessário (usando uma conversão mais difícil de entender) de binário para BCD "sub-rotina)?
Ao mesmo tempo, todos os computadores armazenavam todos os dados como dígitos decimais (marchas de dez posições, tubos de vácuo de código de duas em cinco, BCD etc.), e esse legado ainda permanece hoje. (consulte Por que os chips de relógio em tempo real usam BCD ).
fonte
O PICList é um recurso incrível para pessoas que programam processadores PIC.
Conversão BCD
Você já pensou em usar uma sub-rotina de binário para BCD já testada e testada, otimizada especificamente para o PIC16F?
Em particular, as pessoas na lista PICL gastaram muito tempo otimizando as conversões de binário em BCD em um PIC16F. Essas rotinas (cada uma otimizada manualmente para um tamanho específico) estão resumidas em "Métodos matemáticos de conversão de microcontolador PIC" http://www.piclist.com/techref/microchip/math/radix/index.htm
divisão inteira e mod
Em uma CPU como o PIC16F, uma sub-rotina especializada para dividir por uma constante geralmente é muito mais rápida do que uma rotina de uso geral "dividir variável A por variável B". Você pode colocar sua constante (nesse caso, "0,1") em "Geração de código para divisão / multiplicação constante" http://www.piclist.com/techref/piclist/codegen/constdivmul.htm ou confira o rotinas enlatadas próximas a http://www.piclist.com/techref/microchip/math/basic.htm .
fonte
Dada uma multiplicação de hardware 8x8, pode-se calcular um divmod-10 de um número de tamanho arbitrário usando uma rotina que o calcula para um número de 12 bits no intervalo de 0 a 2559, através do procedimento:
Eu sugeriria escrever uma rotina divmod em que o MSB do número estará em W e o LSB apontado pelo FSR; a rotina deve armazenar o quociente no FSR com pós-decréscimo e deixar o restante em W. Para dividir um comprimento de 32 bits por 10, usaria-se algo como:
Um passo divmod-6 seria muito semelhante, exceto usando constantes de 85 e 6 em vez de 51 e 10. Em ambos os casos, eu esperaria que o divmod10_step fosse 20 ciclos (mais quatro para a chamada / retorno), portanto um divmod10 curto seria cerca de 50 ciclos e um divmod10 longo seria de cerca de 100 (se um caso especial for o primeiro passo, poderá-se economizar alguns ciclos).
fonte
isso pode não ser o mais rápido, mas é uma maneira simples.
fonte