Trucos de matemáticas binarias: cambiar para dividir por diez no es fácil

En CPU pequeñas, a menudo no tiene instrucciones múltiples o divididas. Por supuesto, los buenos programadores saben que cambiar de derecha a izquierda se multiplicará o dividirá por una potencia de dos. Pero siempre hay casos en los que necesitas usar algo que no sea una potencia de dos. A veces puedes calcularlo para la multiplicación.

Por ejemplo, multiplicar por 10 es común cuando se trata de la conversión entre binario y decimal. Pero desde entonces 10n es igual a 8n+2n, puede expresar esto como un conjunto de desplazamiento a la izquierda tres veces para multiplicar por ocho, agregando ese valor a su valor original movido hacia la izquierda una vez para multiplicar por dos.

Pero la división es otro problema. n/10 no es igual n/8-n/2 o algo tan simple como eso. El otro día, un amigo me mostró un fragmento de código muy complicado en el Stack Overflow de un usuario [realtime] que divide un número por 10 y quería saber cómo funcionaba. Es bastante simple si sigues con las matemáticas y te mostraré lo que quiero decir en esta publicación. Resulta que la publicación hacía referencia al venerable libro de Hacker Delight, que tiene muchas riquezas como esta.

Primero multiplica

Primero, hagamos algunos cambios para multiplicar. Cada giro a la izquierda es una potencia de dos, luego n<<1 es 2*n y n<<8 es 256*n. Eso es fácil. Lo difícil es descomponerlo por impotencias de dos: n<<3 + n<<1 es lo mismo que n*10

Si se reúnen haciendo un turno a la vez, a menudo pueden ahorrar algo de tiempo combinando los dos turnos:

SHL A
MOV A, T; Mueva A al almacenamiento temporal
SHL A
SHL A
AÑADIR A, T; Agregar T a A

Esto es bastante eficiente incluso en procesadores que pueden multiplicarse.

Los cambios de división funcionan, pero los compuestos son difíciles

La división es la misma, pero no se combina bien. Hacer n>>1 es n / 2 y n>>8 es n / 256. Pero no hay una manera fácil de combinar divisiones, ya que se pueden multiplicar.

El código que miramos se ve así:

unsigned divu10(unsigned n) {
  unsigned q, r;
  q = (n >> 1) + (n >> 2);
  q = q + (q >> 4);
  q = q + (q >> 8);
  q = q + (q >> 16);
  q = q >> 3;
  r = n - (((q << 2) + q) << 1); return q + (r > 9);
}

¡Aquí tienes un paquete! Pero funciona. El secreto para entender esto es tratar cada turno como una fracción del número. Eche un vistazo al primer taller:

q=(n>>1)+(n>>2)

Así es n/2 + n/4. Si recuerdas las matemáticas de tu escuela secundaria, eso es lo mismo que 3n/4. Por supuesto, esto es lo mismo que multiplicar por 0,75. Si mira hacia la última tarea de q, obtendrá una pista:q=q>>3;

Eso es lo que dice q = q/8. Entonces, si nuestro objetivo es dividir por 10, podría ser más fácil pensar en ello como multiplicar por 0.1. Para igualar bien las potencias de dos, realmente queremos pensar en multiplicar el total por 0.8 y luego dividir por 8.

Entonces, agregar un cambio correcto a dos cambios correctos nos da 0,75, que no está muy lejos de 0,8, pero no existe del todo. La siguiente línea agrega un poco más a nuestro factor de 0,75. ¿Cuánto más? La cantidad es 3n/64 y el total es ahora 51n/64. Eso equivale a 0,797 aproximadamente. Acercándome a 0.8 ya. Cada término agrega un poco menos y nos acerca un poco más. Así es como se desglosa: el último término te acerca un poco más. La 13107n/16384 el término está casi tan cerca.

Expresión Valor básico Delta Relación de valor total

(n >> 1) + n (>> 2)3n / 403n / 40,75
q + (q >> 4)3n / 4 + (3n / 4) / 163n / 6451n / 640,7969
q + (q >> 8)51n / 64 + (51n / 64) / 25651n / 1638413107n / 163840,7999
q + (q >> 16)13107n / 16384 + (13107n / 16384) / 6553613107n / 1073741824858993458n / 10737418240,8

No pude evitar pensar que esto sería bastante fácil de implementar en FPGA.

Comentar el Código

Aquí está el código con comentarios, que es un poco más fácil de seguir:

unsigned divu10(unsigned n) {
  unsigned q, r;
  q = (n >> 1) + (n >> 2); // q=n/2+n/4 = 3n/4
  q = q + (q >> 4);        // q=3n/4+(3n/4)/16 = 3n/4+3n/64 = 51n/644
  q = q + (q >> 8);        // q=51n/64+(51n/64)/256 = 51n/64 + 51n/16384 = 13107n/16384 q = q + (q >> 16); // q= 13107n/16384+(13107n/16384)/65536=13107n/16348+13107n/1073741824=858993458n/1073741824
  // note: q is now roughly 0.8n
  q = q >> 3;              // q=n/8 = (about 0.1n or n/10)
  r = n - (((q << 2) + q) << 1); // rounding: r= n-2*(n/10*4+n/10)=n-2*5n/10=n-10n/10
  return q + (r > 9);      // adjust answer by error term
}

Una vez que lo rompes, no es tan difícil de entender. Este método se remonta un poco, y parece que la fuente original es el libro. Alegría de un hacker (vea la Figura 10-12 en la segunda edición). No pude encontrar el sitio asociado, pero es una copia de archivo. La única diferencia en este código es la última línea comentada y reemplazada por: return q+((r+6)>>4);

El libro explica cómo averiguar los cambios óptimos y agrega y da varios otros ejemplos. También hay muchos otros trucos para compartir en ese capítulo. Si te gusta este tipo de cosas, echa un vistazo a la página sobre pequeños trucos de piratería. Si sus sueños de compartir tienden a desvanecerse, esto puede resultarle interesante.

  • Palmadita dice:

    “La división es la misma, pero no se combina bien. Entonces n >> 1 es n / 2 y n >> 8 es n / 256. Pero no hay una manera fácil de combinar divisiones, ya que se pueden multiplicar.

    El código que miramos tenía este aspecto “.

    O simplemente puede restar 10 del número anterior, regresando si se lleva, aumentando si no es así y haciendo un bucle. Mucho * más largo *, temporal, pero * significativamente * más compacto sin cambiador de barril. A veces, el tiempo de ejecución no importa. (También puede ser más rápido, dependiendo de cuál esperas que sea el rango). Siempre me rompe cuando la gente olvida la resta repetida de esa división.

    • X dice:

      “Devolver si lleva”, esta es una mala práctica porque los enteros sin nombre no “llevan”, el comportamiento es indefinido y ha creado un error realmente desagradable que lo morderá cuando cambie de compilador o plataforma.

      Bienvenido de nuevo al mundo mal definido de la aritmética C y por qué deberíamos renunciar a este lenguaje estúpido.

      • Palmadita dice:

        “Bienvenido de nuevo al mundo mal definido de la aritmética C”

        (mira lo que escribí)
        Uh … ¿exactamente dónde estaba el código C allí?

        Eso es un algoritmo. Si no puede entender cómo implementarlo en su idioma, ese no es el problema del algoritmo. Como referencia, en C, es sólo while (1) {if (n

        • Comedias dice:

          Utiliza los operadores de cambio C, por lo que una suposición C parece razonable según las reglas aritméticas, o la falta de ellas.

          • Palmadita dice:

            Ese no era yo, ese era el artículo principal citado.

          • pelrun dice:

            C no inventó el cambio.

      • Miguel dice:

        ¿Lenguaje estúpido? Entonces, ¿qué es mejor en tu mente que Python, tal vez? ¿Te atreves a adivinar en qué estaba escrito Python? Creo que lo llamas estúpido porque no sabes cómo usarlo.

    • Cuthbert dice:

      Sí, este método puede funcionar bien en algunos casos. También puede simplemente utilizar una subrutina de uso compartido de uso general. Claramente, esta publicación trata sobre la necesidad de que sea rápido. La última cosa pedante de la división de puntos no es la resta repetida; La división se define mejor como una operación de escala.

      • Palmadita dice:

        Los programas de propósito general ofrecen una compensación entre espacio y velocidad. La rutina aquí es un ángulo rápido, el que di es un ángulo espacial.

  • Artenz dice:

    Simplemente haga ‘/ 10’ y deje que el compilador lo entienda.

  • CityZen dice:

    En el código comentado, falta una nueva línea en la línea 5.

  • tekkieneet dice:

    Algunas UC pequeñas como la antigua 8051 tienen MUL y DIV. Ambos duran 4 ciclos. No lo suficiente como para hacerme querer usarlo.

    http://www.keil.com/support/man/docs/is51/is51_mul.htm

    • Valentin Angelovski dice:

      Si cree que 4 ciclos son malos, intente prescindir de ellos. Aquí hay un fragmento de código ASM de un algoritmo de multiplicación de 8×8 bits para el 8051 usando el método de cambio y adición (sin código de operación MUL): https://archive.thebearsenal.com/2016/01/multiplication-by-shift-and-add- método .html

      Un cálculo rápido del código ASM parece (en el peor de los casos) alrededor de 107 ciclos, a diferencia de “solo” 4 ciclos con el código de operación MUL específico. ¡Así que realmente ayudó! 🙂

  • CityZen dice:

    En el código, q = cociente, r = resto. El resto se calcula como (número de entrada) – 10 * q. Si el cociente fuera correcto, el resto siempre sería

  • PaulG dice:

    Ah, matemáticas cambiantes en c, amoroso.

    Consulte también “multiplicar por números mágicos para obtener una parte” de Hackers Delight.

    Este funcionó para mí:

    // para https://cboard.cprogramming.com/c-programming/128545-division-ten-magic-numbers.html

    div por 10 – funciona hasta 99,999

    int x = 150;

    (x * 6554UL) >> 16;

    https://github.com/cups/Binary-fun/blob/master/code/bitshift-division.c

    • Sykobee dice:

      Dividir por 10 en Z80 solo por ADD, funciona con números de 8 bits, usa la capacidad de 16 bits de Z80 y luego usa los 8 bits superiores como respuesta

      ; H = E 10
      e_div_10:
      ld d, 0
      ld h, d
      ld l, e
      agregar hl, hl
      agregar hl, de
      agregar hl, hl
      agregar hl, hl
      agregar hl, de
      agregar hl, hl

      funciona, pero es un juego de números.

      • RW versión 0.0.1 dice:

        Funcionaría de manera similar en el 6809, supongo, o en cualquier otra cosa que tenga 2 registros que se puedan insertar en uno de 16 bits.

  • Murray dice:

    Fácil, divida por casi todo … Supongamos que está trabajando en un número de 16 bits. Multiplíquelo por (0x10000 / 10) y mueva el resultado 16 bits a la derecha.
    Siempre que su deseado dividido por la cantidad sea constante, funciona de manera bastante eficiente. El compilador recibe el golpe por ti.

    • fanoush dice:

      tal vez el punto era usar solo un cambio y +, -, por lo que no hay multiplicación

      • Murray dice:

        Es cierto que la solución anterior supone que el hardware está proliferando. El hardware se multiplica de forma bastante barata en silicio, mientras que la división no. Incluso el humilde atmega8 de 8 bits incluye la duplicación de dispositivos, mientras que el más nuevo cortex m0 + de 32 bits aún excluye la división. La solución anterior es clara, fácil de entender y se extiende a una división de todos los números reales. Los algoritmos diseñados alrededor de constantes específicas, inevitablemente dan como resultado una solución diferente para diferentes constantes. Agrega carga de trabajo innecesariamente a los desarrolladores y depuradores. Nuevamente tienes razón, es necesario, pero es muy pequeño.

        • Phillip Allison dice:

          El 6502 y el 65C02 y sus variantes no tenían multiplicación ni división.
          Ni el Z80.
          Aunque te arruine lo que tienes ahora, para muchos de nosotros en los 70 y 80 tuvimos que pagar con lo que teníamos …

          Dividir en el Z80 fue fácil.

          Div8:
            xor a 
            ld b,16 
          LoopForDiv:
            add hl,hl
            rla
            cp d
            jp c,NxtBit
            sub d
            inc l
          NxtBit:
            djnz LoopForDiv
            ret
          
      • Artenz dice:

        Algunos compiladores (por ejemplo, Gcc) convertirán la multiplicación constante en cambiar / sumar / restar cuando tenga sentido. En ese caso, es mejor escribirlo como multiplicar y aumentar la portabilidad del código (o simplemente reducir el tamaño del código con la opción -Os, por lo que volverá a usar una biblioteca)

        • Palmadita dice:

          Es mejor escribirlo como una multiplicación, compilar y mirar el ensamblaje para asegurarse. GCC puede ser git exacto varias veces.

    • Murray dice:

      Donde uso más a menudo este tipo de técnica es en el escalado de ADC. Supongamos que tiene un ADC de 10 bits y el ADC es máximo a 23 V (esta es la entrada real antes del divisor de voltaje). Para calcular la cantidad de milivoltios, sin dividir, multiplique el resultado de ADC por 23000 y cambie a la derecha por el ADC exacto (en este caso, 10 bits). Esto genera un código portátil eficiente que es fácil de leer y que no necesita ser compartido.

  • Ninguno dice:

    ¿Cuántas CPU incluso decentemente modernas se beneficiarían de tal pirateo? No creo que te convierta en un buen programador el conocer muchos de estos trucos. De hecho, me ha impedido en el pasado preocuparme demasiado por actuar donde no era un problema. Otros lo llevan al extremo opuesto, razón por la cual demasiados programas son ahora recursos reales.

    La mayoría de las CPU, incluso en los años 90, tardaron solo unos pocos ciclos en dividirse. Con la canalización importa aún menos. Quizás esto sea para FPGA o algunos µC con muy bajo rendimiento. Pero en general no es muy útil, pero es una bonita curiosidad.

    • cosa alrededor del lugar dice:

      No hay tantas CPU modernas, estoy seguro, pero en realidad pude usar este artículo por completo hace unos 3 meses para algunos problemas integrados en los que no había una división disponible, pero los cambios eran baratos. En última instancia, tuve que recurrir a tablas de búsqueda precalculadas, que en última instancia podrían ser la mejor opción, pero esto sería muy bueno al menos para un punto de referencia.

      La cantidad de esfuerzo requerido para piratear una división por 10 fue una locura.

    • behle dice:

      Puede ser muy importante si considera manipulaciones de datos enormes como con el cálculo de matrices cuando realiza operaciones similares en una gran cantidad de números.
      No se dará cuenta de la ventaja de tiempo para una operación, pero realizará varios millones de operaciones.

      • Artenz dice:

        Si está haciendo esas cosas, probablemente sea una mejor idea encontrar una CPU con una separación rápida

  • jp314 dice:

    “Izquierda cambió tres veces para multiplicar por ocho, agregando ese valor a su valor original cambiado a izquierda una vez para multiplicar por dos”.
    no, eso es un total de 3 + 1 = 4 giros a la izquierda (aunque con un interruptor de barril son solo 2 operaciones de giro), en lugar de girar a la izquierda dos veces, agregue al original y al giro a la izquierda nuevamente. Menos operaciones, mismo resultado.

    • Palmadita dice:

      Mencionas, pero no lo digas explícitamente, que esto solo importa si no tienes un cambiador de barriles. En realidad, también podría ser más lento en algunas arquitecturas de superescala porque introduce dependencia de datos.

      Dicho esto, si le preocupa que una mano optimice la velocidad de ejecución, probablemente no tenga un desplazamiento de barril o una arquitectura de superescala.

  • Dave dice:

    ¡Fragmento de código asm Z80 en el artículo para ganar!
    Todas las demás CPU apestan.

    • Dave dice:

      Y me equivoco.

      Qué comentario tan tonto hice.

  • ágil dice:

    Mejor aún, use el hecho de que vive mod 2 ^ 32 y multiplique por el inverso modular: división por números enteros invariantes por multiplicación (y cambio o dos)

  • Robert Billing dice:

    Como solíamos hacer en el PDP-11 en los años 70 era tener una mesa de este tipo:

    tabla: .word 40000, 20000, 10000, 8000, 4000, 2000, 1000, 800, 400, 200, 100, 80, 40, 20, 10, 8, 4, 2 1

    Luego, para cada palabra de la tabla, compárela con el valor fuente. Si mesa

    • Artenz dice:

      En mi primera computadora doméstica 6502, la ROM BÁSICA tenía una matriz similar, pero solo con potencias de 10 (en 32 bits), y luego restaba repetidas veces para cada valor.

    • nes dice:

      Aquí hay un algoritmo para BCD que no requiere una tabla: repita sobre el registro de entrada, cambiando a la izquierda cada bit de MS en la parte inferior del registro de salida. Después de cada movimiento, agregue 3 a cualquier bocado en el registro de salida que sea> = 5.

      Si está utilizando una CPU con aritmética BCD o si está tratando con palabras> el tamaño de ALU, esta sería una forma más eficiente de hacerlo.

      • nes dice:

        Un poco de PoC de lo anterior, porque jugamos código …

        # incluir
        int main
        {
        int i;
        int a = 0xbc614e, b = 0;
        int x;

        printf (“0x% 08x”, a);
        por (i = 1; i; i 3) | ((b >> 2) & ((b >> 1) | b))) & 0x11111111;
        x | = x b = (b + x) se (a & (1 b | = 1;
        a }

        printf (“=% 08x n”, b);
        return 0;
        }

        • nes dice:

          Dios mío, los comentarios html obviamente no concuerdan con el operador de pala C. Aquí hay un enlace en su lugar:
          https://tio.run/##TY/dasMwDIWv46c4tGxYrBtxO8ogP0@yG9tJNkPnlCwdhqbPnklNO@YbH32SDjr@@cP7eV6H6A@npkX5PTahf/mslQpxxJcNUf/0oSF1VpmQUCy/RYU8Ob83r@0GTqpbJxVKZceBZadXeXrI3xJWG1jiftcP0IGHTcFOCChL1gQ2zxJjrR3qGjvCdNdbwuNdG@GOSFCezO0V1@WpQmI7XEu5h1eekOiPhQ7aipcRtDNEDHlyqpa@XY5hefkXoIIEeI@cwEmCoR1PQ5Swl3n@BQ

          • RW versión 0.0.3 dice:

            Dang, ¿qué hace ese sitio? ¿Codificas el contenido en las URL?

  • derp dice:

    si “cambia a la izquierda” demasiadas veces, Windows le pedirá que active las teclas adhesivas …

    • Mywk dice:

      Papá bromea … por qué, exactamente por qué …

    • Eb dice:

      ¡Usted, señor, me hizo reír! gracias por eso 😀

  • Alex Rossie dice:

    Me recuerda al famoso Q_rsqrt, la raíz cuadrada inversa rápida utilizada en Quake III Arena (pero presumiblemente existió antes).

    https://en.wikipedia.org/wiki/Fast_inverse_square_root#Overview_of_the_code

    Los comentarios de Cormacks (el código está en la wikipedia) lo describen mejor.

  • snarkysparky dice:

    (410 * N) >> 12 en innumerables enteros de 32 bits. Si su N no causará desbordamiento.

    Está lo suficientemente cerca para muchas cosas.

    410/2 ^ 12 = 0,10009765625

  • Stan dice:

    Esto es de lo que ahora es una memoria extremadamente pobre. Durante mi formación en Control Data en Londres hace 40 años y pico, un idioma que tuvimos que aprender fue ICL Plan (para ICL 1900). No hubo una separación innata, pero fue una rutina de la biblioteca. Para nuestro código, no se nos permitió usar la biblioteca, pero tuvimos que compartirlo nosotros mismos.

  • Matt Southgate dice:

    Gran artículo y ya tengo un buen camino a través de Hacked Joy. Tiene un error tipográfico en la línea de comentario del código de muestra 4: 51n / 644. Debería ser 51n / 64. Inicialmente me confundió como si nunca hubiera encontrado el enfoque fraccional de la división.

  • Adem Güneş dice:

    Hola,

    Quizás el formato BLD es lo que quieres. (BLD: aspecto decimal binario)

    Por ejemplo: sea N = 19735.

    Ahora conviértalo a BLD.

    19635
    04312: 11011
    02101: 00110
    01000: 00101
    00000: 01000

    Entonces el resultado es: 01000, 00101, 00110, 11011 ..

    Tenga en cuenta que estos no son números binarios, son números decimales regulares, pero solo componen 1 y 0.

    De hecho parece un BCD pero completamente diferente.

    Atrás: 1000 * 2 ^ 3 + 101 * 2 ^ 2 + 110 * 2 + 11011 = 8000 + 404 + 220 + 11011 = 19635

    Una ventaja es que solo trabaja con 1 y 0.

    Saludos

    PD: (C) Copyright de Adem GÜNEŞ

  • Vaquero dice:

    ¿Cómo se vería el artículo si tomara el atajo?

    • Vaquero dice:

      ¡Maldito sanador HTML!
      … lo que debe haber estado entre paréntesis:
      “Dividir por turnos es solo una multiplicación por una fracción donde un denominador es una potencia de dos, por lo que puede usar un compuesto tradicional (agregando) giros a la izquierda en el numerador y solo un giro a la derecha para el denominador. Cuanto mayor sea la potencia de dos, puede permitirle optar por el denominador, cuanto más se acerque a un resultado preciso “.

  • Kevin Nixon dice:

    Sí, esto sería fácil de implementar en FPGA, pero es mejor que use uno de los núcleos multiplicadores de cable duro que probablemente requiera menos energía y menos puertas que esta versión, que se implementaría con LUTs de tela y cadenas. Simplemente multiplicaría por 1/10 con el multiplicador.

Nora Prieto
Nora Prieto

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *