¿La forma más rápida de obtener enteros mod 10 y enteros dividir 10?

Si un hardware no admite operaciones de módulo o división, se necesitan muchos más ciclos de CPU para simular módulo / división por software. ¿Hay alguna forma más rápida de calcular la división y el módulo si el operando es 10?

En mi proyecto, con frecuencia necesito calcular el módulo entero 10. En particular, estoy trabajando en PIC16F y necesito mostrar un número en una pantalla LCD. Hay 4 dígitos para admitir, por lo que hay 4 llamadas a la función de módulo y división (implementación de software). Es decir, como el siguiente:

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();

Hay otras áreas que usan un código similar.

Aquí hay un algoritmo binario a BCD que utilicé hace varios años basado en uno encontrado aquí . Estaba usando un controlador de pantalla BCD externo a 7 seg para que el resultado pudiera escribirse en los puertos adecuados directamente como BCD empaquetado para la salida.

Esto es bastante rápido si tiene un multiplicador de hardware en el PIC, estaba usando un PIC18F97J60. Si no tiene un multiplicador de hardware en su PIC, considere usar shift + add para la multiplicación.

Esto toma un 16bit int sin firmar y devuelve BCD empaquetado con 5 dígitos, podría modificarse y hacerse más rápido para 4 dígitos. Utiliza las adiciones shift + para aproximar la división por 10, pero dado el rango de entrada limitado, es exacto para este uso. Es posible que desee empacar el resultado de manera diferente para alinearse con la forma en que usa el resultado.

void intToPackedBCD( uint16_t n, uint8_t *digits ) {

    uint8_t d4, d3, d2, d1, d0, q;  //d4 MSD, d0 LSD

    d1 = (n>>4)  & 0xF;
    d2 = (n>>8)  & 0xF;
    d3 = (n>>12) & 0xF;

    d0 = 6*(d3 + d2 + d1) + (n & 0xF);
    q = (d0 * 0xCD) >> 11;
    d0 = d0 - 10*q;

    d1 = q + 9*d3 + 5*d2 + d1;
    q = (d1 * 0xCD) >> 11;
    d1 = d1 - 10*q;

    d2 = q + 2*d2;
    q = (d2 * 0x1A) >> 8;
    d2 = d2 - 10*q;

    d3 = q + 4*d3;
    d4 = (d3 * 0x1A) >> 8;
    d3 = d3 - 10*d4;

    digits[0] = (d4<<4) | (d3);
    digits[1] = (d2<<4) | (d1);
    digits[2] = (d0<<4);
}

Suponiendo enteros sin signo, la división y la multiplicación se pueden formar a partir de cambios de bits. Y a partir de la división (entera) y la multiplicación, se puede derivar el módulo.

Para multiplicar por 10:

y = (x << 3) + (x << 1);

Dividir por 10 es más difícil. Sé de varios algoritmos de división. Si recuerdo correctamente, hay una manera de dividir por 10 rápidamente usando cambios de bit y sustracción, pero no recuerdo el método exacto. Si eso no es cierto, entonces este es un algoritmo de división que administra <130 ciclos . No estoy seguro de qué micro está usando, pero puede usarlo de alguna manera, incluso si tiene que portarlo.

EDITAR: Alguien dice más en Stack Overflow , si puede tolerar un poco de error y tener un registro temporal grande, esto funcionará:

temp = (ms * 205) >> 11;  // 205/2048 is nearly the same as /10

Suponiendo que tiene división y multiplicación, el módulo es simple:

mod = x - ((x / z) * z)

Puede convertir de BCD a BCD empaquetado sin ninguna división utilizando el algoritmo de doble oscilación . Utiliza solo shift y add 3 .

Por ejemplo, convertir 243 ₁₀ = 11110011 ₂ a binario

0000 0000 0000   11110011   Initialization
0000 0000 0001   11100110   Shift
0000 0000 0011   11001100   Shift
0000 0000 0111   10011000   Shift
0000 0000 1010   10011000   Add 3 to ONES, since it was 7
0000 0001 0101   00110000   Shift
0000 0001 1000   00110000   Add 3 to ONES, since it was 5
0000 0011 0000   01100000   Shift
0000 0110 0000   11000000   Shift
0000 1001 0000   11000000   Add 3 to TENS, since it was 6
0001 0010 0001   10000000   Shift
0010 0100 0011   00000000   Shift
   2    4    3
       BCD

Este algoritmo es muy eficiente cuando no hay un divisor de hardware disponible. Se usa más sobre solo el desplazamiento a la izquierda en 1, por lo que es rápido incluso cuando no hay una palanca de cambios de barril disponible

Dependiendo de la cantidad de dígitos que necesite, puede usar el método de fuerza bruta ( d- número de entrada, t- cadena ASCII de salida):

t--;
if (d >= 1000) t++; *t = '0'; while (d >= 1000) { d -= 1000; *t += 1; }
if (d >= 100) t++; *t = '0'; while (d >= 100) { d -= 100; *t += 1;}
if (d >= 10) t++; *t = '0'; while (d >= 10) { d -= 10; *t += 1;}
t++; *t = '0' + d;

También puede cambiar los if múltiples en un bucle, con potencias de diez obtenidas por multiplicación o una tabla de búsqueda.

Esta nota de aplicación describe algoritmos para aritmética BCD, incluida la conversión de binario a BCD y viceversa. La nota de aplicación es de Atmel, que es AVR, pero los algoritmos descritos son independientes del procesador.

No tengo una buena respuesta, pero hay una gran discusión en nuestro sitio hermano Stack Overflow sobre exactamente el mismo tema de división y optimización de módulos.

¿Tiene suficiente memoria para implementar una tabla de búsqueda?

Hackers Delight tiene un documento sobre algoritmos de división óptimos.

¿Ha considerado mantener ese valor como BCD todo el tiempo (usando simples subrutinas especiales "Incremento de BCD" y "Añadir BCD"), en lugar de mantener ese valor en forma binaria y convertirlo a BCD según sea necesario (usando una conversión más difícil de entender de binario a BCD "subrutina)?

En un momento, todas las computadoras almacenaron todos los datos como dígitos decimales (engranajes de diez posiciones, tubos de vacío de código de dos de cinco, BCD, etc.), y ese legado aún perdura en la actualidad. (vea ¿Por qué los chips de reloj en tiempo real usan BCD? )

La PICList es un recurso increíble para las personas que programan procesadores PIC.

Conversión BCD

¿Ha considerado utilizar una subrutina binaria a BCD probada y probada, optimizada específicamente para el PIC16F?

En particular, las personas en la PICList han pasado mucho tiempo optimizando las conversiones de binario a BCD en un PIC16F. Esas rutinas (cada una optimizada a mano para un tamaño específico) se resumen en "Métodos matemáticos de conversión de radix de microcontoller PIC" http://www.piclist.com/techref/microchip/math/radix/index.htm

división entera y mod

En una CPU como la PIC16F, una subrutina especializada para dividir por una constante es a menudo mucho más rápida que una rutina de "división de variable A por variable B" de propósito general. Es posible que desee colocar su constante (en este caso, "0.1") en la "Generación de código para la multiplicación / división constante" http://www.piclist.com/techref/piclist/codegen/constdivmul.htm o consulte el rutinas enlatadas cerca de http://www.piclist.com/techref/microchip/math/basic.htm .

Dada una multiplicación de hardware de 8x8, se puede calcular un divmod-10 de un número de tamaño arbitrario mediante una rutina que lo calcula para un número de 12 bits en el rango de 0-2559 a través del procedimiento:

1. Asuma el número original en OrigH: OrigL
2. Divida el número original por dos y guárdelo en TempH: TempL
3. Agregue el MSB de TempL * 51 al LSB de TempH * 51. Ese es el cociente aproximado
4. Multiplique el cociente aproximado por 10, descartando el MSB del valor.
5. Reste el LSB de ese resultado del LSB del número original.
6. Si ese valor es 10 o mayor (el máximo será 19), reste 10 y agregue 1 al cociente aproximado

Sugeriría escribir una rutina divmod en la que el MSB del número estará en W, y el LSB señalado por FSR; la rutina debe almacenar el cociente en FSR con post-decremento y dejar el resto en W. Para dividir un largo de 32 bits por 10, uno usaría algo como:

  movlw 0
  lfsr 0, _number + 3; Point to MSB
  llamar a _divmod10_step
  llamar a _divmod10_step
  llamar a _divmod10_step
  llamar a _divmod10_step

Un paso divmod-6 sería muy similar, excepto el uso de constantes de 85 y 6 en lugar de 51 y 10. En cualquier caso, esperaría que divmod10_step sea 20 ciclos (más cuatro para la llamada / retorno), por lo que un breve divmod10 sería sería de aproximadamente 50 ciclos y un divmod10 largo sería de aproximadamente 100 (si un caso especial es el primer paso, se podrían ahorrar algunos ciclos).

Esto puede no ser el más rápido, pero es una forma simple.

 a = 65535;

    l = 0;
    m = 0;
    n = 0;
    o = 0;
    p = 0;

    while (a >= 10000)
    {   a -= 10000;
        l += 1;
    }
     while (a >= 1000)
    {   a -= 1000;
        m += 1;
    }
     while (a >= 100)
    {   a -= 100;
        n += 1;
    }
     while (a >= 10)
    {   a -= 10;
        o += 1;
    }
     while (a > 0)
    {   a -= 1;
        p += 1;
    }