¿Dónde puedo encontrar algoritmos dividir suave y se multiplican?

Question

Estoy trabajando en un microcontrolador sin necesidad de hardware multiplicar y dividir. Necesito cocinar algoritmos de software para estas operaciones básicas que son un equilibrio agradable de tamaño compacto y la eficiencia. Mi puerto compilador de C empleará estos algos, no los de los desarrolladores de C mismos.

Mi google-fu es lo que va apareciendo sobre todo el ruido sobre este tema.

Puede alguien me punto a algo informativo? Puedo utilizar Agregar / sub y instrucciones de desplazamiento. algos basadas búsqueda en la tabla podría también trabajo para mí, pero estoy un poco preocupado por abarrotar tanto en back-end del compilador ... um, por así decirlo.

Answer 1

Aquí hay un sencillo algoritmo de la multiplicación:

1. Comenzar con el bit más a la derecha del multiplicador.

2. Si el bit en el multiplicador es 1, añadir multiplicando

3. Shift multiplicando por 1

4. Mover a bit siguiente en el multiplicador y volver al paso 2.

Y aquí está un algoritmo de división:

1. Si divisor es más grande que los dividendos, parada.

2. Mientras registro divisor es menor que el registro de dividendos, desviación a la izquierda.

3. divisor registro de desplazamiento a la derecha 1.

4. Reste divisor registro del registro de dividendo y cambiar el bit a 1 en el registro de resultado en el bit que se corresponde con el número total de cambios realizados en el registro de divisor.

5. Empezar de nuevo en el paso 1 con divisor de registro en el estado original.

Por supuesto que tendrá que poner en un cheque por la división por 0, pero debería funcionar.

Estos algoritmos, por supuesto, son sólo para los números enteros.

Answer 2

Mi referencia favorita para cosas como esta, disponible en forma de libro:

http://www.hackersdelight.org/

También usted no puede ir mal con TAOCP: http: // www-cs-faculty.stanford.edu/~uno/taocp.html

Answer 3

Aquí hay un algoritmo de división: http: // www. prasannatech.net/2009/01/division-without-division-operator_24.html

supongo que estamos hablando enteros?

Si no hay soporte de hardware, que tendrá que implementar su propio excepción de división por cero.

(No he tenido mucha suerte con rapidez la búsqueda de un algoritmo de multiplicación, pero voy a seguir buscando si alguien no encuentra uno).

Answer 4

Una simple y algoritmo de la multiplicación bastante performant para los enteros es campesina rusa Multiplicación .

Para racionales, podría intentar un binario cita la notación , para los que la división es más fácil que costumbre.

Answer 5

Resulta que todavía tengo algo antiguo código 68000 ensamblador para el algoritmo de multiplicación y división larga. 68000 código es bastante limpio y simple, por lo que debe ser fácil de traducir para el chip.

El 68000 tenía multiplican y dividen a las instrucciones IIRC -. Creo que estos fueron escritos como un ejercicio de aprendizaje

decidimos a poner el código aquí. Añadido los comentarios y, en el proceso, fija un problema.

;
; Purpose  : division of longword by longword to give longword
;          : all values signed.
; Requires : d0.L == Value to divide
;          : d1.L == Value to divide by
; Changes  : d0.L == Remainder
;          : d2.L == Result
;          : corrupts d1, d3, d4
;

        section text

ldiv:   move    #0,d3     ; Convert d0 -ve to +ve - d3 records original sign
        tst.l   d0
        bpl.s   lib5a
        neg.l   d0
        not     d3
lib5a:  tst.l   d1        ; Convert d1 -ve to +ve - d3 records result sign
        bpl.s   lib5b
        neg.l   d1
        not     d3
lib5b:  tst.l   d1        ; Detect division by zero (not really handled well)
        bne.s   lib3a
        rts
lib3a:  moveq.l #0,d2     ; Init working result d2
        moveq.l #1,d4     ; Init d4
lib3b:  cmp.l   d0,d1     ; while d0 < d1 {
        bhi.s   lib3c
        asl.l   #1,d1     ; double d1 and d4
        asl.l   #1,d4
        bra.s   lib3b     ; }
lib3c:  asr.l   #1,d1     ; halve d1 and d4
        asr.l   #1,d4
        bcs.s   lib3d     ; stop when d4 reaches zero
        cmp.l   d0,d1     ; do subtraction if appropriate
        bhi.s   lib3c
        or.l    d4,d2     ; update result
        sub.l   d1,d0
        bne.s   lib3c
lib3d:                    ; fix the result and remainder signs
;       and.l   #$7fffffff,d2  ; don't know why this is here
        tst     d3
        beq.s   lib3e
        neg.l   d2
        neg.l   d0
lib3e:  rts

;
; Purpose  : Multiply long by long to give long
; Requires : D0.L == Input 1
;          : D1.L == Input 2
; Changes  : D2.L == Result
;          : D3.L is corrupted
;

lmul:   move    #0,d3       ; d0 -ve to +ve, original sign in d3
        tst.l   d0
        bpl.s   lib4c
        neg.l   d0
        not     d3
lib4c:  tst.l   d1          ; d1 -ve to +ve, result sign in d3
        bpl.s   lib4d
        neg.l   d1
        not     d3
lib4d:  moveq.l #0,d2       ; init d2 as working result
lib4a:  asr.l   #1,d0       ; shift d0 right
        bcs.s   lib4b       ; if a bit fell off, update result
        asl.l   #1,d1       ; either way, shift left d1
        tst.l   d0
        bne.s   lib4a       ; if d0 non-zero, continue
        tst.l   d3          ; basically done - apply sign?
        beq.s   lib4e       ; was broken! now fixed
        neg.l   d2
lib4e:  rts
lib4b:  add.l   d1,d2      ; main loop body - update result
        asl.l   #1,d1
        bra.s   lib4a

Por cierto - Nunca hice averiguar si era necesario convertir todo a positivo en la salida. Si usted tiene cuidado con las operaciones de cambio, que pueden ser aéreas evitable.

Answer 6

Para multiplicar, sumar productos parciales de la desplazado multiplicando a un acumulador si y sólo si el bit correspondiente en el multiplicador es set. Shift multiplicando y el multiplicador al final del bucle, probando multiplicador y 1 para ver si la adición se debe hacer.

Answer 7

Los chips de la serie Microchip PIC 16Fxxx no tienen una multiplicación o división de instrucciones. Quizás algunos de los blandos se multiplican y dividen a las rutinas suaves para que puedan ser transportados a su MCU.

de microcontroladores PIC matemáticas básicas métodos de multiplicación

de microcontroladores PIC matemáticas básicas Métodos División

También puedes ver "método de Newton" para la división . Creo que el método da el tamaño del ejecutable más pequeña de cualquier algoritmo de la división que he visto, aunque la explicación hace que suene más complicado de lo que realmente es. He oído que algunos superordenadores Cray primeros utilizan el método de Newton para la división.