Me gustaría preguntarle sobre el algoritmo de división que puedo implementar en el Ensamblador para el procesador i8080. Sé que el método más fácil es dividir por resta repetida pero es muy lento. Encontré muchos algoritmos de división, pero muchos de ellos son muy difíciles. ¿Alguien me puede dar un consejo?
La división de software es lenta (o compleja). El hardware para hacerlo generalmente implica más espacio o tiempo. Las tecnologías integradas bipolares implementaron en realidad una división de FP completamente combinatoria en hardware ... en el pasado. Pero tales hazañas no se hacen a menudo.
Ya tienes los comentarios básicos sobre la división que casi cualquiera que pruebe su mano aplicaría. Pero son más lentos de lo que necesitan ser. Incluso en un 8080A. (De hecho, aún poseo algunos de esos chips y su soporte. Y mi amigo más cercano aún tiene su Altair 8800 en funcionamiento, lo que es bastante bueno).
No hace mucho tiempo, me involucré en la mejora de la biblioteca de punto flotante para un compilador comercial para el chip MSP430. Pude mejorar dramáticamente el rendimiento aplicando lo que se llama "división no restauradora" y aplicando algunas ideas novedosas al diseño. Ningún otro compilador comercial podría alcanzar su velocidad, en ese momento. Resulta que escribí una pequeña documentación sobre el proceso que apliqué en los comentarios y los compartiré con ustedes aquí:
; This routine uses non-restoring division. If you aren't familiar with it,
; consider this idea:
;
; Call each step of the trial subtraction T[n]. At each step we want to test
; the result of 2 times the prior remainder minus the divisor. If the trial
; subtraction succeeds, we just shift the remainder one bit to the left and
; do the subtraction again. So at each step our successful trial subtraction
; it is something like this: ... T[i]=2*T[i-1]-D, T[i+1]=2*T[i]-D ... and so
; on. But if the trial subtraction fails, the divisor needs to added back
; to the remainder before before shifting and doing the next subtraction.
; Instead, this is T[i+1]=2*(T[i]+D)-D. But this is just T[i+1]=2*T[i]+D.
; Comparing these two results, you can see that the shift of T[i] still takes
; place, but that in this case addition of the divisor is used on the next
; step instead of subtraction. Non-restoring division is named that way
; because it replaces the addition+shift+subtraction used when subtraction
; from the remainder fails, with shift+addition. It alternates between
; shift+subtract and shift+add, depending on the quotient bit generated.
;
; The division loop is not unrolled here.
;
; This code needs to produce 24 good mantissa bits as a quotient, where the
; leading bit is '1', and we then need to also produce one final bit for
; rounding purposes. (If the leading bit -- the most significant one --
; isn't a '1', then we'd lose significance because of the fixed count of
; generated quotient bits.)
;
; The actual division code loop is best examined as a coroutine. Imagine
; the division routine something like the following diagram. Since program
; text is usually viewed under fixed-point fonts, it should render as a
; readable picture. I apologize for any difficulties in interpreting it:
;
; start
; |
; v
; ,-------,
; |frstbit|
; '-------' ,-------,
; ,-----> | | |
; | v v |
; | ,-------, ,-------, |
; | | sub | | add | |
; | '-------'----------, ,----------'-------' |
; | c=1 | c=0 \/ c=1 | c=0 |
; | v /\ v |
; | ,-------, <--------' '--------> ,-------, |
; | | rlc | | rla | |
; | '-------' '-------' |
; | | | |
; | v v |
; | ,-------, ,-------, |
; '<--| dec | | dec |-->'
; z=0 '-------' '-------' z=0
; | z=1 z=1 |
; v v
; ,-------, ,-------,
; | round1| | round0|
; '-------' '-------'
; | |
; v v
; '-------------> end <------------'
;
; The 'sub' code performs a trial subtraction step and the 'add' code per-
; forms the trial addition step. The 'rlc' code shifts in the carry in the
; case where the quotient bit is a '1'. The 'rla' code shifts in a '0' bit
; for the quotient. The 'dec' code checks for the loop end. 'frstbit'
; represents the generation of the first quotient bit. This is special
; because we know something about the relationship of dividend and divisor
; (the dividend and divisor both have their MSB=1 and are within a factor of
; two of each other, which as soon as the first subtraction takes place is no
; longer known) and we must ensure the leading bit is '1' and may need to
; adjust the exponent, plus init the loop counter. The 'round1' and 'round0'
; parts deal with differences in interpreting the final remainder for
; rounding, depending on what the last generated quotient bit was.
El código anterior no está "desenrollado". Es solo un bucle simple. Lo ejecutas por la cantidad de bits necesarios.
La esencia de ese código es evitar realizar una "adición" si una resta resulta en un resultado negativo. En cambio, la división simplemente cambia de marcha y continúa por un camino diferente, en cambio, va "por el otro lado" por un tiempo. Simplemente realiza un seguimiento de qué lado del pasillo está encendido y se desplaza cuando cambia el supuesto. También puedes hacer esto a mano, y verás que funciona.
Los ejemplos anteriores (y más abajo) requieren que la idea de "normalización" ya haya ocurrido. Esto solo significa que el bit inicial del dividendo y el divisor deben ser "1" y que debe hacer un seguimiento de la cantidad de turnos necesarios para obtener ese comienzo. Al hacerlo se garantiza que se produzcan resultados de máxima precisión. Pero dicha inicialización no es requerida en la división no restaurada. El mismo algoritmo funciona incluso cuando eso no ha ocurrido.
Tiendo a realizar la división como sin firmar, primero. (Capturo los signos, por supuesto.)
A menudo usaré un dividendo que es el doble del tamaño del divisor donde el algoritmo produce un cociente separado y el resto es del mismo tamaño que el divisor. Entonces, por ejemplo, podría tener un dividendo de 48 bits, un divisor de 24 bits, un cociente y un resto. Es apenas más código o tiempo de ejecución para hacer eso que para forzar que el dividendo sea del mismo tamaño. Y obtengo resultados más completos. Así que generalmente lo hago de esa manera. Pero no siempre. Depende.
Aquí hay un ejemplo de código que se desenrolla en una forma de by-8. Es mucho más rápido, ya que el control de conteo no se ejecuta con tanta frecuencia. Pero la compensación es el espacio de código. Pero cuando realmente necesitas velocidad, ayuda mucho:
; If you aren't familiar with non-restoring division, the consider this idea:
; Call each step of the trial subtraction T[n]. At each step we want to test
; the result of 2 times the prior remainder minus the divisor. If the trial
; subtraction succeeds, we just shift the remainder one bit to the left and
; do the subtraction again. So at each step our successful trial subtraction
; it is something like this: ... T[i]=2*T[i-1]-D, T[i+1]=2*T[i]-D ... and so
; on. But if the trial subtraction fails, the divisor needs to added back
; to the remainder before before shifting and doing the next subtraction.
; Instead, this is T[i+1]=2*(T[i]+D)-D. But this is just T[i+1]=2*T[i]+D.
; Comparing these two results, you can see that the shift of T[i] still takes
; place, but that in this case addition of the divisor is used on the next
; step instead of subtraction. Non-restoring division is named that way
; because it replaces the addition+shift+subtraction used when subtraction
; from the remainder fails, with shift+addition. It alternates between
; shift+subtract and shift+add, depending on the quotient bit generated.
;
; It is unrolled-by-8 in the sense that the code for generating each bit is
; copied 8 times in inline fashion, to avoid a conditional loop on each bit.
; Since a decrement and conditional jump require three cycles, doing that
; once for 8 bits is a big win over doing it once for each bit.
;
; This code needs to produce 24 good mantissa bits as a quotient, where the
; leading bit is '1', and we then need to also produce one final bit for
; rounding purposes. (If the leading bit -- the most significant one --
; isn't a '1', then we'd lose significance because of the fixed count of
; generated quotient bits.)
;
; The actual division code loop is best examined as a coroutine. Imagine
; the division routine something like the following diagram. Since program
; text is usually viewed under fixed-point fonts, it should render as a
; readable picture. I apologize for any difficulties in interpreting it:
;
; start ,-------, ,-------,
; | | | | |
; | | v v |
; | | ,-------, ,-------, |
; v | |movbyte| |movbyte| |
; ,-------, | '-------' '-------' |
; |frstbit| | | | |
; '-------' | v v |
; | | ,-------, ,-------, |
; | | |rlc/sub| |rla/add| |
; v | '-------'----------, ,----------'-------' |
; '------ | ----> | c=0 \/ c=1 | c=0 |
; | c=1 v /\ v |
; | ,-------, <--------' '--------> ,-------, |
; | |rlc/sub| |rla/add| |
; | '-------'----------, ,----------'-------' |
; | c=1 | c=0 \/ c=1 | c=0 |
; | v /\ v |
; | ,-------, <--------' '--------> ,-------, |
; | |rlc/sub| |rla/add| |
; | '-------'----------, ,----------'-------' |
; | c=1 | c=0 \/ c=1 | c=0 |
; | v /\ v |
; | ,-------, <--------' '--------> ,-------, |
; | |rlc/sub| |rla/add| |
; | '-------'----------, ,----------'-------' |
; | c=1 | c=0 \/ c=1 | c=0 |
; | v /\ v |
; | ,-------, <--------' '--------> ,-------, |
; | |rlc/sub| |rla/add| |
; | '-------'----------, ,----------'-------' |
; | c=1 | c=0 \/ c=1 | c=0 |
; | v /\ v |
; | ,-------, <--------' '--------> ,-------, |
; | |rlc/sub| |rla/add| |
; | '-------'----------, ,----------'-------' |
; | c=1 | c=0 \/ c=1 | c=0 |
; | v /\ v |
; | ,-------, <--------' '--------> ,-------, |
; | |rlc/sub| |rla/add| |
; | '-------'----------, ,----------'-------' |
; | c=1 | c=0 \/ c=1 | c=0 |
; | v /\ v |
; | ,-------, <--------' '--------> ,-------, |
; '<--|rlc/dec| |rla/dec|-->'
; z=0 '-------' '-------' z=0
; | z=1 z=1 |
; v v
; ,-------, ,-------,
; | round1| | round0|
; '-------' '-------'
; | |
; v v
; '-------------> end <------------'
Bueno, eso es todo por ahora. Si tiene alguna pregunta sobre el proceso, pregunte. He hecho un montón de codificación 8080 de montaje. Pero han pasado varias décadas desde entonces, así que ten cuidado si me veo un poco oxidado.
Necesitas usar el algoritmo de cambio y resta. Un ejemplo puede ser encontrado aquí; división .
En la década de los 70, tuve un problema con la división en un procesador de propiedad que tenía un registro BCD de 16 dígitos. Estaba contando las restas y observando el desbordamiento. Cuando solo pisé todo me pareció bien. Estaba tratando de calcular ocho porcentajes diferentes. Un día, dejé la cosa corriendo y fui a almorzar. Cuando volví, el primer porcentaje estaba hecho. Hacer algunos cálculos mostró que podría haber comenzado un pequeño número en una división de gran número en ese entonces y no se haría ahora.
Lea otras preguntas en las etiquetas assembler