Algoritmo rapido de division 24/24 bits

[vixctor]

Este es un algoritmo bastante rapido que permite dividir numeros de 24/24 bits.

Fue creado ya que necesitaba un algoritmo sumamente rapido para dividir numeros grandes, la aplicacion, era un medidor de RPMs. Si bien ocupa algo de codigo, su eficiencia lo amerita para las aplicaciones, a continuacion se da una explicacion sencilla en la que se basa el codigo y el programa en .asm se encuentra hasta abajo, espero que les sirva en sus programas.

Saludos

Victor

PD. Todos los programas que subire, llevan las variables que se utilizan, plus los flags, y el codigo a continuacion mas un ejemplo de su uso.
Otros ejemplos y funcoines, los pueden encontrar en: este link

Código: [Seleccionar]

;*******************************************************************************************************
; Flags usados por la rutina de division de 24 bits...
;*******************************************************************************************************
#define      A_equal_B      flags_div_24,0   ; 0 = A don´t equal B 1 = A equal B
#define      A_mayor_B   flags_div_24,1   ; 0 = A < B, 1 = A > B

;********************************************************************************************************
; Variables de la division de 24 entre 24 bits
;********************************************************************************************************
   flags_div_24   ; estatus del proceso de la division de 24 bits
   pot_2      ; potencia de 2 que se utilizara para testeo de la division
   cont_shift      ; contador de recorrido de potencias de 2

   dividendo_lo   ; numero usado como dividendo de 24 bits parte baja
   dividendo_hi   ; numero usado como dividendo de 24 bits parte alta
   dividendo_up   ; numero usado como dividendo de 24 bits parte superior
  
   divisor_lo      ; numero usado como el divisior de 24 bits parte baja
   divisor_hi      ; numero usado como el divisior de 24 bits parte alta
   divisor_up      ; numero usado como el divisior de 24 bits parte superior

   res_lo      ; resultado de la division parte baja (8 bits)
   res_hi      ; resultado de la division parte alta (16 bits)
   res_up      ; resultado de la division parte superior (24 bits)

   sum_lo      ; suma de 24 bits parte baja
   sum_hi      ; suma de 24 bits parte alta
   sum_up      ; suma de 24 bits parte superior

   acum_lo      ; acumulador de valores temporales de 24 bits parte baja
   acum_hi      ; acumulador de valores temporales de 24 bits parte alta
   acum_up      ; acumulador de valores temporales de 24 bits parte superior


   shift_temp_lo   ; valor temporal del registro de corrimiento de 24 bits parte baja
   shift_temp_hi   ; valor temporal del registro de corrimiento de 24 bits parte alta
   shift_temp_up   ; valor temporal del registro de corrimiento de 24 bits parte superior
;********************************************************************************************************
;21 variables usadas
;********************************************************************************************************

;********************************************************************************************************
; EJEMPLO DE SU USO
;*******************************************************************************************************
; Carga de la base dividendo
;*******************************************************************************************************
   movlw   0xE4      ; Ejemplo, 15,000,000
   movwf   dividendo_up   ;
   movlw   0xE1      ;
   movwf   dividendo_hi   ;
   movlw   0xC0      ;
   movwf   dividendo_lo   ;
  
;*******************************************************************************************************
; Carga del divisor
;*******************************************************************************************************
   movlw   0x28      ; 15,000,000 / 2,678,571
   movwf   divisor_up      ;
   movlw   0xDF      ;
   movwf   divisor_hi      ;
   movlw   0x2B      ;
   movwf   divisor_lo      ;
;*******************************************************************************************************
   call   div_24      ; realizo la division correspondiente... 24/24 bits
;*******************************************************************************************************
   movf   res_lo,w      ; Este es el resultado de la division = 5
   movf   res_hi,w      ; Este es el resultado de la division = 0
   movf   res_up,w      ; Este es el resultado de la division = 0

   nop
   bra      $-2

;********************************************************************************************************
; CODIGO...
;********************************************************************************************************

;********************************************************************************************************
; div_24: Esta rutina realiza una division de un numero de hasta 24 bits, entre otro de hasta 24 bits.
; La division se realiza utilizando el metodo de corrimiento de registro, esto es: generando potencias de
; 2 tal que se vaya recosntruyendo el valor original.  El numero original se va multiplicando por 2 hasta
; que sea mayor que el dividendo, y luego, por medio de sumas, se verifica si ya se ha llegado al valor
; deseado, la ventaja VS el metodo de incremento, es en velocidad de procesamiento aunque se desperdicia
; espacio en codigo.  Sus parametros son: dividendo_up:dividendo_hi:dividendo_lo, que es el dividendo en
; 24 bits y divisor_up:divisor_hi_divisor_lo, que es el divisor de 24 bits, el resultado se da en:
; res_up_res_hi:res_lo, en 24 bits tambien.
;********************************************************************************************************
div_24
  
   clrf   cont_shift      ; inicializo el numero de corrimientos
   clrf   res_up      ; inicializo el resultado en 0
   clrf   res_hi      ;
   clrf   res_lo      ;

;********************************************************************************************************
; Hago una copia temporal del divisor_XX en sum_XX para poder ser usado el valor por la rutina de
; comparacion test_mag_24
;********************************************************************************************************
   movff divisor_lo,sum_lo           ; realizo un backup del valor para despues volver a restaurarlo...
   movff divisor_hi,sum_hi           ; sum_XX tiene la copia del valor de divisor_XX
   movff divisor_up,sum_up         ;

;********************************************************************************************************
; Validacion en caso que el divisor > que el dividendo de entrada a la rutina
;********************************************************************************************************
   call   test_mag_24   ; checo la magnitud del dividendo vs el divisor...
   btfss   A_mayor_B   ; El divisor es mayor que el dividendo?
   return         ; SI, por lo tanto, el valor entero de la division es 0

;********************************************************************************************************
first_aprox         ; busco el 1er valor que me aproxime al resultado de la division...
;********************************************************************************************************
   call   test_mag_24   ; checo la magnitud del dividendo vs el divisor...
   btfss   A_equal_B      ; Valores iguales?
   bra   continue_aprox   ; No, seguir continuando con la aproximacion...  
;********************************************************************************************************
; Todos los valores iguales, el resultado puede ser 1 o 2...
;********************************************************************************************************
   call   shift_24      ; recorro N bits a la izquierda para tener la potencia de 2 equivalente...  
   movf   shift_temp_lo,w   ; ahora, concateno los bits recorridos con el resultado...
   movwf   res_lo      ; para asi obtener las potencias de dos y por lo tanto el resultado final
   movf   shift_temp_hi,w   ; ahora, concateno los bits recorridos con el resultado...
   movwf   res_hi      ; para asi obtener las potencias de dos y por lo tanto el resultado final
   movf   shift_temp_up,w   ; ahora, concateno los bits recorridos con el resultado...
   movwf   res_up      ; para asi obtener las potencias de dos y por lo tanto el resultado final
   return         ; los 3 son iguales, por lo tanto, la division = 1

;********************************************************************************************************
continue_aprox
;********************************************************************************************************
   btfss   A_mayor_B   ; el dividendo es mayor que el divisor?
   bra   end_first      ; si, el numero seria mayor a la base de tiempo si lo multiplicara por 2...
   incf   cont_shift,f   ; he realidado una rotacion, la cuento...
   bcf   STATUS,C      ; inicializo el carry en cero para ir añadiendolos...
   rlcf   sum_lo,f      ; Byte LO rotado
   rlcf   sum_hi,f      ; Byte HI rotado
   rlcf   sum_up,f      ; byte_UP rotado
   btfss   STATUS,C      ; el bit msb de la rotacion de 24 bits fue 1?
   bra   first_aprox   ; me regreso a rotar hasta que el bit msb del periodo sea 1...
end_first

;********************************************************************************************************
; Restauro los valores de sum_XX a divisor_XX para poder continuar con la division...
;********************************************************************************************************
   movff      sum_lo,divisor_lo       ; realizo un backup del valor para despues volver a restaurarlo...
   movff      sum_hi,divisor_hi       ; sum_XX tiene la copia del valor de divisor_XX
   movff     sum_up,divisor_up      ;
   call   shift_right_NC   ; deshago el ultimo corrimiento para que divisor < dividendo... con carry
   decf   cont_shift,f   ; corrijo el contador de corrimientos decrementandolo...

;********************************************************************************************************
; Listo, primer valor calculado, ahora, procedo al ciclo para encontrar las potencias restantes...
;********************************************************************************************************
   movf   cont_shift,w   ; ahora, ya se que potencia inicial de 2 use, guardo el valor para testear
   movwf   pot_2      ; posteriormente las demas potencias...

;********************************************************************************************************
; Ahora subo al resultado la potencia inicial de dos que me aproxima al resultado
;********************************************************************************************************
   call   shift_24      ; recorro N bits a la izquierda para tener la potencia de 2 equivalente...  
   movf   shift_temp_lo,w   ; ahora, concateno los bits recorridos con el resultado...
   movwf   res_lo      ; para asi obtener las potencias de dos y por lo tanto el resultado final
   movf   shift_temp_hi,w   ; ahora, concateno los bits recorridos con el resultado...
   movwf   res_hi      ; para asi obtener las potencias de dos y por lo tanto el resultado final
   movf   shift_temp_up,w   ; ahora, concateno los bits recorridos con el resultado...
   movwf   res_up      ; para asi obtener las potencias de dos y por lo tanto el resultado final

   tstfsz   pot_2      ; si la potencia fue 0, es porque se trata de decimales que no calculare...
   bra   $+4      ; potencia diferente de 2, por lo menos realizare 1 ciclo
   return         ; listo, division terminada...

;********************************************************************************************************
; Hasta aca tengo la primera potencia de 2 calculada, las demas seran por suma y testeo del resultado...
;********************************************************************************************************
   movff      divisor_lo,acum_lo      ; realizo un backup del valor pues podria necesitar volver a restaurarlo...
   movff      divisor_hi,acum_hi      ; acum_XX tiene la copia del valor...
   movff      divisor_up,acum_up    ;

;********************************************************************************************************
loop_div_24
;********************************************************************************************************
   call   shift_right      ; primero, obtengo la potencia inferior de 2 de la ultima utilizada...
   bcf   STATUS,C      ; limpio el carry just in case...
   movf   divisor_lo,w   ; ahora, realizo la suma sumando primero las partes bajas y luego las altas
   addwf   acum_lo,w      ; resultado esta en el work
   movwf   sum_lo      ;

   movf   divisor_hi,w   ;
   addwfc   acum_hi,w      ;
   movwf   sum_hi      ;
  
   movf   divisor_up,w   ;
   addwfc   acum_up,w   ;
   movwf   sum_up      ;
;********************************************************************************************************
   btfsc   STATUS,C      ; hubo un desbordamiento en la suma?
   bra   dont_sum      ; Si, por lo tanto NO he de realizar la suma...
;********************************************************************************************************
   call   test_mag_24   ; checo si la suma fue menor o mayor a la base de tiempos...
;********************************************************************************************************
   btfsc   A_mayor_B   ; debo hacer la suma o no hacerla?
   call   sum_pot      ; SI, debo de hacer la suma...
   btfsc   A_equal_B      ; Los numeros fueron iguales?
   return         ; Si, numeros iguales, division terminada...

;********************************************************************************************************
dont_sum
;********************************************************************************************************
   decfsz   pot_2,f      ; he probado tooodas las potencias de 2?
   bra   loop_div_24   ; aun no, seguir probandolas hasta tener el resultado final...
   return         ; Division finalizada... =O)




;********************************************************************************************************
; test_mag_24: Esta rutina basicamente compara dos numeros de 24 bits para determinar cual es mayor...
; Los numeros a comparar estan en las variables: dividendo_XX = num A y sum_XX = num B
; SI A > B, entonces enciende la bandera A_mayor_B, por el contrario la pone en clear.
; SI A = B, entonces enciende la bandera A_equal_B, por el contrario la pone en clear.
;********************************************************************************************************
test_mag_24
   bsf   A_mayor_B   ; Asumo que A > B
   bcf   A_equal_B      ; Asumo que A no = B
   movf   dividendo_up,w   ; primero vs el byte mas significativo
   cpfseq   sum_up      ; es igual que sum_up?
   bra   $+4      ; no es igual, checar si es menor...
   bra   sum_upper_equal   ; es igual, comparar el bite de enmedio
   cpfslt   sum_up      ; es < que sum_up?
   bcf   A_mayor_B   ; B > A, lo indico...
   return         ; el byte superior es menor, por lo tanto, el resto de los bytes no importa
;********************************************************************************************************
sum_upper_equal
;********************************************************************************************************
   movf   dividendo_hi,w   ; segundo vs el byte de enmedio
   cpfseq   sum_hi      ; es igual que sum_hi?
   bra   $+4      ; no es igual, checar si es menor...
   bra   sum_middle_equal     ; es igual, comparar el bite de enmedio
   cpfslt   sum_hi      ; es < que sum_hi?
   bcf   A_mayor_B   ; B > A, lo indico...
   return         ; el byte medio es menor, por lo tanto, el resto de los bytes no importa
;********************************************************************************************************
sum_middle_equal
;********************************************************************************************************
   movf   dividendo_lo,w   ; es igual, comparar por ultimo el byte lsb...
   cpfseq   sum_lo      ; es igual que sum_lo?
   bra   no_equal_lo   ; no es igual, checar si es menor...
   bsf   A_equal_B      ; TODOS iguales, indico que A = B
   return         ; es igual, la suma es valida para este valor
no_equal_lo
   cpfslt   sum_lo      ; es < que sum_lo?
   bcf   A_mayor_B   ; B > A, lo indico...
   return         ; es byte aun es menor, por lo tanto, se puede seguir con el test...




;********************************************************************************************************
; shift_right: Esta rutina divide entre dos todo el divisor, de entrada lo hace con carry = 0 pero se
; puede seleccionar que tome en cuenta el ultimo valor de carry llamandola como shift_carry_24
;********************************************************************************************************
shift_right
   bcf   STATUS,C      ; limpio el carry para añadir ceros a los bits lsb
shift_right_NC
   rrcf   divisor_up,f   ; byte_UP rotado
   rrcf   divisor_hi,f   ; Byte HI rotado
   rrcf   divisor_lo,f   ; Byte LO rotado
   return         ;

;********************************************************************************************************
; shift_24: Esta rutina crea una potencia de 2 en base a lo que tenga como valor cont_shift, hara un
; recorrimiento N veces a la izquierda hasta que el contador = 0
;********************************************************************************************************
shift_24
   clrf   shift_temp_up   ; incializo mis registros de corrimiento temporales
   clrf   shift_temp_hi   ; incializo mis registros de corrimiento temporales
   movlw   d'1'      ; el valor comenzara en 1 cuando minimo  
   movwf   shift_temp_lo   ; partes baja y alta
   bcf   STATUS,C      ; el primer valor a recorrer sera el carry, que estara en 1...
;********************************************************************************************************
; Validacion en caso que la potencia sea 2 a la 0...
;********************************************************************************************************
   tstfsz   cont_shift      ; si el contador era cero, no debo de recorrer nada...
   bra   loop_shift_24   ; no es cero, recorrer N veces el bit...
   return               ;
;********************************************************************************************************
loop_shift_24
;********************************************************************************************************
   rlcf   shift_temp_lo,f   ; primero recorro el byte lsb
   rlcf   shift_temp_hi,f   ; despues recorro el byte msb
   rlcf   shift_temp_up,f   ; despues recorro el byte superior
   decfsz   cont_shift,f   ; he recorrido las posiciones deseadas?
   bra   loop_shift_24   ; aun no, seguir recorriendo
   return
;********************************************************************************************************

;********************************************************************************************************
; sum_pot: Esta rutina, actualiza el valor de acum_XX con el valor de sum_XX, ademas, hace una suma de
; OR inclusiva de las potencias que se han ido calculando previamente...
;********************************************************************************************************
sum_pot
   movff   sum_lo,acum_lo   ; este es el nuevo valor acumulado...
   movff   sum_hi,acum_hi   ; este es el nuevo valor acumulado...
   movff   sum_up,acum_up   ; este es el nuevo valor acumulado...
   decf   pot_2,w      ; asumo la potencia de 2 inferior a la actual
   movwf   cont_shift      ; ahora, concatenare esta potencia de 2 al resultado...
   call   shift_24      ; recorro N bits a la izquierda para tener la potencia de 2 equivalente...  
   movf   shift_temp_lo,w   ; ahora, concateno los bits recorridos con el resultado...
   iorwf   res_lo,f      ; para asi obtener las potencias de dos y por lo tanto el resultado final
   movf   shift_temp_hi,w   ; ahora, concateno los bits recorridos con el resultado...
   iorwf   res_hi,f      ; para asi obtener las potencias de dos y por lo tanto el resultado final
   movf   shift_temp_up,w   ; ahora, concateno los bits recorridos con el resultado...
   iorwf   res_up,f      ; para asi obtener las potencias de dos y por lo tanto el resultado final
   return         ; listo, suma y acumulador actualizados
;********************************************************************************************************


[groundman]

excelente. siempre viene bien tener programas multifuncionales para integrarlos en nuestros proyectos.

saludos.

[AlexFBP]

¿¿Pero no tendran alguna rutina similar para procesadores a 8 bits?? (p ej, PIC16F87xA, PIC16F6x8A) 

[MerLiNz]

he mirado el codigo que utiliza el C18 para las divisiones 24/24bits y es mas pequeño en comparacion con este, como de 40 lineas, creo que esta mucho mas optimizado que este, por lo menos eso parece. Si quereis pongo el codigo para que veis la diferencia.

[vixctor]

  MerLiNz:  Claro que el codigo de  C es muchismo más corto, pues se basa en acumulacion, por lo que su ejecucion es más laaaaaaarrrgaaaaaaa.

Este codigo, esta optimizado para hacer la division usando potencias de 2, de esta manera, la aproximacion al resultado, es muchisimo más rapida que el algoritmo de C, el cual he corrido y visto su ejecucion desde el list de la aplicacion.    El algoritmo normal, asume iniciar el divisor, y lo va sumando a si mismo hasta que el cociente es mayor que el dividendo, ahi es cuando termina la rutina.

So... te invito a que hagas una prueba...  Divide el numero mayor, que es de 24 bits, o sea 16777216 entre 1 = 16777216 con tu codigo y observa cuantos ciclos de reloj se tarda versus este algoritmo, el mio, se tardara solo 24 loops para encontrar el resultado.

Saludos

[tapi8]

Muy buen aporte, gracias.

Yo en estas operaciones me pierdo, lo simulare para ver su funcionamiento y asi aprender.

[MerLiNz]

no no, las funciones matematicas del C18 son en ASM, es mas te viene el codigo en C anulado con // y todo en ASM. Asi se puede observar lo que seria en C y como es en ASM

He probado a hacer lo que dices de dividir 2 numeros de 24bits 16777215/1, lo hace en 24 loops unicamente.

[MerLiNz]

te pongo el codigo para que lo examines

Código: [Seleccionar]

       
 // Clear the remainder
        clrf __REMB0, 0
        clrf __REMB1, 0
        clrf __REMB2, 0

        // Set the counter to 24
        movlw 24
        movwf INDF1, 0

        // Clear the carry flag
        bcf STATUS, 0, 0

loop:
    //AARG24 <<= 1; The carry is always clear at the top of the loop.
    rlcf __AARGB2, 1, 0
    rlcf __AARGB1, 1, 0
    rlcf __AARGB0, 1, 0

        // REM24 = (REM24 << 1) | (AARG24 >> 24)
    rlcf __REMB2, 1, 0
    rlcf __REMB1, 1, 0
    rlcf __REMB0, 1, 0

        //if (PROD >= BARG24)
    movf __BARGB2, 0, 0
    subwf __REMB2, 0, 0
    movf __BARGB1, 0, 0
    subwfb __REMB1, 0, 0
    movf __BARGB0, 0, 0
    subwfb __REMB0, 0, 0
    bnc _false
        //{
        //REM24-= BARG24;
        movf __BARGB2, 0, 0
        subwf __REMB2, 1, 0
        movf __BARGB1, 0, 0
        subwfb __REMB1, 1, 0
        movf __BARGB0, 0, 0
        subwfb __REMB0, 1, 0

incf __AARGB2, 1, 0
        //}

        _false:

        decfsz INDF1, 1, 0  // if (--count != 0) then loop. Does not affect carry flag.
        bra loop