¿Cuál es el algoritmo de división de enteros sin signo de 16 bits x 16 bits más rápido (en ciclos de reloj) que se ejecutará en un ATMEGA1284?

¿Cuál es el algoritmo de división más rápido (en ciclos de reloj) que se ejecutará en un ATMEGA1284?

  • El dividendo es un número de 16 bits sin signo que se pasa al algoritmo en un par de registros de 8 bits.
  • El divisor es un número de 16 bits sin signo que se pasa al algoritmo en un par de registros de 8 bits.
  • El cociente y el resto se distribuyen en cualquier par de registros de 8 bits.
  • El código del algoritmo (más las tablas de búsqueda) debe consumir menos de 5K bytes de memoria flash.
  • El algoritmo puede devolver cualquier valor para la división por 0.

Manual del conjunto de instrucciones AVR:
https://ww1.microchip.com/downloads/en/devicedoc/atmel-0856-avr-instruction-set-manual.pdf

AVR200: rutinas de multiplicación y división:
https://ww1.microchip.com/downloads/en/AppNotes/doc0936.pdf

El algoritmo que tengo hasta ahora toma entre 57 y 68 ciclos de reloj y usa 768 bytes de tablas de búsqueda. Realicé una prueba exhaustiva de 16 horas que verificó que calcula el cociente y el resto correctos para todas las 2^32 combinaciones de dividendo y divisor.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;ARGUMENTS:  r16, r17, r18, r19
;  r16:r17 = N (numerator)
;  r18:r19 = D (divisor)
;RETURNS:    r20, r21
;  r20:r21 (quotient)
;  r22:r23 (remainder)
;
;DESCRIPTION:  divides an unsigned 16 bit number N by unsigned 16 bit divisor D
;
;ALGORITHM OVERVIEW
;
;RZERO = 0;
;if(D < 256){
;  N2 = (N * ((R1H_TBL[D] << 8) + R1L_TBL[D])) >> 16;
;  P  = N2 * D
;}else{
;  D1 = (R1H_TBL[D] * D) >> 8
;  N1 = (R1H_TBL[D] * N) >> 8
;  if(D1 < 256){
;    N2 = N1 >> 8;
;  }else{
;    N2 = N2 * R2_TBL[D1 & 0xFF];
;  }
;  P = N2 * D;
;  if(P > 65535){
;    N2 = N2 - 1    ;//Decrement quotient
;    N1 = N2 - P + D;//Calculate remainder
;    return;//return quotient in N2, remainder in N1
;  }
;}
;N1 = N - P;
;if(P > N){
;  N2 = N2 - 1;//decrease quotient
;  N1 = N1 + D;//increase reamainder
;  return;//return quotient in N2, remainder in N1
;}
;if(N1 > D){
;  N2 = N2 + 1;
;  N1 = N1 - D;
;  return;//return quotient in N2, remainder in N1
;}
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
.align 256
;Recipricol table #1, high byte.
;R1H_TBL[x] = min( high(2^16/x) / 256 , 255)
R1H_TBL:
.db 0xFF, 0xFF, 0x80, 0x55, 0x40, 0x33, 0x2A, 0x24, 0x20, 0x1C, 0x19, 0x17, 0x15, 0x13, 0x12, 0x11
.db 0x10, 0x0F, 0x0E, 0x0D, 0x0C, 0x0C, 0x0B, 0x0B, 0x0A, 0x0A, 0x09, 0x09, 0x09, 0x08, 0x08, 0x08
.db 0x08, 0x07, 0x07, 0x07, 0x07, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x05, 0x05, 0x05, 0x05, 0x05
.db 0x05, 0x05, 0x05, 0x05, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04
.db 0x04, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03
.db 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02
.db 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02
.db 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02
.db 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01
.db 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01
.db 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01
.db 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01
.db 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01
.db 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01
.db 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01
.db 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01
;Recipricol table #1, low byte.
;R1L_TBL[x] = min( low(2^16/x) mod 256 , 255)
R1L_TBL:
.db 0xFF, 0xFF, 0x00, 0x55, 0x00, 0x33, 0xAA, 0x92, 0x00, 0x71, 0x99, 0x45, 0x55, 0xB1, 0x49, 0x11
.db 0x00, 0x0F, 0x38, 0x79, 0xCC, 0x30, 0xA2, 0x21, 0xAA, 0x3D, 0xD8, 0x7B, 0x24, 0xD3, 0x88, 0x42
.db 0x00, 0xC1, 0x87, 0x50, 0x1C, 0xEB, 0xBC, 0x90, 0x66, 0x3E, 0x18, 0xF4, 0xD1, 0xB0, 0x90, 0x72
.db 0x55, 0x39, 0x1E, 0x05, 0xEC, 0xD4, 0xBD, 0xA7, 0x92, 0x7D, 0x69, 0x56, 0x44, 0x32, 0x21, 0x10
.db 0x00, 0xF0, 0xE0, 0xD2, 0xC3, 0xB5, 0xA8, 0x9B, 0x8E, 0x81, 0x75, 0x69, 0x5E, 0x53, 0x48, 0x3D
.db 0x33, 0x29, 0x1F, 0x15, 0x0C, 0x03, 0xFA, 0xF1, 0xE8, 0xE0, 0xD8, 0xD0, 0xC8, 0xC0, 0xB9, 0xB1
.db 0xAA, 0xA3, 0x9C, 0x95, 0x8F, 0x88, 0x82, 0x7C, 0x76, 0x70, 0x6A, 0x64, 0x5E, 0x59, 0x53, 0x4E
.db 0x49, 0x43, 0x3E, 0x39, 0x34, 0x30, 0x2B, 0x26, 0x22, 0x1D, 0x19, 0x14, 0x10, 0x0C, 0x08, 0x04
.db 0x00, 0xFC, 0xF8, 0xF4, 0xF0, 0xEC, 0xE9, 0xE5, 0xE1, 0xDE, 0xDA, 0xD7, 0xD4, 0xD0, 0xCD, 0xCA
.db 0xC7, 0xC3, 0xC0, 0xBD, 0xBA, 0xB7, 0xB4, 0xB2, 0xAF, 0xAC, 0xA9, 0xA6, 0xA4, 0xA1, 0x9E, 0x9C
.db 0x99, 0x97, 0x94, 0x92, 0x8F, 0x8D, 0x8A, 0x88, 0x86, 0x83, 0x81, 0x7F, 0x7D, 0x7A, 0x78, 0x76
.db 0x74, 0x72, 0x70, 0x6E, 0x6C, 0x6A, 0x68, 0x66, 0x64, 0x62, 0x60, 0x5E, 0x5C, 0x5A, 0x58, 0x57
.db 0x55, 0x53, 0x51, 0x50, 0x4E, 0x4C, 0x4A, 0x49, 0x47, 0x46, 0x44, 0x42, 0x41, 0x3F, 0x3E, 0x3C
.db 0x3B, 0x39, 0x38, 0x36, 0x35, 0x33, 0x32, 0x30, 0x2F, 0x2E, 0x2C, 0x2B, 0x29, 0x28, 0x27, 0x25
.db 0x24, 0x23, 0x21, 0x20, 0x1F, 0x1E, 0x1C, 0x1B, 0x1A, 0x19, 0x18, 0x16, 0x15, 0x14, 0x13, 0x12
.db 0x11, 0x0F, 0x0E, 0x0D, 0x0C, 0x0B, 0x0A, 0x09, 0x08, 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01
;Recipricol table #2
;R2_TBL[x] = min( 2^16/(x+256), 255)
R2_TBL:
.db 0xFF, 0xFF, 0xFE, 0xFD, 0xFC, 0xFB, 0xFA, 0xF9, 0xF8, 0xF7, 0xF6, 0xF5, 0xF4, 0xF3, 0xF2, 0xF1
.db 0xF0, 0xF0, 0xEF, 0xEE, 0xED, 0xEC, 0xEB, 0xEA, 0xEA, 0xE9, 0xE8, 0xE7, 0xE6, 0xE5, 0xE5, 0xE4
.db 0xE3, 0xE2, 0xE1, 0xE1, 0xE0, 0xDF, 0xDE, 0xDE, 0xDD, 0xDC, 0xDB, 0xDB, 0xDA, 0xD9, 0xD9, 0xD8
.db 0xD7, 0xD6, 0xD6, 0xD5, 0xD4, 0xD4, 0xD3, 0xD2, 0xD2, 0xD1, 0xD0, 0xD0, 0xCF, 0xCE, 0xCE, 0xCD
.db 0xCC, 0xCC, 0xCB, 0xCA, 0xCA, 0xC9, 0xC9, 0xC8, 0xC7, 0xC7, 0xC6, 0xC5, 0xC5, 0xC4, 0xC4, 0xC3
.db 0xC3, 0xC2, 0xC1, 0xC1, 0xC0, 0xC0, 0xBF, 0xBF, 0xBE, 0xBD, 0xBD, 0xBC, 0xBC, 0xBB, 0xBB, 0xBA
.db 0xBA, 0xB9, 0xB9, 0xB8, 0xB8, 0xB7, 0xB7, 0xB6, 0xB6, 0xB5, 0xB5, 0xB4, 0xB4, 0xB3, 0xB3, 0xB2
.db 0xB2, 0xB1, 0xB1, 0xB0, 0xB0, 0xAF, 0xAF, 0xAE, 0xAE, 0xAD, 0xAD, 0xAC, 0xAC, 0xAC, 0xAB, 0xAB
.db 0xAA, 0xAA, 0xA9, 0xA9, 0xA8, 0xA8, 0xA8, 0xA7, 0xA7, 0xA6, 0xA6, 0xA5, 0xA5, 0xA5, 0xA4, 0xA4
.db 0xA3, 0xA3, 0xA3, 0xA2, 0xA2, 0xA1, 0xA1, 0xA1, 0xA0, 0xA0, 0x9F, 0x9F, 0x9F, 0x9E, 0x9E, 0x9D
.db 0x9D, 0x9D, 0x9C, 0x9C, 0x9C, 0x9B, 0x9B, 0x9A, 0x9A, 0x9A, 0x99, 0x99, 0x99, 0x98, 0x98, 0x98
.db 0x97, 0x97, 0x97, 0x96, 0x96, 0x95, 0x95, 0x95, 0x94, 0x94, 0x94, 0x93, 0x93, 0x93, 0x92, 0x92
.db 0x92, 0x91, 0x91, 0x91, 0x90, 0x90, 0x90, 0x90, 0x8F, 0x8F, 0x8F, 0x8E, 0x8E, 0x8E, 0x8D, 0x8D
.db 0x8D, 0x8C, 0x8C, 0x8C, 0x8C, 0x8B, 0x8B, 0x8B, 0x8A, 0x8A, 0x8A, 0x89, 0x89, 0x89, 0x89, 0x88
.db 0x88, 0x88, 0x87, 0x87, 0x87, 0x87, 0x86, 0x86, 0x86, 0x86, 0x85, 0x85, 0x85, 0x84, 0x84, 0x84
.db 0x84, 0x83, 0x83, 0x83, 0x83, 0x82, 0x82, 0x82, 0x82, 0x81, 0x81, 0x81, 0x81, 0x80, 0x80, 0x80

.def NH    = r16 .def NL    = r17
.def DH    = r18 .def DL    = r19
.def N2H   = r20 .def N2L   = r21
.def N1H   = r22 .def N1L   = r23
.def PRODL = r0  .def PRODH = r1
.def PH    = r2  .def PL    = r3
.def D1H   = r4  .def D1L   = r5
.def RZERO = r6
.def Rx    = r7 

idivu_16x16_x:
    clr RZERO                 ;1
    ;Check that DH is not zero
    tst DH                    ;1
    brne idivu_16x16_x_dhne   ;2
    ;code for D < 256   
idivu_16x8:
    ;lookup low byte of recipricol into P.
    ;where P = min(2^16 / D,2^16-1)
    mov zl, DL               ;1
    ldi zh, high(R1L_TBL*2)  ;1 
    lpm PL, Z                ;3
    ldi zh, high(R1H_TBL*2)  ;1 
    lpm PH, Z                ;3
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    ;calculate N2 = (P * N) >> 16
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    ;     NH:NL
    ;  X  RH:RL
    ;------------------------------------------
    ;   N2H    |   N2L    |  N1H     | dropped
    ;----------+----------+----------+---------
    ;          |          | H(PL*NL) | L(PL*NL)
    ;          | H(PL*NH) | L(PL*NH) |
    ;          | H(PH*NL) | L(PH*NL) |
    ; H(PH*NH) | L(PH*NH) |          |
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
    mul NL , PL     ;1  PL*NL
    mov N1H, PRODH  ;1  N1H <= H(PL*NL)
    mul NH , PH     ;1  PH*NH
    mov N2H, PRODH  ;1  N2H <= H(PH*NH)
    mov N2L, PRODL  ;1  N2L <= L(PH*NH)
    mul NH , PL     ;1  PL*NH
    add N1H, PRODL  ;1  N1H <= H(PL*NL) + L(PL*NH) 
    adc N2L, PRODH  ;1  N2L <= L(PH*NH) + H(PL*NH)
    adc N2H, RZERO  ;1  propagate carry to N2H      
    mul NL , PH     ;1  PH*NL
    add N1H, PRODL  ;1  N1H <= H(PL*NL) + L(PL*NH) + L(PH*NL)
    adc N2L, PRODH  ;1  N2L <= H(PH*NL) + L(PH*NH) + H(PL*NH)
    adc N2H, RZERO  ;1  propagate carry to N2H  
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    ;calculate P = N2 * DL ,note DH=0
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;    
    mul N2L, DL              ;1
    mov PL, PRODL            ;1
    mov PH, PRODH            ;1
    mul N2H, DL              ;1
    add PH, PRODL            ;1
    rjmp idivu_16x16_x_adj_n ;2
    ;code for D >= 256
idivu_16x16_x_dhne:          
    ;Lookup Rx = min(256 / DH, 255)     
    mov zl, DH               ;1
    ldi zh, high(R1H_TBL*2)  ;1 
    lpm Rx, Z                ;3
    ;D1 = (D * Rx) >> 8          
    mul Rx , DH              ;1
    mov D1L, PRODL           ;1
    mov D1H, PRODH           ;1
    mul Rx , DL              ;1
    add D1L, PRODH           ;1
    adc D1H, RZERO           ;1
    ;N1 = (D * Rx) >> 8          
    mul Rx , NH              ;1
    mov N1L, PRODL           ;1
    mov N1H, PRODH           ;1
    mul Rx , NL              ;1
    add N1L, PRODH           ;1
    adc N1H, RZERO           ;1
    ;if D1H = 0 then use Rx = 256, otherwise use table   
    tst D1H                  ;1
    brne idivu_16x16_x_dxhne ;2
    mov N2L, N1H             ;1
    clr N2H                  ;1
    rjmp idivu_16x16_x_checkn;2
    idivu_16x16_x_dxhne:
    ;Lookup Rx = (2 ^ 16) \ (256 + D1H)
    mov zl, D1L              ;1
    ldi zh, high(R2_TBL*2)   ;1
    lpm Rx, Z                ;3
    ;N2 = (N1 * R2) >> 16
    mul Rx  , N1H            ;1
    mov PL  , PRODL          ;1
    mov N2L , PRODH          ;1
    mul Rx , N1L             ;1
    add PL , PRODH           ;1
    adc N2L, RZERO           ;1
    clr N2H                  ;1
    idivu_16x16_x_checkn:
    ;Check result (it may be off by +/- 1)
    ;P = N2 * D
    ;NOTE:  N2 <=255 so NxH = 0, also P < 2^16 so we can discard upper byte of DH * NxL
    mul DL , N2L             ;1
    mov PL, PRODL            ;1
    mov PH, PRODH            ;1
    mul DH , N2L             ;1
    add PH , PRODL           ;1 
    brcc idivu_16x16_x_adj_n ;2
    ;if multiply overflowed then...
    ;decrement quotient
    ;calculate remainder as N - P + D
    subi N2L, 0x01           ;1
    sbci N2H, 0x00           ;1
    mov N1L, NL              ;1
    mov N1H, NH              ;1
    sub N1L, PL              ;1
    sbc N1H, PH              ;1
    add  N1L, DL             ;1
    adc  N1H, DH             ;1
    rjmp idivu_16x16_x_end   ;2
    ;Adjust result up or down by 1 if needed.
    idivu_16x16_x_adj_n:
    ;Add -P to N, with result in P
    mov N1L, NL              ;1
    mov N1H, NH              ;1
    sub N1L, PL              ;1
    sbc N1H, PH              ;1
    brsh idivu_16x16_x_pltn  ;2
    idivu_16x16_x_decn2:
    ;if P > N then decrement quotient, add to remainder
    subi N2L, 0x01           ;1
    sbci N2H, 0x00           ;1
    add  N1L, DL             ;1
    adc  N1H, DH             ;1
    rjmp idivu_16x16_x_end   ;2
    idivu_16x16_x_pltn:
    ;test remainder to D 
    cp  N1L, DL              ;1
    cpc N1H, DH              ;1
    ;if remainder < D then goto end
    brlo idivu_16x16_x_end   ;2
    ;if remainder >= D then increment quotient, reduce remainder
    subi N2L, 0xFF           ;1
    sbci N2H, 0xFF           ;1
    sub N1L, DL              ;1
    sbc N1H, DH              ;1
    idivu_16x16_x_end:
    ret
    .undef NH    .undef NL   
    .undef DH    .undef DL   
    .undef N2H   .undef N2L  
    .undef N1H   .undef N1L  
    .undef PRODL .undef PRODH
    .undef PH    .undef PL   
    .undef D1H   .undef D1L  
    .undef RZERO 
    .undef Rx
¿Cuál es tu pregunta, exactamente? Sin duda, puede haber algoritmos más rápidos, pero ¿cuál es exactamente su definición del algoritmo "más rápido"? ¿Nos pide que optimicemos su código?
Bastante seguro de que el operador C /funcionaría bastante bien.
@StarCat Fastest significa "toma la menor cantidad de ciclos de reloj" en este procesador y consume menos de 5K bytes de memoria flash para almacenar el código y las tablas asociadas. Siempre puede haber algún algoritmo más rápido (aún desconocido). Solo pido a las personas que proporcionen los algoritmos más rápidos que conocen para esta arquitectura de procesador. Los algoritmos presentados por Atmel en sus notas de aplicación toman 243 ciclos o 173 ciclos. Pude mejorar esto y bajarlo a 68 ciclos. Si alguien encuentra una manera de guardar ciclos de reloj en mi código existente, eso también cuenta como una respuesta.
@EugeneSh. Estoy bastante seguro de que no se compararía con esto, pero ¿es este código el más rápido posible ? Lo dudo, ¡necesito echar un vistazo más de cerca!
Seguramente una afirmación "lo más rápida posible" necesita una prueba formal.
@EugeneSh. Es probable que el código generado por un compilador de C sea una variante de la división de tipos de cambio y resta. Por lo tanto, es probable que sea comparable a la nota de la aplicación de Atmel, y probablemente varias veces más lenta de lo que ya tengo. Habiendo dicho eso, me encantaría ver una lista de desmontaje que demuestre lo contrario.
@EugeneSh. Exactamente mi punto.
@EugeneSh. A los efectos de esta pregunta, "el algoritmo publicado más rápido conocido" o "el más rápido que se me ocurrió que es mejor que lo que se ha publicado" cuenta como "el más rápido".
@ user4574 avr-gcc.senthilthecoder.com : aquí puedes jugar con el desmontaje.
De hecho, el Godbolt original también funciona: gcc.godbolt.org/z/sqxcvq .. pero tiene una llamada a una función incorporada, lo que no es útil, supongo.
@BruceAbbott Este código es 2,5 veces más rápido que lo que publicó Atmel, pero estoy de acuerdo, podría ser más rápido. Las tablas de búsqueda que estoy usando no tienen suficientes bits para calcular directamente la respuesta y requieren un paso adicional donde agrego +/-1 para corregir el resultado al final. El paso adicional usa alrededor de 10 ciclos. También en una rama hay una multiplicación que puede desbordarse y requiere una verificación adicional que toma algunos ciclos. El uso de más bits en los coeficientes de búsqueda eliminaría las comprobaciones, pero a costa de incluso más ciclos debido a las operaciones de multiplicación más grandes que se requieren para usarlos.
@ user4574 este es un algoritmo de división de propósito general. Estoy bastante seguro de que la mayoría del código que se ejecuta en un microcontrolador pequeño no necesita un algoritmo de propósito general. Es decir, creo que en muchos, si no en la mayoría de los casos, el divisor o el dividendo se conocerán en tiempo de compilación, lo que probablemente creará oportunidades para crear código que sea más rápido que esto.
@StarCat En este caso, necesito un algoritmo de división general. Lo estoy usando para calcular los puntos de intersección entre las formas y el borde de la pantalla para los algoritmos de dibujo de gráficos. Probablemente también lo usaré para hacer matemáticas en formas de onda capturadas.
@EugeneSh. Según su enlace, parece que GCC usa un algoritmo de cambio y resta en el procesador. Es muy pequeño, en cuanto a código, pero no tan rápido.
@ user4574 ¿Ha intentado un enfoque de co-rutina desenrollado y sin restauración utilizando solo registros y sin lecturas de memoria? Sospecho que llevará más tiempo. Pero tengo que preguntar, de todos modos.
@ user4574 A menudo quiero normalizar las entradas, antes. (Sin embargo, esto lo hace muy cercano al punto flotante). Me parece menos valioso saber que 14/31813 es 0 R 14, ya que no se ha descubierto nada nuevo que no se haya podido aprender con una simple comparación. Pero a menudo encuentro útil la operación si aprendo que el resultado es 59065 R 54991 E -27 D 63626 = (59065 + 54991/63626)*2^(-27). Sigue siendo una división de enteros. Justo precedida de normalización previa a los mismos pasos de división.
(@jonk: He jugado con no restaurar hasta el retorno - para "la ruta de 8 iteraciones para divisores con un byte alto distinto de cero". A 7-8 ciclos por bit más rápido que la ruta de 5 ciclos por bit para " hasta divisores de 7 bits" por encima de 11 iteraciones, a la par con 5-6 ciclos por bit para "divisores de 8 bits " .

Respuestas (1)

Esta pregunta se ha vuelto a hacer en Code Review@SE . De esa publicación:

Estoy buscando formas de reducir el tamaño del código, el tamaño de la tabla de búsqueda o la cantidad de ciclos de reloj.

Desde mi evaluación, el acceso a R1H_TBL(tabla de bytes altos de recíprocos) & R2_TBL[x]está en la ruta crítica, lo que hace que sea menos atractivo ir más allá de invertir un solo ciclo para "alejar el caso especial" de la mitad superior de R1H_TBL.
R1L_TBLestá fuera de la ruta crítica, lo que se suma a la molestia de no ver cómo reducirlo: invertí horas y horas tratando de hacer una aproximación polinomial usando la aritmética de un procesador de 8 bits .

¿Creerías que la mitad de los números enteros son pares ?
Cuando mi = 2 h , h ∈ ℕ , ⌊ 2 dieciséis mi ⌋ = ⌊ ⌊ 2 dieciséis h ⌋ 2 ⌋ : ¡no hay necesidad de entradas para números pares!
No se ha terminado de trabajar en los detalles (especialmente llevar de byte alto a bajo) o verificar la aplicabilidad a R2_TBL.
Me topé con esta reevaluación desenrollada de cambio y "resta" (antes: 88 ciclos "+ retorno", después de ~ 77, yendo por 70) después de descubrir que abordé las iteraciones de la manera incorrecta. (La forma más exitosa es usar una tabla para divisores pequeños , y una sola comparación para decidir qué es pequeño).

Pude bajar a 62 ciclos hasta ahora. Al reorganizar algunos registros, pude usar las instrucciones MOVW para mover algunos pares de registros en 1 ciclo de reloj. La referencia del conjunto de instrucciones muestra 2 ciclos para MOVW, pero la hoja de datos de la pieza muestra 1. Además, la generación de la tabla en RAM permite el acceso a la tabla de 2 ciclos en lugar de 3 ciclos para LPM. Esta parte tiene mucha RAM, por lo que es factible usar 256 * 3 bytes de RAM.
(@user4574: Actualmente, me temo que lo anterior no conduce a otra reducción viable del tamaño de la tabla: no he encontrado una manera de hacer las "escalas" necesarias lo suficientemente rápido. ¿Puede recomendar una presentación de la división de Goldschmidt y Newton? -Raphson para representaciones que no sean de punto flotante? ((Re-)descubrí Even/Seidel/Ferguson: un análisis de error paramétrico del algoritmo de división de Goldschmidt .) ¿Hay algún material de acceso público en el que se basa su código?)
Mi enfoque para desarrollar el algoritmo fue buscar algoritmos de división en Wikipedia para obtener ideas generales. en.wikipedia.org/wiki/Division_algorithm . Y para ver las recomendaciones de Atmel (que me gustó en la publicación original). En realidad, no conozco ningún buen artículo que pueda recomendar. Aunque, cabe señalar que con las tablas existentes obtienes una división de 8 bits x 8 bits casi gratis si estuvieras escribiendo esa función.
¿Cuál es el algoritmo de división de enteros sin signo de 16 bits x 16 bits más rápido (en ciclos de reloj) que se ejecutará en un ATMEGA1284?
RespuestasAquíPolítica de privacidad1y, 0v