¿La forma más rápida de obtener un entero mod 10 y un entero dividido 10?

Question

Si un hardware no admite operaciones de módulo o división, se necesitan muchos más ciclos de CPU para simular el 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 necesito con frecuencia calcular el módulo entero 10. En particular, estoy trabajando en el PIC16F y necesito mostrar un número en una pantalla LCD. Hay 4 dígitos para apoyar, por lo que hay 4 llamadas a la función de módulo y división (implementación de software). Es decir, como lo 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 utilizan un código similar.

Answer 1

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

Esto es bastante rápido si tienes un multiplicador de hardware en el PIC, yo estaba usando un PIC18F97J60. Si no tienes un multiplicador por hardware en tu PIC, considera usar shift + add para la multiplicación.

Esto toma un int sin signo de 16 bits y devuelve BCD empaquetado con 5 dígitos, podría ser modificado y hecho más rápido para 4 dígitos. Utiliza shift + sumas para aproximar la división por 10, pero dado el limitado rango de entrada es exacto para este uso. Es posible que quiera empaquetar el resultado de manera diferente para alinearse con la forma en que utiliza 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);
}

Answer 2

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

Para multiplicar por 10:

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

Dividir por 10 es más difícil. Conozco varios algoritmos de división. Si no recuerdo mal, hay una forma de dividir por 10 rápidamente usando desplazamientos de bits y sustracciones, pero no recuerdo el método exacto. Si eso no es cierto, entonces este es un algoritmo de división que gestiona <130 ciclos . No estoy seguro de qué micro estás usando, pero puedes usarlo de alguna manera, aunque tengas que portarlo.

EDIT: Alguien dice en Stack Overflow Si puedes tolerar un poco de error y tienes un registro temporal grande, esto funcionará:

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

Suponiendo que tengas la división y la multiplicación, el módulo es sencillo:

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

Answer 3

Dependiendo de la cantidad de dígitos que necesite, podrá utilizar 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 múltiples ifs en un bucle, con potencias de diez obtenidas por multiplicación o una tabla de búsqueda.

Answer 4

Esta nota de aplicación describe algoritmos para la 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.

Answer 5

El PICList es un recurso increíble para la gente que programa procesadores PIC.

Conversión BCD

¿Has pensado en utilizar una subrutina binaria a BCD ya probada y optimizada específicamente para el PIC16F?

En particular, la gente de la PICList ha dedicado mucho tiempo a optimizar 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 Radix del Microcontador PIC". http://www.piclist.com/techref/microchip/math/radix/index.htm

división de enteros y mod

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