División de 64/32 bits en un procesador con división de 32/16 bits

Question

My processor, un pequeño microcontrolador de 16 bits sin FPU y matemática entera solo tiene 16/16 división y 32/16 división, ambas toman 18 ciclos. En este momento estoy usando una rutina de software muy lenta (~ 7,500 ciclos) para hacer una división de 64/32. ¿Hay alguna forma de utilizar estos motores de división para calcular una división de 64/32? ¿Similar a cómo ya estoy usando el multiplicador y el sumador de 16x16 para calcular las multiplicaciones de 32x32? Estoy usando C pero puedo trabajar con cualquier explicación general sobre cómo se puede hacer ... Espero apuntar a < 200 ciclos (si es posible)

Answer 1

Consulte "Hacker's Delight", división de palabras múltiples (páginas 140-145).

El concepto básico (volviendo a Knuth) es pensar en su problema en términos de base-65536. Entonces tienes un problema de división de 4 dígitos por 2 dígitos, con división de 2/1 dígitos como primitiva.

El código C está aquí: http://www.hackersdelight.org/hdcodetxt/divmnu.c.txt

Answer 2

Mi copia de Knuth (El arte de Computer Programming) está en funcionamiento, por lo que no puedo verificarlo hasta el lunes, pero esa sería mi primera fuente. Tiene una sección completa de aritmética.

---

editar: su publicación sobre "división 16/16 y división 32/16 que ambos toman 18 ciclos". - Los dsPIC tienen una operación de resta condicional en el ensamblaje. Considere usar esto como su primitiva computacional.

También tenga en cuenta que si X = XH * 2 + XL y D = DH * 2 + DL, entonces, si usted está buscando

(Q, R) = X/D, donde X = Q * D + R

donde Q = QH * 2 + QL, R = RH * 2 + RL, entonces

XH * 2 + XL = DH * QH * 2 + (DL * QH + DH * QL) * 2 + (DL * QL) + RH * 2 + RL

Esto sugiere (examinado términos que son de alta 32 bits) para utilizar el siguiente procedimiento, similar a largo división:

1. (QH, R0) = XH/(DH + 1) -> XH = QH * (DH + 1) + R0 [32/16 brecha]
2. R1 = X - (QH * 2) * D [requiere un 16 * 32 se multiplican, un cambio-dada por 16, y una de resta 64 bits]
3. calcular R1' = R1 - D * 2
4. mientras que R1' > = 0, ajuste QH hacia arriba por 1, ajuste R1 = R1' , y vaya al paso 3
5. (QL, R2) = (R1 >> 16)/(DH + 1) -> R1 = QL * (DH + 1) + R2 [división 32/16]
6. R3 = R1 - (QL * D) [requiere un multiplicador de 16 * 32 y reste 48 bits]
7. calcular R3' = R3 - D
8. mientras que R3' > = 0, ajuste QL hacia arriba por 1, ajuste R3 = R3' , y vaya al paso 7

Su cociente de 32 bits es el par (QH, QL) y el resto de 32 bits es R3.

(Esto supone que el cociente no es mayor de 32 bits, lo que usted necesita saber antes de tiempo, y se puede comprobar fácilmente con anticipación.)

Answer 3

sólo puedo sugerir conseguir resultado por sustracción consecutiva y incremento del registro de resultados.Intentar dividir el registro de 64 bits en 2 o 4 partes y dividirlas por separado es un no-go, ya que la división entera introduce un error.

Answer 4

punto de partida sería: D. Knuth, The Art of Computer Programming Vol.2, Sección 4.3.1, el algoritmo D

Pero supongo que puede que necesite optimizar el algoritmo.

Answer 5

Es posible que desee mirar Booth's Algorithm (http://www.scribd.com/doc/3132888/Booths-Algorithm-Multiplication-Division).

La pieza que desea está aproximadamente a la mitad de la página.

No he visto esto desde mi clase VLSI, pero, esta puede ser su mejor opción, si es posible, es posible que desee hacer esto en conjunto, para optimizarlo tanto como sea posible, si va a llamar esto a menudo.

Básicamente implica desplazar, sumar o restar.