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

10

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 con frecuencia necesito calcular el módulo de enteros 10. En particular, estoy trabajando en PIC16F y necesito mostrar un número en un LCD. Se admiten 4 dígitos, 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 código similar.

    
pregunta Donotalo

10 respuestas

11

Aquí hay un algoritmo binario a BCD que usé hace varios años, basado en uno encontrado aquí . Estaba usando un controlador de pantalla BCD a 7 seg externo 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 Mayús + sumar para la multiplicación.

Esto incluye un int. sin signo de 16 bits y devuelve un 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 empaquetar el resultado de manera diferente y 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);
}
    
respondido por el Mark
8

Suponiendo que los enteros sin signo, la división y la multiplicación se pueden formar a partir de desplazamientos de bits. Y a partir de la división y multiplicación (enteras), 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 los cambios de bits y la resta, pero no puedo recordar 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á 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 tiene un gran registro temporal, esto funcionará:

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

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

mod = x - ((x / z) * z)
    
respondido por el Thomas O
6

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

Por ejemplo, convertir 243 10 = 11110011 2 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 se dispone de una palanca de cambio de barril

    
respondido por el phuclv
4

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

    
respondido por el jpc
2

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

    
respondido por el stevenvh
1

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

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

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

    
respondido por el Adam Lawrence
1

¿Ha considerado mantener ese valor como BCD todo el tiempo (usando subrutinas especiales especiales "Incremento de BCD" y "BCD agregado"), en lugar de mantener ese valor en forma binaria y convertirlo a BCD según sea necesario (usar un método más difícil de ¿entiende la subrutina "convertir de binario a BCD"?

Al mismo tiempo, 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 cada cinco, BCD, etc.), y ese legado aún perdura. (vea ¿Por qué los chips de reloj en tiempo real usan BCD ).

    
respondido por el davidcary
1

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

Conversión BCD

¿Ha considerado utilizar una subrutina de binario a BCD probada y probada en el mercado específicamente optimizada para el PIC16F?

En particular, las personas en la lista PIC han pasado mucho tiempo optimizando las conversiones de binario a BCD en una PIC16F. Esas rutinas (cada una optimizada a mano para un tamaño específico) se resumen en "Métodos matemáticos de conversión PIX de microcontrolador PIC" enlace

división entera y mod

En una CPU como la PIC16F, una subrutina especializada para dividir por una constante suele ser mucho más rápida que una rutina de propósito general "divide la variable A por la variable B". Es posible que desee poner su constante (en este caso, "0.1") en el "Generación de código para la multiplicación / división constante" enlace o visite las rutinas enlatadas cerca de enlace .

    
respondido por el davidcary
1

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

  1. Asume 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. Multiplica 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), resta 10 y suma 1 al cociente aproximado

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

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

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

    
respondido por el supercat
1

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;
    }
    
respondido por el sergiu

Lea otras preguntas en las etiquetas